【题解】五月训练日记

拼尽全力无法战胜 div2b，要重开了。(╥﹏╥)

CF2108E. Spruce Dispute

*2600 Code

考虑如何给删完点后的剩下 \(n-1\) 个点分配颜色使得答案最大。

拆贡献，对于一条边，我们肯定想让跨过这条边的路径尽可能多。换句话说，设这条边两侧的子树大小分别为 \(a,b\ (a<b)\)，我们肯定想让子树大小为 \(a\) 的一侧的点的颜色互不相同。

可以证明，从这棵树的重心开始按 dfs 序涂色最优。即按 dfs 顺序 \(1\to 2\to 3\to \ldots \to \left\lfloor\frac{n}{2}\right\rfloor\to 1\to 2\to \ldots\to \left\lfloor\frac{n}{2}\right\rfloor\) 这么涂。

想到这么做是因为重心满足 "最大的子树不超过 \(\left\lfloor\frac{n}{2}\right\rfloor\)" 这一条件。首先，按 dfs 序涂色是毋庸置疑的，这样能保证同样的颜色肯定被隔在了不同子树，一个类似结论的题是 arc160e。其次，考虑从一个非重心点 \(x\) 向重心方向移动到 \(y\) 的过程，边 \((x,y)\) 两侧子树较小的那一侧在变大，能容纳更多颜色，一定不劣。

至此，以重心为根，所有颜色都被分到了不同子树，两个颜色相同的点之间的简单路径长度可以改写为两个点到重心的距离之和。因此，总答案可以改写为所有点到重心的距离和。

接着，考虑删掉哪个点。我们拥有以下两个观察：

删叶子比删其它点优。因为删非叶子会让其子树内的点的深度都 \(-1\)，不划算。
其次，在所有叶子中，删深度最小的。这是上一段的直接推论。

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

CF1450C1/C2. Errich-Tac-Toe

*2100 Code（C1）

*2300 Code（C2）

见到 \(\lfloor\frac{k}{3}\rfloor\)，可以有意识的将操作划分为三个等价类，满足三个等价类的操作数之和为 \(k\)。这样根据抽屉原理，一定有一类操作的数量 \(\le \lfloor\frac{k}{3}\rfloor\)。

对于 C1，令 \(t_{i,j}=(i+j)\bmod 3\)，那么网格被划分成了三类。定义三种操作如下：

\(\forall \ t_{i,j}=0\) 的 \((i,j)\)，若 \(s_{i,j}= X\)，改为 \(O\)。
\(\forall \ t_{i,j}=1\) 的 \((i,j)\)，若 \(s_{i,j}= X\)，改为 \(O\)。
\(\forall \ t_{i,j}=2\) 的 \((i,j)\)，若 \(s_{i,j}= X\)，改为 \(O\)。

注意到上述任意一种操作都能实现目标（因为任意三个横着的或竖着的格子必定包含 \(t_{i,j}\) 的三种取值）。

并且这三类操作的操作数之和恰好为 \(k\)，根据抽屉原理，一定有一种操作满足操作数 \(\le \lfloor\frac{k}{3}\rfloor\)。

对于 C2，同样令 \(t_{i,j}=(i+j)\bmod 3\)，但三种操作变化如下：

\(\forall \ t_{i,j}=0\) 的 \((i,j)\)，若 \(s_{i,j}= X\)，改为 \(O\)；\(\forall \ t_{i,j}=1\) 的 \((i,j)\)，若 \(s_{i,j}= O\)，改为 \(X\)。
\(\forall \ t_{i,j}=1\) 的 \((i,j)\)，若 \(s_{i,j}= X\)，改为 \(O\)；\(\forall \ t_{i,j}=2\) 的 \((i,j)\)，若 \(s_{i,j}= O\)，改为 \(X\)。
\(\forall \ t_{i,j}=2\) 的 \((i,j)\)，若 \(s_{i,j}= X\)，改为 \(O\)；\(\forall \ t_{i,j}=0\) 的 \((i,j)\)，若 \(s_{i,j}= O\)，改为 \(X\)。

每种操作都由两个形如 \(X\to O\)，\(O\to X\) 的子操作组合而成，保证了任意三个横着的或竖着的格子都一定不全为 \(X/O\)。

又对于每个 \(s_{i,j}\) 不为 . 的格子，至多变化一次，所以上述三种操作的操作数之和仍然是 \(k\)。

同理也一定有一种操作满足操作数 \(\le \lfloor\frac{k}{3}\rfloor\)。

时间复杂度 \(O(n^2)\)。

CF1450E. Capitalism

*2700 Code

首先，原图一定构成二分图，按照 \(a_i\) 的奇偶性分成两侧。不是二分图一定无解。

其次，考虑未定向的边 \((u,v)\)，需要满足 \(a_u=a_v+1\) 或 \(a_v=a_u+1\)。

转换成可以使用差分约束的形式，也就是 \(a_u-a_v\le 1\) 且 \(a_v-a_u\le 1\)。

但这两个条件只是必要条件，若充分则还需满足 \(a_u\neq a_v\)。但注意到二分图自然满足 \(a_u\neq a_v\)（边权为 \(1\) 且没有奇环的情况下两个相邻点的最短路的奇偶性一定不同），故判完二分图上面的转化自然充要。

接着，考虑已经定向了的边 \((u,v)\)，不妨令 \(a_v=a_u+1\)，则同样可以转化为：\(a_u-a_v\le -1\) 且 \(a_v-a_u\le 1\)。

现在可以开始跑差分约束了，但还面临两个问题：

Q1：如何保证跑出来的可行解极差最大？
Q2：选出哪一个点作为起点（零势点）？

A1：差分约束跑出来的可行解就是每个变量在其约束条件下的最大值。你也可以想象选定零势点后，最大值不可能超过从起点出发到某一点的最短路。

A2：我们选取每一个点都作为零势点跑 spfa，并钦定 \(0\) 是最小值，这样最后若存在 \(dis<0\) 或负环，该方案就不合法，忽略掉就行了。

于是，做法是遍历 \(i\in [1,n]\)，钦定 \(i\) 为起点跑出一个 \(dis\) 序列，最后取极差最大的即可。

时间复杂度 \(O(n^2m)\)。

CF1445E. Team-Building

*2500 Code

题意概括一下：给定一个 \(n\) 个点 \(m\) 条边的图，有 \(k\) 种颜色，每个点的颜色你也知道，问选出两种颜色，使它们的导出子图是二分图的方案数。

首先，你得会怎么用并查集判断二分图，不懂的可以做一下 P1525 以及 P5787。

这里总结一下，分如下几步：

初始化一个大小为 \(2n\) 的并查集。
遍历每条边 \((x,y)\)：
- 若 \(\text{dsu.same}(x,y)\)，则不是二分图。
- \(\text{dsu.merge}(x,y+n)\)，\(\text{dsu.merge}(y,x+n)\)。
- 若 \(\text{dsu.same}(x,x+n)\) 或 \(\text{dsu.same}(y,y+n)\)，则不是二分图。
否则是二分图。

回到该题，我们可以把图中的所有边分为两类，第一类是连接相同颜色的边，第二类是连接不同颜色的边。

我们先把第一类边都连起来，对所有 \(k\) 种颜色判断第 \(i\) 种颜色构成的单色连通块是否是二分图。

一种颜色的单色连通块若不是二分图，那么这种颜色与其它颜色的导出子图就一定不是二分图。（因为二分图等价于没有奇环，有奇环的图和其它图并起来原来的奇环也不会消失）

设有 \(cnt\) 种颜色的单色连通块是二分图，那么答案的上界是 \(\frac{cnt(cnt-1)}{2}\)，尝试容斥一下，排除一些不是二分图的组合。

暴力的做法是 \(O(cnt^2)\) 枚举两种颜色，将连接这两种颜色的边的第二类边加上，判断是否为二分图。

注意到第二类边的数量是有限的，如果改成枚举边的话，就是 \(O(m)\) 的。

一种简洁且直接的做法是对每一个颜色二元组 \((col_x,col_y)\) 记录有哪些边 \((u,v)\) 连接了颜色分别为 \(col_x\) 和 \(col_y\) 的点。即用一个 map<array<int, 2>, vector<array<int, 2>>> 存边，虽然多了一个 \(\log\)，但相比把边按颜色排序的做法会好写很多。

注意到整个判断过程第一类边一直保留，第二类边在判断完一种颜色组合后需要撤销，故用一个可撤销并查集来维护。

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

CF2102E. 23 Kingdom

*2200 Code

题目相当于对所有 \(i\in [1,n]\)，选出至多一组 \(a_l=i\)，\(a_r=i\)，\(l<r\) 的 \(l,r\)，并累加 \(r-l\) 的贡献。

因为序列中的每个数只能变小不能变大，故从大到小枚举 \(i\)，试图确定左右端点，没用上的位置丢进一个集合 \(S\) 里备选。而用上的数将来也可能变小作为新的端点，所以这其实是一个反悔贪心问题。

现在，对于一个 \(i\)，我们从 \(S\) 中取出最小的数作为 \(l\)，最大的数作为 \(r\)。有两种选择：

\([l,r]\) 作为一个新的线段。
\(l\) 替代已有线段中最大的 \(l\)，\(r\) 替代已有线段中最小的 \(r\)。

二选一怎么选？注意到已有线段中最大的 \(l\) 一定小于已有线段中最小的 \(r\)，否则肯定不优。

如果 \([l,r]\) 加进当前线段集合后仍然满足上述条件，那么这条新线段的贡献肯定严格大于第二种情况。

反过来，如果 \((L',R')\) 加进去变成 \(L\ L' \ L\ R' \ L\ R\ R\ R\)，那就不如 \(L'\) 替换最后一个 \(L\)，变成 \(L\ L\ L'\ R\ R\ R\)。

故优先判断 \([l,r]\) 作为一个新线段是否可行，不行再考虑替代已有的左右端点。

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

CF2110D. Fewer Batteries

Code

二分答案。设二分出的答案是 \(mid\)，那么策略就固定了：在把电池拿到 \(mid\) 个前，能拿就尽量拿。

DAG 上 dp，令 \(dp[x]\) 表示从 \(1\to x\) 这一段最多能拿到的电池数目： \[ dp[y]=\min(mid,\max_{x\to y}(dp[x]+b[y])) \] 初始令 \(dp[x]=\begin{cases}\min(mid,b[1])&,x=1\\-1 &,x>1\end{cases}\)，最后 check 一下 \(dp[n]\) 是否非负即可。

时间复杂度 \(O(n\log w)\)。