AtCoder Regular Contest 061

题目链接代码链接

C Many Formulas


题意是给出了由1到9组成的一个字符串,字符串长度最多是10,你可以在字符串中间添加+号,算所有方案得到的数的总和。

因为长度最多只有10,直接暴力算。

D Snuke’s Coloring


题意是给出H*W的格子,在上面不是黑点就是白点,现在给出N个(0<=N<=min(10^5,H*W))黑点的位置,算3*3的格子内,有0到9的黑点的格子分别有多少个。

对每一个黑点,将其被算入的3*3的格子都+1,对于3*3的格子直接计算左上角的那个格子被覆盖的数量。

E Snuke’s Subway Trip


给出了N个车站,M条地铁线,每一条地铁线由相关公司建造,如果在乘坐地铁的过程中,切换了地铁线所在的公司,那么费用+1。计算从车站1到车站N的最小费用。

优先队列+宽搜,记录当前到达该车站的最小费用以及所乘坐的车,这样就能够判断下一次走的时候费用是否+1了。

F Card Game for Three


题意是一张牌上面有a、b、c三个字母中的一个,A有N张这样的牌,B有M张,C有K张。现在他们没事了,然后又开始做游戏了。。。

由A开始翻牌,翻自己所含有的最上面的牌,如果是a,则A继续翻牌;如果是b,则轮到B翻牌;C同理。

如果轮到自己的时候发现自己没有牌了,则这个人获胜。

现在给出N、M、K,问A获胜有多少种。

Codeforces上的讨论

这个题不要去考虑有三柱牌,直接考虑最终获胜的时候的序列。就拿讨论里面的例子举例,如果N=5,M=4,K=6,那么A获胜的时候序列一定是先出现了5个a,出现b的次数小于等于4,出现c的次数小于等于6。当前翻过的牌数位x,后面的牌任意选,即3^(N+M+K-x)。

那么对于前面翻过的这些牌来说,方案数就是
$$
ans={\begin{pmatrix}
n+x-1\\
n-1
\end{pmatrix}}*fs(x)
\\
fs(x)=\sum_{i+j=x,i<=m,j<=k}{\begin{pmatrix}
x\\
i
\end{pmatrix}}
$$

现在来求fs(x),fs(x)找规律。。。。。。。。。。。。

画一下杨辉三角的图,发现就是fs(x+1)与2*fs(x)相差不多,如果加多了的话只需减掉前面的C(x,m)或者C(x,k)就能够递推了。