题解-AtCoder Beginner Contest 242

比赛链接

所有提交记录即代码

A - T-shirt

按题意模拟即可。

B - Minimize Ordering

对字符串排序。

C - 1111gal password

简单数位dp，记 \(f_{i,j}\) 代表第 \(i\) 位是 \(j\) 的方案数。转移从 \(f_{i-1,j-1},f_{i-1,j},f_{i-1,j+1}\) 即可。

D - ABC Transform

函数递归题，容易发现每进行一次操作位置变成原来的 \(2\) 倍或 \(2\) 倍加 \(1\)，那么我们倒着做直到 \(k=1\) 时停止，不断把 \(k\) 除以 \(2\)。而 \(k=1\) 时只用考虑 \(s[1]\)。复杂度 \(O(\log{k})\)。

E - (?x?)

简单计数，可以参考数位dp的思想，枚举一段前缀顶到了最大值，下一位不到，后面 \(26\) 种字母随便填。

F - Black and White Rooks

简单容斥，考虑枚举 \(i\) 行 \(j\) 列放白子，那么白子必然放在交叉处，可以抽象成一个 \(i\times j\) 的矩形。要求每行每列都有一个，那么先随便放，然后减去某些行或某些列没有的情况。然后再在 \(n*m-i*m-j*n+i*j\) 个格子里放黑子。

G - Range Pairing Query

莫队傻逼题，精细分析复杂度是 \(O(n\sqrt{Q})\)，能冲。