CF 一句话题解。

已更新：CF1695，CF1700，CF1699。

CF1695 一句话题解#

• CF1695A 考虑最大数的位置，那么答案一定是它左上左下右上右下的四个矩形中面积最大的那个。
• CF1695B 如果石子的堆数 是奇数，那么 Joe 在第 轮会第一次将要之前被取过的石子堆中取走石子，而这堆石子恰巧是被 Mike 取走过一次的，因此 Mike 必胜。否则两人要取石子的石子堆是不交的，直接考虑即可。
• CF1695C 可以发现从 到任何一个点的距离，忽略最后一个二进制位的话是一个区间。那么直接预处理 到所有点距离的最大最小值即可。
• CF1695D1/D2 可以发现一个结论：一个点集 能确定树上的所有点，当且仅当对于任意一个度数不小于 的点，如果把它当做根，只有一个其的子树中不存在 中的点。有一个直接推论：被选取的点子有可能是叶子。那么直接找一个度数不小于 的点开始 dfs 计算答案即可。
• CF1695E 观察合法的构造中不同的矩形中相同的两个连通块，可以发现成这种形式：，其中红线代表第一个矩形中由同一个多米诺骨牌覆盖的格子，蓝线则代表第二个矩形中的。将骨牌看做联系两个数字的边，那么一个连通块可以看做是一条经过每条边两次的路径，路径上奇偶交错的边被分别分到第一个矩形和第二个矩形中。那么直接在 dfs 树上欧拉遍历，经过返祖边的时候立刻走一个来回即可。

CF1700 一句话题解#

• CF1700A 这个最短路肯定是先一路向右再拐一下向下。
• CF1700B 假设原数是 位数。如果最高位不是 就拿 减去原数，否则拿 减去原数。
• CF1700C 考虑差分数组，直接模拟即可。
• CF1700D 显然开启尽量前面的 pipe 比较优，然后给询问排序直接从大到小扫一遍即可。
• CF1700E 考虑一个格子如果周围 4 格没有比它小的数，称之为坏的。如果一个矩阵合法，那么必然没有坏的格子。一次交换最多让 5 个格子从不合法变成合法，所以如果不合法的格子有 个或更多则答案是 。否则考虑任意一个格子和它周围 4 格的数和矩阵中的另外哪个数交换，这样的交换方案数是 的，然后一次交换最多影响被交换的格子上的数，和与被交换的两个格子相邻的数，这些数的个数是很少的，可以直接统计。
• CF1700F 考虑到如果有这样的形式，那么一定不是最优的：，其中黑色的 1 代表原矩阵中的 1，红色的 1 代表目标矩阵中的 1。我们显然可以让两个黑 1 均变换所在横行来得到一个更小的解。于是考虑每行的每个前缀中原矩阵的 1 的个数减去目标矩阵中 1 的个数，如果在某个前缀位置上是一正一负，那么调整成同号一定更优。

CF1699 一句话题解#

• CF1699A 考察到三个数两两异或和的和必定是偶数(令 , 的奇偶性就是 的奇偶性)，故 是奇数时无解， 是偶数时的情况时易于构造的。
• CF1699B 小王说观察样例可得构造。笔者没有写这题。摆烂了。
• CF1699C 考虑从小到大加数，维护覆盖当前已加入所有数的区间，容易发现新加数时，如果数在区间内则该数可以在区间内随意取值，区间无变化。否则该数必不能移动，区间有唯一变化。所以区间在任何时刻都是唯一的，直接维护即可。
• CF1699D 考虑记 为以 结尾最多剩多少数，转移时考虑删除一个区间即可。一个区间能被删除当且仅当区间长度是偶数且区间内众数出现次数不多于区间长度的一半。
• CF1699E 枚举分拆后的最小值，考虑每个数在分拆为不小于这个最小值的数，分拆出的最大值的最小值，这些最小值的最大值减去所枚举的最小值即为答案。