周赛75 文字版题解

写在前面

这期的周赛感觉是 难度最大的一期，验题阶段写了很久。 特别是 题，需要考虑的情况非常多，而且需要考虑的细节非常多。 其他题还是比较正常的，我写的代码有点shi，就不贴了

A.小红的正整数计数

输出 即可。

B.小红的双生串

将字符串分成两个部分，取出现次数最多的字符的出现次数，分别为 和 ，答案为 。

C.小红的双生排列

若 为奇数，只能奇数，偶数，奇数..放，所以答案为奇数个数的排列方案乘以偶数个数的排列方案。 若 为偶数，可以奇数，偶数，奇数，偶数..放，也可以偶数，奇数，偶数，奇数..放，所以答案为奇数个数的排列方案乘以偶数个数的排列方案的两倍。

D.小红的双生数

考虑答案必须为 的形式。 若 的位数为奇数，那么进位，答案必然为 的形式。 若 的位数为偶数，每两位考虑变成一个 的倍数，若能变得很前面两位不一样，且不需要进位，则直接变；若需要进位，则提前记录前面可以进位的数，后面的位数则用 的形式填充，存不存在可进位的数，也是变成 的形式。若不能变得和前面两位不一样则也需要进位，同样进位的问题和刚才的方法一致。

E.小红的双生英雄

我们需要将双生英雄两两分组，对于落单的则和自己匹配。 这样用 表示前 个匹配关系，花费为 ，当前选了 个英雄的最大战斗力。

预处理 ，然后就可以用刷表填充下一个位置。

同时考虑一对匹配关系中单只上场和双只上场的情况即可，若是自己和自己匹配的则不考虑两只都上场的情况。

F.G 小红的双生树

对于 版本，直接暴力即可。

对于 版本，会发现叶子结点只会跟父亲结点同色，那么就可以形成唯一的匹配关系。然后对树染色，发现只会染成根为红色和蓝色的两种情况。

考虑其中一棵目标染色树，只需要维护路径之外的点的修改次数+询问路径中蓝色结点的个数得到 ，然后考虑另一棵目标染色树，发现同理做即可，答案就是 。

对于上述的预处理可以用树上前缀和预处理，对于查询部分，可以使用 对路径查询进行容斥。