cf补题日记

听退役选手建议，补40道C、D题。

（又又又开新专题。。。

进度：2/40

 

原题1：

You are given a string ss, consisting of digits from 00 to 99. In one operation, you can pick any digit in this string, except for 00 or the leftmost digit, decrease it by 11, and then swap it with the digit left to the picked.

For example, in one operation from the string 10231023, you can get 11031103 or 10221022.

Find the lexicographically maximum string you can obtain after any number of operations.

（每个数可以和它左边的数交换，请找到交换后string的最大值）

原题2：

Alice and Bob participate in a fishing contest! In total, they caught nn fishes, numbered from 11 to nn (the bigger the fish, the greater its index). Some of these fishes were caught by Alice, others — by Bob.

Their performance will be evaluated as follows. First, an integer mm will be chosen, and all fish will be split into mm non-empty groups. The first group should contain several (at least one) smallest fishes, the second group — several (at least one) next smallest fishes, and so on. Each fish should belong to exactly one group, and each group should be a contiguous subsegment of fishes. Note that the groups are numbered in exactly that order; for example, the fishes from the second group cannot be smaller than the fishes from the first group, since the first group contains the smallest fishes.

Then, each fish will be assigned a value according to its group index: each fish in the first group gets value equal to 00, each fish in the second group gets value equal to 11, and so on. So, each fish in the ii-th group gets value equal to (i−1)(i−1).

The score of each contestant is simply the total value of all fishes that contestant caught.

You want Bob's score to exceed Alice's score by at least kk points. What is the minimum number of groups (mm) you have to split the fishes into? If it is impossible, you should report that.

（B想比A钓鱼的贡献多k，求至少要将鱼分多少组。第一组贡献为0，第二组为1，……第n组为n-1）

 

1.Digital string maximization（991.D）

思路：

赛时一直冥思苦想，怎么能找到每个位置上最大值，并且给他们换上去呢？想的我脑袋都大了。事实上，暴力居然能过。从0~n-1遍历string，对每个i，从0~i遍历i，如果s[j-1]<s[j]-1，就将两数交换，即以该数组的排序方式进行排序，每次排序，前面i个数都是从大到小的，所以碰到s[j-1] >= s[j]-1，就可以直接break。

 

 

2.Competitive Fishing（edu 172.C）

记得开long long!

思路：

这道题真的很有意思，最多能放n-1个隔板，每个隔板只对隔板右边的数有影响，隔板带来的贡献为右边的1总数-0总数，计算出n-1个隔板各自的贡献后排个序，从大贡献的隔板开始放，直到res>=k。

下图为举例。