Codeforces Global Round 7

A. Bad Ugly Numbers

n=1时,显然无解.

n>1时,第一位为2,后面全为3就是一个解.

B. Maximums

递推.

C. Permutation Partitions

最优答案肯定是让最大的k个数全部算上,让每个最大的k个数全部单独处在一个区间即可.

D2. Prefix-Suffix Palindrome (Hard version)

先找到仅由长度相等的最长的前后缀构成的回文串,然后如果前缀之后或者后缀之前还有一个回文串,可以把这个回文串插入到中间,易知这样构造出的答案一定是最优的.

将字符串翻转一下再扫一遍就可以求出两边的回文串,然后去掉两边的回文串,在中间剩下的字符串跑一边马拉车,就可以找到前缀后最长的回文串,翻转一下再跑一边就可以找到后缀前最长的回文串,看哪个长加哪个就行了.

赛后题解没有用马拉车,用了一个神奇的方法求某位置开始的最长回文串,但是我没看懂.