CF1844A

题意

组数据，每组给定两个整数 ，两个人从一个石堆中轮流取石子，每次恰好取 个或者  个，不能完成取石子者输。要求构造一个后手必胜的石堆  ，要求  ，输出石堆的石子数。

数据范围： 。

题解

我写了一个挺烦的做法：

如果输入为  ，输出  。

如果输入为  ，输出  。

否则输出  ，因为先手不能取式子，后手胜。

实际上只要输出  即可。

代码

CF1844B

题意

 组数据，每组给定一个正整数  ，要求构造一个  的排列，使得子区间  为素数的子区间个数最多。

 。

题解

 不是素数，所以要有贡献，区间至少包含  。不妨考虑把  放在序列中间。

然后观察到，如果一个区间不是素数，它要么不包含  ，要么至少同时包含  ，所以把  放在区间两端，符合第二种条件的区间只有一个（全局）。（本质是根据 mex 大小分类讨论）

代码

CF1844C

题意

 组数据，每组数据给定一个长度为  的数组 ，规定操作为：选中一个位置  ，移去  ，若  ，移去  和  ，并在原位置插入  ，求若干次操作之后只剩下一个数时，剩下的数最大能是多少。

数据范围： 。

题解

性质1：选中任意奇数长度的子区间，可以在不影响其它位置的情况下全部删除。

性质2：直接删除端点若干次，可以不影响其它位置的情况下删掉一个前缀，后缀同理。

性质3：间隔一个奇数长度的子区间的两个数可以合成一个数。

性质4：考虑在删掉一个前缀和一个后缀之后，从左起选择若干个数，选择的相邻两个数之间间隔一个长度为奇数的子区间，则这个选出来的子序列可以最终合成一个数。

根据性质4，可以使用动态规划思想求一个子序列，满足任意相邻两个数间隔一个奇数长度的子区间，求子序列和的最大值。

设  为选择了  的前缀的最大和的子序列大小（间隔满足奇数），枚举上一个选的数，有转移方程：

由于取的只是最值，在递推过程中，对于奇数序列和偶数序列，可以分别只保存一个历史最值进行递推。

单组数据时间复杂度  ，空间复杂度  。

代码

CF1844D

题意

 组数据，每组给定一个正整数  ，要求构造一个字典为全体小写字母集合的字符串，满足：按照顺序重排到任意  的矩阵（）中后，矩阵中四相邻的元素不相等。

数据范围：  。

题解

考虑  的所有约数  ，对每个位置  有约束：

暴力求  的约数集合（），从左往右考虑每个位置  ，考虑所有约数  ，排除所有位置  已经填放的字母，任取一个剩下的字母（不妨取最小）填充当前位置  。

由于  的约数个数是  的，这个值在  时期望远小于字典大小  ，所以这个填法是正确的。

单组复杂度  。

代码

CF1844E

题意

 组数据，给定一个  的矩阵赋值 A, B, C 三种字母，并给定  条限制，每条形如”对某个  的子矩阵，主对角线元素相同“或者”对某个  的子矩阵，副对角线元素相同“，求是否有符合条件的赋值方式。

数据范围： 。

题解

性质：将每个  的小矩形的情况拼成一个  的矩阵（以中心为参考），设主对角线相等为  ，副对角线相等为  。考虑原矩阵中任意一个相邻的  的子矩阵中四个  的子矩阵的情况：其中有偶数个  和偶数个  。也就是新矩形中任意一个  的子矩阵中有偶数个  和偶数个  ，也就是要么全都相等，要么有两个  和两个 。

推论1：在新矩形中，任意一个子矩形的四个角的值有偶数个  和偶数个  。

这个性质和原推论等价。

证明：可以对新矩阵中的以  的子矩形为单位进行数学归纳。

推论2：在新矩形中，任意两行要么对应列全相等，要么对应列全相反。

这个性质和原推论等价。

证明：

首先证明相邻两行的情况。任取一列，若它们相等：取其相邻列，必然相等。可以拓展到整行。

相邻两行要么全相等要么全相反，这是一种等价关系，可以向整个矩阵传递。

根据推论2，我们知道，所有行可以分为两类，类内两行对应列全相等，两类各区一行对应列全相反。

给定的约束其实就是规定了新矩形中某个位置必须填  或者某个位置必须填  。那么对于同一列来说，若干个已经填了的位置，其实约束了某两行属于同类或者不属于同类。

那么可以用扩展域并查集来处理这些约束，看看结果是否矛盾。

代码

CF1844F1F2

这两天被组里赶着读论文，晚点再来补题。