AtCoder Regular Contest 060
I also really like this issue of Regular Contest. The questions are very interesting, question link.
C Tak and Cards
The meaning of question C is to give N (N<=50) numbers, each number ranges from 1 to 50, and then give a value A. Select a number arbitrarily from these N numbers. The average of the selected numbers is A. How many selection methods are there?
dp[i][j][x] represents the number of ways that when the i-th number is reached, there are j numbers that sum to x.
D Digit Sum
The meaning of question D is that a function f(b,n) is given,
$$
f(b,n)=n \ \ \ \ when\ \ n<b
$$
$$
f(b,n)=f(b,floor(\frac{n}{b}))+(n%b)
$$
Then given n and s, find the smallest b such that f(b,n)=s. If there is no such b, output -1.
Next time you see a question where n and b range from 10^11 to 10^12, just consider O(sqrt(n)).
First consider the situation of b<sqrt(n) and directly calculate it violently.
Then consider b>sqrt(n), then n=pb+q, and p+q=s. We get n-s=b*(p-1) because b>sqrt(n), so p is smaller than sqrt(n). Enumerate p and note that q must also meet the conditions.
E Tak and Hotels
The meaning of question E is that the coordinates of n hotels are given, and then a person travels a distance of no more than L in one day and must sleep in the hotel at night. Then there are Q questions asking how many days it will take to walk from a to b. It is guaranteed to be reachable.
The idea of doubling, dp[x][a] represents the farthest hotel that can be reached after 2^a days from x, and then each time the query is violent from the highest to the lowest.
F Best Representation
I found that Japanese people in AtCoder like to ask this kind of questions, and I can’t say very well about what kind of questions they are
If the string X can be expressed as a concatenation of k (k>=2) strings a, it is not a good string, otherwise it is a good string.
Now given a string, it is required to decompose this string into strings that are all good strings. . . Ask what is the minimum number of decomposed strings among all successfully decomposed sets. Let it be ans. How many division methods are there so that the minimum number of strings is ans? Output ans and how many division methods there are. = =. Suddenly I realized that my language skills are so poor. If you don’t understand, just read in English. Of course, I think that is quite difficult to understand.
The fun part of this question is that, excluding the case where all characters are equal (in this case, the output is strlen(w), 1, needless to say), the minimum number of decomposed strings must be either 1 or 2. It is 1 when the string itself is a good string. When this string can be expressed as a concatenation of k (k>=2) strings a, then at this time, hey hey (…), if it is split, the former will have one more and the latter will have one less, and it can be divided into two good strings.
So after this question is judged to be 1, to put it bluntly, it is to judge whether a string can be decomposed into k (k>=2) strings a connected together. There is a similar question on POJ, which can be solved directly by kmp. If both the before and after are satisfied, the number of methods will be +1. That 1e9+7 is just bluffing. . .
This question is also very interesting (it is really a lot of fun for mentally retarded children…)