AtCoder Regular Contest 060

这一期的Regular Contest我也是肥肠喜欢啊,题目都很好玩啊,题目链接

代码链接

C Tak and Cards


C题题意是给出N(N<=50)个数,每个数的范围在1到50之间,然后给一个值A。从这N个数任意选择数字,要求选取的这些数字的平均值是A,问有多少种选取的方法。

dp[i][j][x]表示到第i个数时,有j个数组成和为x的方法数量。

D Digit Sum


D题题意是给出了一种函数f(b,n),
$$
f(b,n)=n \ \ \ \ when\ \ n<b
$$

$$
f(b,n)=f(b,floor(\frac{n}{b}))+(n\%b)
$$

然后给出了n和s,求是最小的b,使得f(b,n)=s。如果不存在这样的b,输出-1。

下次看到n,b范围在10^11,10^12这种题,直接考虑O(sqrt(n))啊啊啊。

首先考虑b<sqrt(n)的这种情况,直接暴力算。

然后考虑b>sqrt(n),那这样n=pb+q,有p+q=s。得到n-s=b*(p-1)因为b>sqrt(n),所以p是小于sqrt(n)的,枚举p,注意q也要符合条件即可。

E Tak and Hotels


E题题意是给出了n个旅馆的坐标,然后有一个人旅行一天的时间行走的距离不超过L,晚上必须在旅馆睡。然后有Q个询问,问从a走到b至少需要几天,保证是可以到达的。

倍增的想法,dp[x][a]表示从x经过2^a天能够达到的最远旅馆,之后每次询问从最高次往低次暴力。

F Best Representation


发现AtCoder日本人很喜欢出这种题,关于这种是哪种我也说不太好

字符串X如果能够被表示成k(k>=2)个字符串a连接而成的话,就不是好字符串,否则就是好字符串。

现给出一个字符串,要求把这个字符串分解成都是好字符串的字符串。。。问在所有分解成功的集合中,分解出来的最少的字符串数量是多少,设为ans,有多少种分法,使得最少字符串数量为ans,输出ans和这个多少种分法。= =。突然发现我语言能力如此捉急,看不懂的看英文吧,当然我觉得那个也挺难懂的。

这个题就好玩在,排除所有字符相等的情况(这种情况输出的是strlen(w),1,不用多说),分解出来的最少字符串数量一定不是1就是2。当这个字符串本身就是好字符串的时候就是1。当这个字符串可以表示成k(k>=2)个字符串a连接而成的话,那么此时,嘿嘿嘿(……),一拆的话,前者多一个,后者少一个,就可以分成两个好字符串啦。

所以这个题判断出是1的情况之后,说白了就是判断一个字符串可不可以分解成由k(k>=2)个字符串a连接而成,POJ上面有一道类似的题目,kmp直接可以解,前后如果都满足,方法的数量就+1。那个1e9+7纯属唬人。。。

这个题目也挺好玩(真是智障儿童欢乐多。。。)