AGC 选做

AGC017E Jigsaw

将离地 \(0\) 长度 \(a\) 的看做 \(a\)，离地 \(a\) 的看做 \(-a\)，则两个积木能匹配相当于左积木的右边和右积木的左边互为相反数。方便起见，将所有积木左边取反，看做相等匹配。

我们考虑放到图上，一个左边为 \(a\) 右边为 \(b\) 的积木会让图上从 \(a\to b\) 有一个有向边。对于每个弱联通块分别考虑：

• 如果这个弱联通块内所有点的入度减出度都为 \(0\)，则不可能存在。
• 否则，考虑所有入度减出度大于 \(0\) 的 \(x\)，其必须满足 \(x<0\)，对于入度减出度小于 \(0\) 的 \(x\)，其必须满足 \(x>0\)。并且，还需要存在一种将起点和终点匹配的方式，使得整张图能被划分成若干欧拉路径。

可以证明，只要图满足上述条件，存在这样的划分方式以及欧拉路径。上面条件显然是必要的，考虑构造证明：新建一个超级源 \(S\)，若 \(x\) 的入度比出度大 \(x\)，则让 \(x\) 向 \(S\) 连边补足出度，否则让 \(S\) 向 \(x\) 连边补足入度。现在的图显然有欧拉回路，然后在这个图的欧拉回路中把和 \(S\) 有关的边扔掉就可以得到匹配方式和欧拉路径。

上述条件容易 \(O(n)\) 判断。

submission

AGC016E Poor Turkeys

考虑在固定 \(i\) 一定存在的时候，会产生什么样的限制。

考虑按照时间从后往前做。对于一条边 \(x,y\)，如果 \(x,y\) 都存活了，那么 \(i\) 肯定无法最终存在。否则，如果其中有一个已经存活了，则另一个就确定了被杀死的时间，也就是当前时刻，之后也就存活了。因此，钦定一个点最终存在就给某些点确定了被杀死的时间。

然后考虑两个点同时存在的时候的限制，一个简单的想法是直接按照上面跑，如果跑出矛盾了，也就是说一个点被确定了两次时间，就寄了。但是这样是 \(O(n^2m)\) 的，无法通过。

然后你发现，如果两个点都可以各自存在，那么两个点的限制应该是非常独立的：不能相交。因此，分别跑出两个点的限制之后，再看有没有一个点同时被两个点确定了时间即可。时间复杂度 \(O(nm+\frac{n^3}{\omega})\)。

submission

AGC013F Two Faced Cards

我们考虑用 Hall 定理转化问题。当我们在一个二元组中选择了 \(x\) 之后，我们给一个序列 \(A\) 的 \([x,\infty]\) 都 \(+1\)。对于另一种卡牌 \(x\)，给 \(A\) 的 \([x,\infty]\) 都 \(-1\)。如果两边卡牌数相等，则最后我们要求 \(A_i\geq 0\)。

可以预见的，我们需要对于每个单面卡牌，求出把这张单面卡牌拿掉之后，二元组得分最大值，并且一旦这个求出来了，询问就好做了。转化成 Hall 定理，就是对于一个 \(x\)，满足 \(i<x\) 的 \(A_i\geq 0\)，否则 \(A_i\geq -1\)。

不妨假设 \(A_i> B_i\)，我们先让所有点选择 \(A_i\)，之后让最少的 \([B_i,A_i-1]\) 区间 \(+1\) 来满足条件。

接下来一步是比较思维跳跃的一步：考虑最大的 \(i\) 满足 \(A_i<-1\)，找到包含 \(i\) 的左端点最小的区间 \([l,r]\)，则 \([l,r]\) 一定被选。

分类讨论：

• 若 \(A_i\) 处限制是 \(\geq -1\)，则 \(i\) 后面都满足了，那么一定选左端点最小的。
• 若 \(A_i\) 处限制是 \(\geq -1\)，则 \(i\) 处被两个区间覆盖，\(i\) 后面只需要被一个区间覆盖就能满足条件，这样将两个区间中右端点较小的一个替换成当前这个一定不劣。

则我们可以用一个堆维护贪心。

之后 \(A_i\) 就 \(\geq -1\)，那么对于一个 \(x\) 的限制，就相当于选一些区间将 \(<x\) 处的 \(A_i=-1\) 都覆盖到，这个可以简单贪心。时间复杂度 \(O(n\log n)\)。

submission

AGC011F Train Service Planning

记 \(s_i\) 表示 \(0\to n\) 的车从 \(i\) 站出发的时间，\(t_i\) 表示 \(n\to 0\) 的车到 \(t_i\) 的时间。如果我们不考虑 \(K\) 分钟一次的循环的话，那么如果 \(i\) 是单向线，则区间 \([s_i,s_i+A_i]\) 和区间 \([t_i-A_i,t_i]\) 交的长度为 \(0\)。而考虑了 \(K\) 分钟一次的循环之后，就要求这两个区间在 \(\bmod K\) 意义下不交。

初始的时候 \(s_0=0,t_0\) 可以等于任意值。每次经过一个站之后，会让 \(s_i\) 加上 \(A_i\)，\(t_i\) 减去 \(A_i\)，同时可以花费 \(1\) 的代价将 \(s_i\) 加上 \(1\)，\(t_i\) 减去 \(1\)，要求在单向线的时候区间不交。区间 \([s_i,s_i+A_i]\) 和区间 \([t_i-A_i,t_i]\) 不交的条件是 \(t_i-s_i\geq 2A_i\) 或者 \(t_i=s_i\)，发现这只和 \(s_i,t_i\) 相对大小有关，并且两个改变 \(s,t\) 的操作对相对大小的改变是一样的，因此可以变成维护相对大小。

记 \(f_{i,j}\) 表示到了第 \(i\) 个站，相对大小为 \(j\) 的最小代价，每次要做的就是将 \(j\) 加上一个值，或者将一个区间求最小值之后删去，这个容易用珂朵莉树均摊维护，时间复杂度 \(O(n\log n)\)。

submission

AGC002E Candy Piles

什么时候能想到放到网格上？什么时候能想到放到网格上？

考虑一个简单的 DP：设 \(f_{i,j}\) 表示删了 \(i\) 个最大的数，整体减一减了 \(j\) 次，是先手必胜还是后手必胜。

将 \(a_i\) 从大到小排序之后，这个东西就可以看成一个阶梯状的网格，变成，从 \((1,1)\) 开始，每次往上或者往右走一步，走出边界的人输了。

观察一下，会发现有 \(f_{i,j}=f_{i+1,j+1}\)。考虑分类讨论一下：

• 若 \(f_{i+1,j+1}\) 为先手必败，则 \(f_{i+1,j}\) 和 \(f_{i,j+1}\) 为先手必胜，这样 \(f_{i,j}\) 就先手必败了。
• 反之，则考虑 \(f_{i+1,j+1}\) 的哪个后继是先手必败的，不妨假设为 \(f_{i+2,j+1}\)，则 \(f_{i+2,j}\) 就是先手必胜的，\(f_{i+1,j}\) 是先手必败的，那么 \(f_{i,j}\) 是先手必胜的。

因此，我们只需要找到 \((1,1)\) 不断往上走，走到边界，然后看一看两边能走的长度即可。

submission