Codeforces Round #401 (Div. 2)做题记录

A. Shell Game

发现6次为一个位置的循环节,打表。。。

B. Game of Credit Cards

第一问的贪心就是莫里亚蒂的每个数字要尽量大于等于福尔摩斯的数字。记录下来福尔摩斯的十个数字的出现次数,并对每个人的数字排序。贪心的想法是莫里亚蒂的每个数字i从0到i一次找是否在福尔摩斯的数字中存在过就好了。

第二问贪心的想法是田忌赛马了。。。但是首先如果莫里亚蒂的最小数字大于福尔摩斯的最小数字肯定要选最小的,最大的大于福尔摩斯最大的选最大的。

C. Alyona and Spreadsheet
题意:给出一个n*m的数字矩阵(n*m<=100000),给出k个询问(k<=100000),询问形式是l,r。代表询问从第L行开始到第R行为止,是否存在一列是非单调递减的。是输出YES,否输出NO。
预处理出来每个位置最上可以延伸到哪一个位置,然后做一个n*m的dp就可以了。dp[i][j]代表(i,j)这个位置左边所有列中最上可以延伸到的位置。然后每次就可以O(1)回答了。

D. Cloud of Hashtags

题意:略。

从后往前贪心,如果对于第i个字符串发现第i+1个字符串字典序比它小,这也就意味着他需要把它从哪个字符开始字典序变小的字符全部删去。当然如果出现长度上的问题,多余的也需要删去。。。发现cin实在是太慢了,cin用了1400ms,scanf只需要148ms。。。。。

E. Hanoi Factory

题意:给出N个圆环(N<=100000),每个圆环有三个属性:a,b,h。a是内圆环半径,b是外圆环半径,h是这个圆环的高度。如果两个圆环i可以摆到j上面去,要求i的b要小于等于j的b。而且j的a要小于i的b,求最高高度。

比赛的时候想的dp啊。。。没写出来实在是自己太菜了。。。

对dp[i]代表第i个圆环的最大高度。先按照b降序排序吧,如果b相同就按照a降序排序,因为如果b相同的话肯定a越大的在最下面。然后把所有圆环的a和b离散化一下。然后每次对于第i个圆环,我们需要知道a小于他的b所有的圆环的最大的dp值。这个可以用线段树logn解决。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注