Solution Set #3-526互联

紧急更新。

上 OI-transit 上加训构造，感觉 OI-transit 是很好的找题网站。

25 loj6736. 「2020 集训队论文」最小连通块

应该加个部分分：DFS 序是 \(1\sim n\)。

你考虑这个部分分怎么做。一种做法是剥叶子，每次找到一个叶子的父亲。存在判断一个点是否是另一个点祖先的方法：询问 \((\{1,v\},u)\)，如果返回 true 的话说明 \(u\) 是 \(v\) 的祖先。但是因为祖先比较多，所以不好判定是否是父亲。考虑换一种思路，每次对一个点找到它的所有儿子，然后把它的所有儿子剥去。这样子假如满足上面的条件就一定满足 \(v\) 是 \(u\) 的儿子。考虑这个怎么做，可以把后缀还没有找到父亲的点的集合找出来，在上面二分，直到不存在儿子为止。

回到原题，考虑找到树的一个拓扑序，然后在拓扑序上跑上面的算法。给出构造拓扑序的算法：按照任意顺序加入点，每次二分找到最长的前缀使得前缀中没有当前点的儿子，然后把这个点插入这个位置。

总操作次数 \(2n\log n\)。

提交记录 #1948376 - LibreOJ (loj.ac)

26 uoj569【IOI2020】Stations

暴力传 DFS 序的 \([in_i,out_i]\) 可以做到 \(k\leq n^2\)。

考虑一下为什么只传 \(in_i\) 会出问题，原因在于我们不知道 \(in_v\) 最大的儿子 \(v\) 的 \(out_v\) 是多少。但是注意到 \(out_v=out_u\)，所以可以这样构造：黑白染色，白色记录 \(in_i\)，黑色记录 \(out_i\)。但是 \(out_i\) 会重复，所以每次做的时候 \(+1\) 就可以了。

我在写上面这个做法的时候写错了个地方：在求 DFS 序记录 \(cnt\) 的时候，只在赋标号的时候增加 \(cnt\)，然后就会做了。注意到它实际上是满足 DFS 序的所有性质的。

提交记录 #667160 - Universal Online Judge (uoj.ac)

27 loj3366「IOI2020」嘉年华奖券

题意可以转化成：有 \(k\) 轮，每轮选择 \(n/2\) 个数，使得符号为正；选择 \(n/2\) 个数，使得符号位负。最大化其代数和。

尝试枚举每个颜色符号为正的次数，设为 \(x_i\)，则判定是否有解的问题可以看作这样一个模型：

判断是否存在二分图，使得左部有 \(k\) 个点，每个点度数为 \(n/2\)；有部有 \(n\) 个点，每个点度数为 \(x_i\)。

根据经典的 Gale-Ryser 定理，其等价于按 \(x_i\) 从大到小排序后，满足 \(\sum_{i=1}^j x_i\leq k\min(j,n/2)\)。

看起来比较麻烦，但是实际上可以观察到其等价于 \(x_i\leq k\)，证明是显然的。所以直接嗯排序然后嗯贪就行了。

提交记录 #1948658 - LibreOJ (loj.ac)

我做的时候 Gale-Ryser 写的是 \(\sum \min(x_i,j)\geq \frac{jn}{2}\)，啥都没看出来。

28 loj3365. 「IOI2020」连接擎天树

简单题。

手玩一下发现构造不出来 \(3\)，先判掉 \(3\)。然后有 \(2\) 的一定是基环树。那么合法的充要条件是：

\([p_{i,j}=1]\) 满足传递性。
\([p_{i,j}\neq 0]\) 满足传递性。

判完之后先把 \(p_{i,j}=1\) 连成树，然后构造 \(p_{i,j}=2\) 的环。实现方法是把两个连通块的环合并起来，每次维护环内的一条边即可。

提交记录 #1948774 - LibreOJ (loj.ac)

29 CF1392E Omkar and Duck

挺有意思的。

题意是让你构造一个矩阵，使得起点到终点的所有格路上的数的权值和互不相同，多次询问，每次需要找到对应路径。

暴力的做法是把第 \(i\) 步到达的格子映射到一个数上。这样做的问题是，一个数对应的路径未必满足第 \(i\) 步和第 \(i+1\) 步相邻。而题目的性质告诉我们一个格子的后继一定在下一条副对角线上的一排格子里面相邻。不妨利用奇偶性进行构造。对于第 \(i\) 条副对角线，\(x\) 为奇数的 \((x,y)\) 赋值为 \(2^{x+y}\)，其余为 \(0\)，这样可以唯一确定后继。

Submission #236164644 - Codeforces

30 CF1368F Lamps on a Circle

做了好久啊啊啊。

先随便构造一下。存在 \(n/2+\mathcal{O}(1)\) 的构造：每次往偶数位置放一个数，然后只能删掉一个。

发现没必要以 \(2\) 为分母。换成 \(k\) 可以得到一个构造：每次跳过模 \(k\) 余 \(1\) 的位置，然后放 \(k-1\) 个。这样每次操作，灯的数量都增加恰好 \(1\)。考虑这么做的上界，有 \(\lceil\frac{n}{k}\rceil\) 个位置被禁止，最后一次会删掉 \(k-1\) 个，所以答案是 \(n-\lceil\frac{n}{k}\rceil-(k-1)\)。

考虑这么做的最优性。其实很容易分析，考虑最后一次操作之后最多剩下多少个数，注意到最后一次操作必然增加灯的数量，所以不会存在连续 \(k\) 个亮着的灯，所以可以证明构造达到上界。

Submission #236196080 - Codeforces

31 CF1368E Ski Accidents

奇怪题，仍然做了好久。

考虑利用出度很小的性质构造。乱想一下可以得到一个 \(\frac{2}{3}n\) 的构造：如果一个点有入度，那么把它的两个后继删了，这样我们用 \(2\) 个点解决了 \(3\) 个点的问题。实际实现的话可以按照拓扑序删点。

考虑精细分析一下这个事情。注意到我们上面分析上界忽略了”点有入度“的条件，不妨把它的前驱找出来，显然这个点入度为 \(0\)。所以对于上面三个点构成的子结构，我们必须要找到作为前驱的第四个点。而第四个点出度最多为 \(2\)，所以作为前驱的点最多带两个三个点的子结构。所以可以看成一个七个点的独立结构，我们用删除四个点的代价解决了它。所以上述算法可以分析到 \(\frac{4}{7}n\) 的上界。

Submission #236203946 - Codeforces

32 CF1205F Beauty of a Permutation

析合树题。

整体的思路是归纳构造。考虑 \((n,m)\) 析合树上根节点的所有儿子。假设初始我们只有一个合点 / 析点以及它的所有儿子，需要把它的儿子替换成一个排列，使得这些排列的和为 \(m-\frac{deg(deg-1)}{2}\) 或者 \(m-1\)。

不好构造，但是可以调整一下：如果某个点有大于 \(1\) 个非叶子儿子，那么把这个儿子接到任意一个叶子上面仍然合法。所以我们递归到了一个子问题。

于是可以 DP 判断合法性，每次把一个叶子替换成一个析点或一个合点。构造的时候递归下去构造，注意要保证构造的点一定是本原连续段。yhx 给出的构造是：对于合点，递归下去，然后把值为 \(x\) 的点改成 \(m-x+1\)，这样可以保证后面的点不能形成连续段。对于析点，将儿子看成 \(2\)，然后构造一个 \(m=n+1\) 的排列即可。

Submission #236297344 - Codeforces

参考了 OI-transit 里面的实现。

33 CF1329D Dreamoon Likes Strings

编了好久细节。

首先如果我们把 \(s_{i}=s_{i+1}\) 的位置中间加一条分割线，那么分割线会把序列分成 \(cnt\) 段。注意到一次操作最多会减少 \(2\) 段，所以可以算出一个下界 \(\lceil\frac{cnt}{2}\rceil\)。

容易发现每次只会操作一整个连续段，调整可以证明。我们希望每次尽量减少 \(2\) 个连续段，假设连续段头是 \(x\)，段尾是 \(y\)，那么减少两段的充要条件是 \(x\neq 1\land y\neq n\land s_x\neq s_y\)。

不妨观察如果我们不能减少 \(2\) 之后的连续段情况，显然段首段尾是 \((x,y),(y,y),\cdots(y,y),(y,z)\) 的心态，这样不管怎么操作都不能减少 \(2\)，所以操作可以划分为两个阶段，我们的目标是让 \(y\) 的个数尽量少。所以有一个想法：枚举最后的 \(y\)，如果一次操作能够删去 \(y\) 就尽量删去。

直觉上这东西是有更好的构造的。稍微思考一下就可以发现第一阶段的操作相当于在一个序列中，如果相邻两个字符不一样就可以把它删去，问最后最少剩多少。这是经典问题，考虑绝对众数就可以了。

实际实现的话可以每次找到最多的字符，然后找到一个相邻的不一样的字符。我写的是 \(\mathcal{O}(n|\Sigma|+n\log n)\) 的。

Submission #236317001 - Codeforces