Atcoder 试题乱做 Part 5

难度标签：$\mathtt{\text{[HARD]}}$，$\mathtt{\text{[NORMAL]}}$，$\mathtt{\text{[EASY]}}$。

[AGC017C] Snuke and Spells

$\mathtt{\text{[NORMAL]}}$

首先考虑怎样的序列是合法的。第一步，删除的一定是 $x$ 个 $n$，接下来一定是 $y$ 个 $n-x$......

我们将序列长度逐渐变短的过程画在数轴上，那么应该是从 $n$ 开始，发现有 $x$ 个 $n$，然后向左走 $x$ 步。接下来发现 $n-x$ 上值为 $y$，再向左走 $y$ 步。合法当且仅当这样能走到 $0$。

如果存在 $x$ 个 $p$，就从 $p$ 向左覆盖长度为 $x$ 的线段的话，合法就相当于 $[0,n]$ 都被覆盖了。

考虑最少需要多少步，才能变得合法。注意到每移动一步，至多多覆盖一个位置，所以设 $c$ 是未覆盖位置，则至少需要 $c$ 步。同时容易构造 $c$ 步的方案。于是只需要每次修改之后维护未覆盖的位置个数即可。

[AGC017E] Jigsaw

$\mathtt{\text{[NORMAL]}}$

考虑两个积木什么时候可以拼在一起：

• 两个都接地。
• 两个的长度互补。

先不考虑第一个情况的话，相当于当我们遇到了一个右侧接地、长度为 $l$ 的积木，则他要接一个左侧空白长度为 $l$ 的积木。注意到我们总可以将一个积木抽象为 $(a,b)$ 的形式，两个积木 $x,y$ 能拼起来当且仅当 $b_x=a_y$。

于是，对于每块积木，连边 $a\to b$。同时，有一些积木是可以作为最左侧的，一些积木是可以作为最右侧的。这相当于要求我们从一个“左侧点”走一条欧拉路径走到一个“右侧点”（左右侧点是不交的）。注意到欧拉回路是不可行的，因为左右侧点不交。

再考虑第一种情况，相当于就是将整张图拆成若干 “从一个‘左侧点’走一条欧拉路径走到一个‘右侧点’”。这个形式不是很好，考虑建立一个虚点，向所有作为起点的“左侧点”连边，所有作为终点的“右侧点”向虚点连边。这样，答案就是一个欧拉回路。

意思是说，只要我们能给一些“左侧点”添加入度，“右侧点”添加出度，构成一张有欧拉回路的图，那么就合法了。当然，对于每个连通块，都至少要有一个点能和虚点相连（否则就会出现不经过虚点的欧拉回路）。

[AGC017F] Zigzag

$\mathtt{\text{[HARD]}}$

考虑逐个确定每条路径。注意到我们只关注当前最右侧的路径。最朴素的做法是每次暴力枚举一条路径，判断是否可行，这是 $\mathcal{O}(4^n\text{poly}(n,m))$ 的。

不过，我们可以逐步确定，如果我们把一条路径抽象成一个 $01$ 串，那么一条路径 $A$ 能接在一条路径 $B$ 右侧，当且仅当 $A$ 的每个前缀中 $1$ 的个数都 $\ge$ $B$ 的这个前缀中 $1$ 的个数。

于是，我们可以一个一个确定下一步走哪里。设 ${\text{dp}}_{i,S,p,d}$ 表示目前在转移第 $i$ 条路径，目前转移了前 $p$ 步，$S$ 的前 $p$ 位记录完成转移后的状态，后面的位记录前驱状态的这些位，目前与上条线段的距离是 $d$（$\text{popcount}$ 多 $d$）的方案数。

复杂度是 $\mathcal{O}(2^n{n}^{2}m)$，无法通过。我们考虑吃掉 $d$ 这一维。关注到我们的要求只是对于每个前缀，$\text{popcount}$ 都不小于前驱而已。假设我们在这一位放了一个 $1$，那么在接下来的一段时间内，我们可能都是“安全的”，意思是说，我们做的事情不过是将前驱状态的 $1$ 进行一些提前，再在最后加一些 $1$ 而已。

所以，每次如果决定在当前这一位放一个 $1$ 的话，就直接将 $p$ 之后的最近的 $1$ 抓过来用（把 $1$ 的位置设为 $0$），如果没有 $1$ 了就加一个 $1$。这样就只要 $\mathcal{O}(2^{n}nm)$ 了，可以通过。

[AGC018D] Tree and Hamilton Path

$\mathtt{\text{[HARD]}}$

考察了一个较为重要的构造。

首先，考虑哈密顿环的情形。观察一条边的贡献，设这条边两侧的点个数的 $min$ 是 $c$，则这条边的贡献至多为 $2\times w\times c$，即至多在这条边来回这么多次。

实际上，答案是可以顶到上界的。注意到对答案的贡献与两侧点数的 $min$ 相关。我们知道这个值一定 $\le {\displaystyle \frac{n}{2}}$，从而考虑重心。拿重心为根之后，每个点朝向根的子树都是较大的。

假设现在只有一个重心，则每次我们希望一条路径都能跨越重心。这是可行的，因为若将每棵子树都染色，则每种颜色个数 $<{\displaystyle \frac{n}{2}}$，一定可以围成一个环，使得相邻颜色不同。构造方式，可以拿出 $\text{dfn}$，将 $\text{dfn}$ 为偶数的倒序，隔个插入奇数中，容易证明这样恰好每次会跨越根。

再考虑哈密顿链的情况。如果有两个重心，可以得知中间的边至多经过 $n-1$ 次，所以减掉一次中间的边的权值就可以了（剩下的一定有构造方案）。

如果只有一个重心，那么我们可以选择一条与根相连的，权值最小的边，减去即可。

$\text{I Am Back}$

在鸽了不知道多久之后回来了

中间写了一些，题解就懒得补了/emm。

[AGC013F] Two Faced Cards

$\mathtt{\text{[NORMAL]}}$

首先如果钦定了每个点选第一个还是第二个，那么就可以直接每个 $x$ 向所有 $\ge x$ 的 $Y$ 连边。

如何判断是否存在完美匹配？直接把 $X$ 侧看作 $-1$，$Y$ 侧看作 $1$，每个后缀权值 $\ge 0$ 即可（当然也可以从 $\text{Hall}$ 定理的角度得到）。接下来考虑贪心地使得尽量多的点选第一个数：

一开始默认他们都选第一个数，当某一刻的后缀权值 $<0$，选出后缀中的某一个点，切换至“选第二个”。此处明显选择“第二个”最小的点，可以用堆维护。

考虑动态的怎么做。先把 $n$ 个 $X$ 和 $n+1$ 个 $Y$ 按上述方法匹配好，则整个序列的权值是 $1$（因为一定有一个人没匹配）。如果此时已经不存在合法解了，那以后一定不会有。对于新加入的二元组，我们枚举他选择第一个还是第二个。假设他选择了 $x$，那从 $x$ 往前的所有前缀权值都会 $-1$，也就是到了 $x$ 及 $x$ 以前的，第一个权值为 $0$ 的位置 $p$，会出现权值为负数的问题。

同样的，只需要找到 $\ge p$ 的，选“第一个”的，且“第二个”尽量小的元素，切换一下即可。假设切换到 $q$，那 $q$ 及 $q$ 以前的第一个 $0$ 处又会出现问题，只需要重复上述过程即可。注意到这样不会重复选择同一个元素。

于是可以预处理，每个 $0$ 开始往前“跳”需要多少步，或者无解。然后每次只要找到 $p$ 直接调用即可。

[AGC011F] Train Service Planning

$\mathtt{\text{[NORMAL]}}$

尝试手玩。和样例解释的图一样，可以描述为若干段斜率绝对值为 $1$ 的斜线。

对于只有 $B_i=1$ 的情况，首先容易给出一个无解的充分条件：若 $2A_i>K$ 则必然无解，因为甚至塞不进两条不交的，长度为 $A_i$ 的斜线。判完这种情况之后，容易发现就一定能构造一组解了：直接无脑在每个时间段（两条横线之间）随便塞两条斜线就一定可行，只不过可能等待时间很长。

则现在只需要最小化等待时间了，注意到每个时间段看起来非常独立，你可以对每个时间段中任意平移，对合法性没有影响。于是考虑一层一层转移。

如果我们已经得到了上层往这层转移的两个端点 $a,b$，其中 $a$ 是往下走，$b$ 是往上走，那么只需再确定两个接口 $c,d$，计算 $a\to c$ 和 $d\to b$ 即为转移代价。这个问题相当于：在环上有 $a,b,c,d$ 四个点，顺序任意，且只能顺时针移动，要求 $ac$ 和 $db$ 的距离和尽量小。

经过一些讨论容易发现在 $a,b,c,d$ 相对顺序不变的时候，距离是不变的。且 $ac$ 重合或 $bd$ 重合都一定不会漏掉最优解。意思是，当我们选择将向下的斜线一直无缝衔接，只调整向上的斜线，不会漏掉最优解。

于是现在的问题中就只剩下一根向上的斜线了，容易将问题转化为：记录当前斜线的端点（需要满足不和向下的斜线相交，这是模意义下的一个区间），然后转移到下一个点，花费两者之间有向距离。经过对这些限制区间的加减，可以把问题变成：

给定 $n$ 个区间 $[L_i,R_i]$，你可以一开始选定一个变量 $x$，第 $i$ 次需要满足 $x\in [L_i,R_i]$，你每次可以将 $x\leftarrow (x+1)modK$，求最小操作次数。

可以直接设 ${\text{dp}}_{i,j}$ 表示前 $i$ 层后 $x=j$ 的最小花费，那么：

$${\text{dp}}_{i,j}=min\{{\text{dp}}_{i-1,k}+\text{dis}(k,j)\}$$

展开 $\text{dis}(k,j)$ 得到 $j-k$ 或 $j-k+K$，改成维护 ${\text{dp}}_{i,j}-j$ 的最小值即可。使用线段树来优化转移，以下是我没想到的部分：

考虑当前区间是 $[l,r]$，那对于 $i\in [l,r]$，相当于 $\le i$ 的部分都可以直接转移，$>i$ 的部分要 $+K$，于是是一个前缀 $min$ 和后缀 $min+K$ 赋值到当前位置。要对区间内每个 $i$ 都进行这个操作。有两种思考方式：

注意到这实际上就是有向地移动所花费的代价，于是对于任意到达 $i$ 的过程，要么是原本就在 $i$，要么从 $i-1$ 来，所以只需要对 $l$ 这一个位置进行修改即可。

另一种想法是考虑对 $i,i+1$ 两者的转移的差异，只有 $i+1$ 这一个点从 $+K$ 变成不 $+K$。这相当于只要把 $i$ 处的答案和 $i+1$ 原本的答案 $\text{chkmin}$ 即可，而在以后，如果 $i,i+1$ 一直同时出现，则没必要再修改 $i+1$；如果 $i,i+1$ 某一刻不同时出现了，那么必然使用 $i$ 更新了 $i+1$。

所以就可以直接线段树维护了，时间复杂度 $\mathcal{O}(n\log n)$。

[AGC018C] Coins

$\mathtt{\text{[HARD]}}$

贪心真是太困难了。

首先假设默认都选择 $c$，然后调整，将 $a_i\leftarrow a_i-c_i,b_i\leftarrow b_i-c_i$。

假设现在已经选出了 $x$ 个选 $A$，$y$ 个选 $B$，如果不能通过交换变得更优，那么：

$\mathrm{\forall }i\in A,j\in B,a_i+b_j\ge a_j+b_i$

也就是 $a_i-b_i\ge a_j-b_j$。如果我们选定了 $A\cup B$，那么一定将 $a_i-b_i$ 最大的选作 $A$。于是首先将所有数按照 $a_i-b_i$ 从大到小排序，$A$ 一定在一个前缀中选，$B$ 在对应的后缀里选。

因此设 ${\text{pre}}_i,{\text{suf}}_i$ 表示前缀里选 $x$ 个 $A$，后缀里选 $y$ 个 $B$ 的最大 $\mathrm{\Delta }$。然后枚举分界点即可。时间复杂度 $\mathcal{O}(n\log n)$。

[AGC019E] Shuffle and Swap

$\mathtt{\text{[EASY]}}$

首先，一定是一些 11 之间乱换，然后 10 从通过若干个 11 移动到一个 01 上去。

于是，最后一定会形如若干链，从 10 开始，经过若干 11，以 01 结束。记 10，01，11 分别有 $A,B,C$ 个（显然 $A=B$）。一定有 $A$ 条链，可以枚举有多少个 $C$ 中的插入链中，然后剩下的 $C$ 中部分直接全排列就行了。

至于 $A$ 条链排列起来，花费 $i$ 个 $C$ 中元素，可以直接 $\exp$。还有一些系数，比如把 $A,B$ 分别匹配，有一个 $A!$ 的系数之类的。复杂度可以是 $\mathcal{O}(n^2)$，$\mathcal{O}(n{\log }^{2}n)$ 或 $\mathcal{O}(n\log n)$。

[AGC020C] Median Sum

$\mathtt{\text{[EASY]}}$

首先有简单的 $\mathcal{O}(n^{2}a)$ 背包。注意到对于 $S$ 和 $S$ 的补集，他们应该恰好在中位数的左右，因此上述背包的方案数是对称的！因此就只关心拼出过哪些数，而不关心有多少种方案了。只需要 bitset 优化即可做到 $\mathcal{O}({\displaystyle \frac{n^{2}a}{\omega }})$。

[AGC015E] Mr.Aoki Incubator

$\mathtt{\text{[HARD]}}$

完全不会做/ll

观察最终形态，最后的排列顺序一定是按照 $v$ 从小到大。如果一个点 $i$ 被染色了，那他会染到什么样的点呢？

首先，若 $x_j>x_i,v_j<v_i$，或 $x_j<x_i,v_j>v_i$，那么 $i$ 一定会染到 $j$（因为互相穿过）。事实证明，找到 $x_j\ge x_i,v_j\le v_i$ 的，$v_j$ 最小的 $j$ 作为 $l$；$x_j\le x_i,v_j\ge v_i$ 的，$v_j$ 最大的 $j$ 作为 $r$，$i$ 会染黑 $[l,r]$ 中的所有点（还是按 $v$ 排序）。

具体方式可以通过讨论一个 $[l,r]$ 内点的 $x$ 的相对关系。于是问题就变成了，要选择一些区间覆盖 $[1,n]$。同时，注意到将这些区间按照 $i$ 的 $x_i$ 排序后，左右端点分别单调，所以可以通过前缀和来维护，做到线性 $\text{dp}$。