第十八届同济大学程序设计竞赛暨高校网络友谊赛题解

A. 自适应树游走协议

简单题。

复杂度 $O(n)$。

B. 简单的数学题

先做基本变换：

$\begin{aligned} & \sum\limits_{i=1}^n \sum\limits_{j=1} ^ i \lceil\frac{i}{j}\rceil[\operatorname{gcd}(i,j) = 1] \\ =& \sum\limits_{i=1}^n \sum\limits_{j=1} ^ i \lceil\frac{i}{j}\rceil\sum\limits_{g|gcd(i,j)} \mu(g) \\ =& \sum\limits_{g=1}^n \mu(g)\sum\limits_{i=1}^n [g|i]\sum\limits_{j=1} ^ i[g|j] \lceil\frac{i}{j}\rceil \\ =& \sum\limits_{g=1}^n \mu(g)\sum\limits_{i=1}^{n / g}\sum\limits_{j=1} ^i\lceil\frac{gi}{gj}\rceil \\ =& \sum\limits_{g=1}^n \mu(g)\sum\limits_{i=1}^{n / g}\sum\limits_{j=1} ^i\lceil\frac{i}{j}\rceil \end{aligned}$

后面的求和式仅跟 n 有关。

令 $S(n) = \sum\limits_{i=1}^{n }\sum\limits_{j=1} ^i\lceil\frac{i}{j}\rceil$ ，实际上只需要 $S(n / i)$ 的值，而 $n / i$ 的个数为 $O(\sqrt{n})$ 。

考虑快速单点求值：

发现其为二重求和式，即枚举的是下三角的点对 $(i,j)$ ，因此往合并贡献的方向去思考。

当 $\lceil \frac{i}{j} \rceil$ 小于等于 $\sqrt{n}$ ，枚举上界 $w$ ，计算 $\lceil \frac{i}{j} \rceil \leq w$ 的点对个数。

$\begin{aligned} &\lceil \frac{i}{j} \rceil \leq w \\ \Rightarrow & i \leq wj \\ \Rightarrow & \lceil \frac{i}{w} \rceil \leq j \end{aligned}$

即 $\lceil \frac{i}{j} \rceil\leq w$ 的 $(i,j)$ 个数为 $\sum\limits_{i=1}^n i - \lceil \frac{i}{w} \rceil + 1$ （官方题解给的式子有误）。这个明显可以 $O(1)$ 求得。 建议自己封装向下取整，向上取整变动上指标的前缀和函数 ，省很多事。

那么等于 $w$ 的个数即为前缀和做差。

枚举 $w$ 的复杂度为 $O(\sqrt{n})$ 。

当 $\lceil \frac{i}{j} \rceil$ 大于 $\sqrt{n}$ ，意味 $j \leq \sqrt{n}$ ，此时枚举 $j$ （practical 的建议是， j 枚举到 $\lceil \frac{n}{j} \rceil \leq \sqrt{n}$ 停止，避免细节处理）

$\begin{aligned} &\sum\limits_{j=1}^{\sqrt{n}+5}[\lceil \frac{n}{j} \rceil>\sqrt{n}]\sum\limits_{i = j*\sqrt{n}+1}^n\lceil{\frac{i}{j}}\rceil \\ \end{aligned}$

同样也是前缀和做差。

复杂度 $O(\sqrt{n})$ 。

很明显不能在数论分块时在线求 $S(n / i)$ 的值。需要预处理一部分的 $S(i)$ 。

考虑预处理前 $n^{2 / 3}$ 的 $S$ ，计算一下后面在线计算的复杂度：

$n / i \geq n^{2 /3} \Rightarrow i \leq n^{1/3}$ ，即有 $n ^{1 / 3}$ 的点大于等于 $n^{2 / 3}$ 。

复杂度为 $O(\sum\limits_{i=1}^{n^{1/ 3}})\sqrt{n / i}$ ，用积分近似计算复杂度：

$O(\int\limits_{i=1}^{n{1/3}} \sqrt{\frac{n}{i}}) = O(n^{2 / 3}) $ 。满足要求。

因此考虑如何预处理前 $n^{2 / 3}$ 的 $S$ ：

$\begin{aligned} S(n) &= \sum\limits_{i=1}^{n }\sum\limits_{j=1} ^i\lceil\frac{i}{j}\rceil \\ &= \sum\limits_{i=1}^{n }\sum\limits_{j=1} ^i\lfloor\frac{i-1}{j}\rfloor + \frac{n*(n+1)}{2} \\ &= \sum\limits_{i=1}^{n-1}\sum\limits_{j=1} ^i\lfloor\frac{i}{j}\rfloor + \frac{n*(n+1)}{2} \end{aligned}$

前面的二重求和式可以类比杜教筛。具体的，把 $i / j$ 看做积性函数 $1$ 的前缀和。即 $\sum\limits_{j=1}^i\frac{i}{j} = \sum\limits_{j=1}^i(1 * 1)(j) = \sum\limits_{j=1}^id(j)$ 。

故 $\sum\limits_{i=1}^{n-1}\sum\limits_{j=1} ^i\lfloor\frac{i}{j}\rfloor$ 为积性函数 $d$ 的二维前缀和，可以线性递推。

那么最后数论分块就做完了。

复杂度 $O(n^{2/3})$ 。

C. 困难的数学题

递推方程 $f(i) = 1+\sum\limits_{j=k}^if(j-k)$

复杂度为 $O(n)$ 。

夹带一点私货：

这题也可用该方法做，复杂度 $M\log M$ 。需要套个 MTT 。

D. 平衡的字符串

考虑模 k 余数相同的位置，判断一下即可。

复杂度 $O(n)$ 。

E. 不平衡的字符串

由于 $a / b \geq 1 / 2$ ，而 $k$ 必须大于 $a / b$ ，故同一子串不会有不同字符同时满足条件。子串长度用 i - j + 1 表示，子串中字符的个数用 pre_i - pre_{j-1} 表示，就变成了两个点的 trivial BIT 题。

复杂度 $O(nm\log n)$ （实际根本达不到满的复杂度）。

F. 值钱的项链

水题。

G. 自行车调度

费用流裸题。

H. 三阳开泰

令 $f(i,j,k)$ 表示第 i 位二进制， a,b,c 是否到上限的状态 j ， a^b,bc,c^a 是否到上限的状态 k 的个数。

数位 dp 板题。

I. 图中修边

方案可行与否仅跟连通块有关。

deg <= 2 的特判一下。

发现大于等于 3 的完全图删不了；没有奇数度的点的连通块也会删出环来（搭边的过程，就是其中两个点的度数不变，另一个店的度数-2，故整个图的度数集合奇偶性不变）

上述两个结论是充分必要的，判一下就完事。

复杂度 $O(n+m+\alpha n)$ 。

J. 下围棋

首先原游戏由独立的子树游戏构成，子树的 SG 值异或一下就是答案。

子树的游戏可转化为有根树删一个点，该点代表的子树就删除。花几个图，可猜测一颗树的 SG 值应为子树的 SG 值异或和 + 1。

复杂度 $O(n)$ 。