第十二届成都信息工程大学ACM程序设计竞赛题解

A. 欢迎来到算法竞赛的世界！

签到题，直接写即可。

fun fact：题目背景并非虚构，希望大家以后做题能够一发即过，永远不吃罚时。

I. 你是人类吗？

按题意模拟即可。

一种实现方法是，我可以枚举 $(n \times x) \times (m \times x)$ 个像素格，判断其在哪一个单元格中。如果以 $0$ 作起始下标，那么第 $(i,j)$ 个像素格就属于第 $(\lfloor \frac{i}{x} \rfloor, \lfloor \frac{j}{x} \rfloor)$ 个单元格。开一个二维数组进行记录即可。

时间复杂度 $O(nmx^2)$

L. 平衡串

我们记 $01$ 子序列个数为 $c_{01}$ ， $10$ 子序列个数为 $c_{10}$ 。

对于一次交换：

$01 \to 10$ ，则 $c_{01}$ 减一， $c_{10}$ 加一；
$10 \to 01$ ，则 $c_{10}$ 减一， $c_{01}$ 加一。

所以我们只需要统计原串的 $c_{01}$ 与 $c_{10}$ ，答案即为 $\frac{|c_{01} - c_{10}|}{2}$ 。

无解的情况显然是 $|c_{01} - c_{10}|$ 为奇数的情况。

D. 平方序列

构造方法不唯一，std 的构造方法是：

对于前 $m$ 个数： $a_i = i \times 2 - 1$ 。
否则： $a_i = a_{i-k} + i \times 2 - 1$ 。

前 $m$ 个数的和显然为平方数，后者的构造在于 $x^2 - (x-1)^2 = 2x - 1$ 的观察，维持了和为平方数的性质。

这个序列显然是严格递增的，因为每一项都为正且增加了一个 $i \times 2 - 1$ 。

时间复杂度 $O(n)$ 。

J. 分隔

这道题的题解其实一句话就能说完：求一条由最左侧走到最右侧的最短路即可。

赛时，大部分的选手认为从最左侧到最右侧是不能走“回头路”的，于是使用了 $dp$ 解法，这显然是不正确的，其实是可能出现需要“回头”的情况的，例如存在一条“回头”路径上所有点的权值都为 $0$ ，其他点权值都为无穷大。

这道题同样可以用网络流中的最小割求解，但是最小割的时间复杂度太大，无法通过本题。

建立八方无向图（即八个邻侧方向都可以走），用 dijkstra 算法跑最短路即可。

时间复杂度 $O((n\times m)\log(n\times m))$ 。

E. 迷宫制造者

我们先把迷宫中所有不存在墙的位置建墙，把开销记录进答案里。

然后，把迷宫看成一个图，仔细观察题目给出的信息，显然就变成了求最小生成树，被选择的边代表把这堵墙给拆除。

边权的赋值是需要注意的：如果我们拆除墙的位置原来本来就存在墙，那么边权即为其施工开销 $w$ ；如果本来不存在，那么边权应该为其边权开销的相反数 $-w$ ，因为我们是把这堵墙建立起来统计进答案中再拆的，显然一开始就不建立是优的，所以要把这部分开销扣去。

使用 Kruskal 求最小生成树即可。

时间复杂度 $O((n\times m)\log(n\times m))$ 。

F. 我们之间的相交线

对于本题，一种比较好的处理方法是把 $u_1$ 设为根，先按顺序找到给出路径 $(u_1,v_1)$ 上的所有点，找到的序列记为 $path$ 序列， $(u_1,v_1)$ 的长度另外记作 $\text{len}$ 。

然后，我们可以把 $path$ 序列的点在原树中删去，然后找到 $path$ 上每个点可以抵达的最深的长度，对于点 $u$ ，我们把该值记为 $d_u$ 。以上操作均可以在一遍 dfs 内完成。

然后，我们在 $path$ 序列上作一个长度为 $k$ 的“滑动窗口”操作，取窗口上左右两侧端点 $x,y$ ，只需要找到一个窗口，满足 $d_x > 0, d_y > 0, d_x + d_y \ge \text{len}-k$ ，那么就存在一个解。如果找到最后都没找到合法解即为无解。

找到解后，顺着向下找到对应的点即可，可以在 dfs 时处理出每个点的 $\text{nxt}$ 点，这样找答案时会更简单一些。

可以看出，这道题目的思路比较简单，难点在于实现，需要比较精细的处理。

时间复杂度 $O(n)$ 。

B. 小游戏 III

首先有一个显然的结论：如果一个人走到 $0$ ，那么另一个人一定会输。那么当一个人操作时，如果能使 $x$ 变为 $0$ ，那么其一定会将 $x$ 变为 $0$ 。

什么时候 $x$ 能够变成 $0$ 呢？答案是 $\gcd(x,n) \neq 1$ 的时候，也就是 $x$ 与 $n$ 不互质的时候，这个时候只需要取 $y=\frac{n}{\gcd(x,n)}$ 即可。

那么一个人操作时，如果当前 $\gcd(x,n)=1$ ，这个人就只能选取与 $n$ 互质的数 $y$ 。因为一旦选取的数 $y$ 与 $n$ 不互质，那么新的 $x$ 一定有 $\gcd(x,n) \neq 1$ ，这相当于送对方胜利。

所以能选取的 $y$ 一定是与 $n$ 互质的数，相对的，每选取一个与 $n$ 互质的 $y$ ，就会消耗一个与 $n$ 互质的 $x$ 。可以证明的是，所有与 $n$ 互质的 $x$ 都能取到，谁先把与 $n$ 互质的数消耗完，那么谁就赢了。

所以我们只需要找到不在 $S$ 中且与 $n$ 互质的数的个数，判断其奇偶即可。

时间复杂度 $O(n\log n)$ ， $\log n$ 来源于求 $\gcd$ 。

G. Satori and Koishi's game

区间乘积大于 $1e9$ 就不统计是一个很好的性质，如果一个区间里的乘积不大于 $1e9$ ，那么该区间内非 $1$ 数的个数不会超过 $\log1e9$ 个。

由于数字 $0$ 会让区间乘积直接变成 $0$ ，所以我们把序列按 $0$ 断开。然后把 $1$ 压缩，实际实现上可以求出每个非 $1$ 数的 $\text{nxt}$ 与 $\text{pre}$ ，也就是下一个/上一个非 $1$ 数的位置，跳跃地访问。

我们采用离线的方式统计答案，即先求出 $\text{len}:[1,n]$ 的所有答案，再 $O(1)$ 回答每个询问。

在只关注非 $1$ 数的情况下，我们可以暴力的检查长度为 $1 \sim \log 1e9$ 的所有区间，对于一个区间 $[l,r]$ ，其对答案有贡献的区间是 $\text{len}:[r-l+1,nxt_r-pre_l-1]$ ，我们只需要对有贡献的区间取 $\min$ 即可。这个部分可以用线段树大力做，但因为是在做完所有操作后询问答案，所以也可以把每个贡献区间记录下来，最后统一做一个“线段覆盖”类问题。

由于产生贡献的区间个数有 $n\log V$ 个，所以总复杂度为 $O(n \log n \log V)$ 。

H. XOR and SUM

我们可以把每一个二进制位分开来看，这样序列与操作就都变成了 $01$ 序列与翻转操作。

直接去用原序列计算某个子数组的价值是比较困难的，我们可以直接对序列做一个前缀异或，接下来对这个新的前缀序列进行操作与计算。

考虑一个操作，把某一个区间的数全部异或上 $1$ ，那么对于前缀序列，体现的是在这个区间的奇数位被翻转，偶数位不被翻转。特别地：如果区间长度为奇数，那么这个操作区间后的所有位置都需要被翻转。

考虑一个询问，我们只需要记录询问区间内 $0,1$ 的个数 $c_0,c_1$ 。对于询问区间 $[l,r]$ ，如果 $l-1$ 的位置是 $1$ ，则需要翻转一下 $0,1$ 的个数。若记录的是第 $i$ 位，产生的价值即为 $c_1 \times 2^i$ 。

上述操作对每个位都开一个线段树维护即可。

时间复杂度 $O(q \log n \log A)$ 。

C. 你是奶龙？你是奈龙！

我们可以建出主串的 border 树，树上的每个结点代表一个字符串，实际上求出来的是一个森林。

那么，对于当前的串，我们只关心最后一次添加的点到树根的这条链，该链上的结点对应的字符串首先一定是主串 $S$ 的前缀与后缀，这些串的区别在于在主串 $S$ 中出现了多少次。

那么一个结点 $t$ 对应的串 $T$ 在主串 $S$ 中出现了多少次呢？这个出现的次数实际上是子树 $t$ 的大小。

所以我们在不考虑操作 1（即添加操作）的时候，对于 k-绚丽子串的询问，只需要在树上做一个倍增即可，去找深度最大的且子树大等于 $k$ 的位置所对应的串，找深度最大的原因是，border 树的一条链上，其深度越大，字符串长度越长。

现在考虑上操作 1，正向地去做是很困难的，因为每次添加一个点都需要对维护该点的倍增数组，所以我们可以离线所有操作，倒过来去做。先建出所有操作后最终的 border 树，然后倒过来遍历每个操作，每遇到一个操作 1 就删掉相对应的点，这样就保证了正确性与时间复杂度。类似的技巧在 Codeforces Round 907 F Growing Tree 中也有体现。

时间复杂度 $O((n+q)\log (n+q))$ 。

赛时选手和验题人中也有大手子直接写的 SAM 在线处理操作，

可惜我不会。

K. 树上转移

这题本来有一个序列的版本，转移只能从左转移到右边，我们可以先考虑序列版本怎么做。

为了使方差最小，从数学的意义上来看，实际上是把数字分配地更加“均匀”。

对于一个序列，我们可以开一个单调栈维护。栈中维护两个信息 $(s,l)$ ，代表总和与包含的数字个数。最开始，我们依次取出序列中的数 $a_i$ ，初始信息为 $(a_i,1)$ ，然后考虑能否与栈顶信息合并。记栈顶信息为 $(S, L)$ ，如果 $\frac{S}{L} > \frac{s}{l}$ ，代表我栈顶的元素向该序列的数进行转移是更优的，因为这样能使数字更加平均，于是我们就可以把栈顶的信息合并进初始信息，即 $(s,l) \to (S+s, L+l)$ 。