CF Round970 D3 A-F

• 这场更像是D4，所以明天之前会把 G、H 补上。

A

• 答案完全取决于 a 和 b 的奇偶性，做个特判就好。

B

• 开始读题没有注意到那个 square，多费了一些功夫。可以在确定 n 是平方数后构造出对应的字符串，然后与给定的字符串比较即可，因为一旦 n 确定，合法的字符串就是唯一的。

C

• 注意到当 l 和 r 为最大值时对应的答案也才到 4e4，这启发我们可以直接进行暴力求解，从 l 开始，每次将 d 加一即可。

D

• 感觉 D 要比 E 和 F 更有学习意义，我们发现每次执行i = p[i]这个操作，假使我们将 1 到 n 看作一系列节点，那么 i 与 p[i] 之间就有连边，此时发现整张图其实是由一些环组成的（包括自环），我们只需要对所有点进行遍历，如果它没在某个环中（也就是fa[i] == i），就进入 dfs 找环（这其中有记忆化的思想），环的根就是入口节点。当我们把所有环找出来之后，每个节点最多能到的黑色整数个数就是它所在环的黑色整数个数。

E

• 难点其实在于删数的部分，删完之后的计算非常简单。我们可以开一个前缀和数组，用来记录每个字母出现的次数。之后直接对整个数组进行遍历，算出删掉当前字母后的最终答案，最后对这个最终答案取最值就可以。

F

• 看完样例后就能做出来了，只能说样例解释真是个好东西，读题难度远大于做题，不过开始好像取模有点问题，交了几个 wa 之后开了 int128 才过。