【题解】牛客挑战赛 Round 79

A

本来 是另一道题的，但是疑似太简单就换了，结果赛时很多人猜/做不出来）

先说结论：当且仅当数组中只有一个 ，且这个 左右两侧的 的个数相等时， 获胜（等价的表达：数组长度为奇数，数组中央有一个 ，其余都是 ）；否则 获胜。

证明：分类讨论

若数组中有偶数个 ，那么整个数组的积为 ，先手可以一次将所有数字取走并直接获胜。

若数组中有奇数个 ：

从简单的情况入手，不妨假设数组中仅有一个 。这时 左右两侧的子数组元素均为 ，每次操作只能取走其中一个子数组的任意个 ，由此转化为仅有两堆石子的 游戏，当且仅当两侧 的个数相等时，先手必败。

再考虑数组中大于一个-1的情况。能不能转化成之前讨论过的情形呢？答案是可以。作为先手， 肯定希望自己操作过后，数组变成一个先手必败的局面（也就是数组中仅有一个 ，且 两侧 的个数相等）。以下给出一种可行的操作思路：删除原数组中部的某一段区间，保留首尾的两段。因此先统计原数组前缀和后缀 的个数，不妨记为 和 。如果 ，在数组首端保留从左数第一个 及之前的所有 ，在数组尾端保留 个 ，其余的全部删去即可。其余情况类似。因此数组中 的数量大于 且为奇数时，先手必胜。至此，分类讨论已经完备。

B

题意比较难懂。

不难发现，如果两个字符串 相同，则它们的子串也必然存在相同的子串。

因此我们可以知道不满足条件的字符串必然符合 ，当 时，则代表字符串 存在 个相同的字符。

因此我们需要构建一个相同字符相隔尽可能远的字符串。

将出现频率最多的字母作为依据，那么两字母之间相隔就为 ， 为所有字符数量， 为最多的字符的数量。

构造时每次选择剩余最多且在 长度以内不冲突的字符构建即可。

时间复杂度为 。

C

算是比较恶心的一个细节处理了，后来验题人给出了 数据，也是大部分人难以考虑到的一个点（甚至验题人大多数都没想到）。不妨考虑若符合条件的 存在，会满足什么性质。首先，区间两端的函数值应当相同。其次，由于保证了相邻线段斜率不相等，因此线段的端点 也应当具有周期性，且与函数的周期性一一对应。从这个角度出发，可以对每次询问使用 算法，也可以提前暴力预处理出 数组的各个后缀之间的 来解决这个问题。最后，需要特判询问的区间为一条线段或退化为一个点的情况，时间复杂度 。此外需要注意的是，询问区间的两端可能不满足上述周期性，要另外判断。请注意斜率小数精度问题，以及判断如下数据：

6 1
1 2 4 6 8 9
2 1 3 1 3 2
1 9

D

对于任意一点 到达相连的一点 ，我们有两种走法：

1. 走 ，此时的权值异或和为 。
2. 走 ，此时的权值异或和为 。

于是，我们可以得到一个性质：对于任意两个相邻的点 ，我们可以经过 的边的前提下，可以自由选择是否将权值异或 。

对于 个相邻的点 ，且 相连。每次选中一条边时，分为以下情况：

1. 的点都已经被之前选中，此时选择边 使之前 的状态为未选择。此时已选中点的数量 。
2. 的点都未被选中，此时选择边 使之前 的状态为已选择。此时已选中点的数量 。
3. 的其中一点被选中，此时选择边 使之前 的状态取反。此时已选中点的数量不变。

既然有这个性质，不妨我们在思考一下以下问题：

如果两点不相邻，如何做到选择指定两点？

我们可以寻找两点 的路径，选择连接两点之间所有的边。即 。

能否存在一种方案，使我能够选择树上特定几个点进行异或？

由于上文提到，我们选点的数量只能同时 或者 或者不变，所以我们要对两种情况下进行讨论：

• 当选择点的数量为偶数时：我们随意进行选边异或操作即可。
• 当选择点的数量为奇数时：我们需要先选择其中一个点，然后在进行选边异或操作。由于我们选边的时候可以不改变点的数量的前提下达到自由选择需要特定的几个点，所以我们随意选一个点作为初始值即可。

既然我们可以随意选择值进行异或了，那么我们就可以快乐地线性基了。

对于每次查询的两点 ，我们需要知道初始路径的距离为奇数还是偶数，然后再进行分类讨论，至于怎么判断，有很多种办法：例如二分图，并查集。

E1

由于每个禁止区域相互独立，互不影响，因此随机化的 不影响最终结果。

禁止位置的排列非常规则，正难则反，考虑容斥，用 表示把 个车放到棋盘上，且每个车都在禁止位置上。由容斥原理可知，最终的方案数为 。由于每个禁止区域可以放一个车或两个车，放一个车时有三种方案，放两个车时有一种方案。设有 个位置放了 个车，有 个位置放了 个车，枚举满足条件的 和 ，则 。

注意到大部分组合与幂次运算都可以进行预处理，时间复杂度为 。其中，主要的计算量在于找到满足条件的 和 ，因此想要进行优化，就要快速解出 和 ，其满足的方程组如下，解完方程组后就可以 枚举 ：

E2

设 。把 个车放到棋盘上，且每个车都在禁止位置上的方案数为 。由容斥原理可知，最终的方案数为 。令 ，，记 。

于是可以 递推求出 。边界情况为 ，。 最终答案为：

F

转化题意，求一个图中的哈密顿通路，且需要满足某种边的限制。这个问题只能通过搜索与回溯实现。因此，本题的解法显然不唯一。解决问题的关键在于如何增大搜索进入“可行解”的概率，避免过早进入“死胡同”。以下提供了一种解题思路：

先尝试判断合法解的存在性。结论是：题目所给数据范围内，解始终存在。现在考虑如何证明合法解的存在性。容易发现，一个显然的必要条件是“可供使用的斜率数量不小于 ”。那么，长度为 的棋盘中可以使用多少种斜率？这个问题可以暴力打表解决（根据数论，可以得出这个值就是 )。发现这个必要条件可以被满足。

除了上述的必要条件之外，似乎并没有其他的证明手段。那么不妨直接编写一个暴力搜索，看看 较小时解的情况：任选一个点作为起点，每次枚举尚未使用过的斜率，尝试连接到当前位置上，得到一组合法解就输出。容易发现， 时有很多组不同的解（如果尝试过手绘的话，也能发现 时的解很容易构造得出），但 时，较慢的暴搜程序可能无法在短时间内得到答案，手绘也较为困难。

因此要考虑剪枝。观察发现：跨度较大的斜率很大程度上限制了构造的方法（这里的“跨度”是指将该斜率写成有理数并约分后，分子和分母的绝对值大小）。于是可以在枚举斜率时，优先枚举跨度较大的斜率。此外，以某个特定的点作为起始点并沿着所有可能的路径搜索，很可能出现“搜索前期畅通无阻，后期处处碰壁的情况”。相比之下，采取随机化的连边方法，将所有斜率一一“放置”到点阵中，并在该过程中使用可撤销的并查集判断连边的可行性，可以提高搜索的成功率。

该搜索的理论复杂度上限是 。但采用上述两种剪枝方法后，甚至可以快速得到 时的合法解。不过，这与模拟的方式也有一定关系。你当然打表通过本题，前提是你的暴力程序能在比赛前运行出结果。