AtCoder Regular Contest 061
C.Many Formulas
题意
- 给长度不超过(10)且由(0)到(9)数字组成的串S。
- 可以在两数字间放(+)号。
- 求所有方案的数字和。
思路
- (2^{|S|-1})枚举加号的放置状态
代码
D.Snuke's Coloring
题意
- 在一个(H imes W(3 le H,W le 10^9))的棋盘上，有(N(N le 10^5))个格子被染成黑色，其余格子为白色。
- 求在所有(3 imes 3)的子矩形中黑色格子个数分别为(0,1,...,9)的个数。
思路
- 考虑每个黑色格子作为(3 imes 3)矩形中的其中一个格子，求对应矩形的黑色格子数。如果当前矩形的黑色格子数为(x)，则该格子会被计数(x)次。
- (0)的矩形个数由总方案减去有黑色格子的方案数。
代码
E.Snuke's Subway Trip
题意
- 一张图，有(N(N le 10^5))个点，(M(M le 2 imes 10^5))条边。
- 每条边有一种颜色(c_i)。
- 假设通过颜色(i)走到节点(u)，当(u)要走到相邻节点时，如果经过的边仍为颜色(i)，则费用为0，否则需要代价1。
- 求从节点1走到节点N的最小花费。
思路
- 假设与(u)有关的边的颜色有(x)种，则将点拆成(u_{c1}, u_{c2},...,u_{cx})个点。
- 将点(u)设置成总点，与(u_{ci})连边，费用为1。
- 假设(u)走到(v)，颜色为(C)，则(u_C)与(v)连边，费用为0；(u_C)与(v_C)连边，费用为0。
- 最后跑一遍单源最短路即可。
代码
F.Card Game for Three
题意
- Alice、Bob和Charlie分别有(N,M,K(N,M,K le 3 imes 10^5))张牌，每张牌有一个字母（a,b或c）。
- 三个人轮流出牌，牌上的数字代表下一个出牌的玩家。
- 若当前要出牌的玩家没有牌，则该玩家获胜。
- Alice先出牌，求在所有可能的方案中Alice获胜的方案数。
思路
- 出牌顺序看成一串abc的序列，第一个达到手牌上限的人获胜，假设Alice获胜，那么a出现了(N+1)次。因为Alice先手，所以第一个总是固定为a，那么去掉第一个后a出现(N)次。
- 考虑游戏结束时三个人共打出了(i)张牌，可以得到3个信息：
- 最后一张牌必然是a；
- b和c的出现次数不超过(M,K)；
- b和c不会同时超出上限。
- 先从(i-1)选(N-1)位置放a；剩下的位置放置b和c，总方案数为(2^{i-N})，考虑去掉不合法的方案，即b或c超过上限的方案数，小数据可以暴力求，对于b来说，枚举([M+1, i-N])的出现次数，c同理。对于大数据来说，假设长为(i-1)中b不合法的方案数为(fb)，那么当前多了一个填充bc的位置，这个位置可以填bc，方案仍为不合法的方案，此时b的个数大于(M+1)，还要求b的个数刚好为(M+1)的不合法方案数。
代码