AtCoder Grand Contest 043 题解
A - Range Flip Find Route
题意
给定一个 \(H\times W\) 的黑白矩阵 \(A\)，你需要执行若干次以下操作使得 \((1,1)\) 可以通过向下、向右且只走白色格子到达 \((H,W)\)（起点、终点也必须是白色）：
- 将一个连续子矩阵中每个格子反色。
求最少操作次数。
\(H,W\le 100\)
题解
考虑一条 \((1,1)\) 到 \((H,W)\) 只向下、向右的路径。对于路径上一个黑色的连续段，由于路径是只向下、向右的，我们一定可以通过一次操作把改路径上的这个黑色连续段变成白色。
那么我们只需要选择黑色连续段数量最少的路径。DP 即可。
时间复杂度 \(O(HW)\)。
B - 123 Triangle
题意
给定一个只有 \(1,2,3\) 的序列 \(a_1,a_2,\ldots,a_n\)。定义 \(x_{i,j}\) 为
- \(x_{1,j}=a_j\)
- \(x_{i,j}=|x_{i-1,j}-x_{i-1,j+1}|\ (i > 1)\)
求 \(x_{n,1}\)。
\(n\le 10^6\)
题解
首先我们可以把 \(a_i\) 都减 \(1\) 变成 \(0,1,2\)，显然对答案没有影响。
考虑只有 \(0,1\) 时，显然中间过程也只有 \(0,1\)。而对于两个 \(a,b\in \{0,1\}\)，有 \(|a-b|=(a+b)\bmod 2\)。于是 \(a_i\) 对答案的贡献为 \(\begin{pmatrix}n-1\\i-1\end{pmatrix}\)，在模 \(2\) 意义下使用卢卡斯定理计算即可。
只有 \(0,2\) 时，发现我们可以把 \(a_i\) 都除以 \(2\)，转化成只有 \(0,1\) 的问题，最后乘 \(2\) 即可。
包含 \(1\) 时，在出现全 \(1\) 之前，所有状态都一定包含至少一个 \(1\)；而全 \(1\) 之后的所有状态一定是全 \(0\)。所以最终答案一定不可能是 \(2\)。于是我们把 \(2\) 变为 \(0\) 后用只有 \(0,1\) 的方法计算即可。
时间复杂度 \(O(n\log n)\)。
C - Giant Graph
题意
给定三个 \(N\) 个点分别为 \(M_1,M_2,M_3\) 条边的简单无向图 \(X,Y,Z\)，记每张图的点分别为 \(x_1,\ldots,x_n,y_1,\ldots,y_n,z_1,\ldots,z_n\)。
定义 \(X\times Y\times Z\) 为一个由所有 \(N^3\) 个三元组 \((x_i,y_j,z_k)\) 作为节点的无向图，边的生成方式如下：
- 对于 \(X\) 中的所有边 \((x_u,x_v)\) 和所有 \(w,l\)，\((x_u,y_w,z_l)\) 和 \((x_v,y_w,z_l)\) 连边；
- 对于 \(Y\) 中的所有边 \((y_u,y_v)\) 和所有 \(w,l\)，\((x_w,y_u,z_l)\) 和 \((x_w,y_v,z_l)\) 连边；
- 对于 \(Z\) 中的所有边 \((z_u,z_v)\) 和所有 \(w,l\)，\((x_w,y_l,z_u)\) 和 \((x_w,y_l,z_v)\) 连边。
一个节点 \((x_i,y_j,z_k)\) 的权值为 \((10^{18})^{i+j+k}\)。
求 \(X\times Y\times Z\) 的最大带权独立集。
\(N\le 10^5,M_1+M_2+M_3\le 10^5\)。
题解
考虑一个 \(N^3\) 的做法，我们将 \((x_i,y_j,z_k)\) 按 \(i+j+k\) 从大到小排序，依次加入最大独立集。这样贪心显然是对的。
我们可以把这个贪心写成一个类似于 DP 的形式，即 \(f_{i,j,k}\) 表示 \((x_i,y_j,z_k)\) 是否被选入最大独立集。\((x_i,y_j,z_k)\) 被选入最大独立集当且仅当 \((x_i,y_j,z_k)\) 的后继状态都没有被选入最大独立集，其中后继状态是指与 \((x_i,y_j,z_k)\) 有边且权值大于该状态权值的状态。
观察 DP 的转移，发现这与博弈论的转移非常相似。于是我们可以把问题转化为一个游戏：
- 有三张无向图 \(X,Y,Z\)，初始时在 \(x_1,y_1,z_1\) 有一颗棋子。两个人轮流操作，每次选择一张图上的棋子移动到相邻的且编号更大的节点，若无法移动则输。
选入最大独立集的点恰好是所有后手必胜的状态。
注意到这一游戏是三个游戏的和，SG 函数值等于三个游戏的 SG 值异或的结果。而三个游戏各自的 SG 值可以 \(O(N+M)\) 求出。
我们现在需要对所有满足 \(\operatorname{SG}(x_i)\oplus \operatorname{SG}(y_j)\oplus \operatorname{SG}(z_k)=0\) 的 \(i,j,k\)，对 \(10^{18(i+j+k)}\) 求和。
注意到单个游戏的 SG 函数值在 \(O(\sqrt{M})\) 级别，所以我们枚举其中两个 SG 值就可以唯一确定另一个。时间复杂度 \(O(N+M)\)。
D - Merge Triplets
题意
求可以通过以下方式构造的本质不同的 \(1\) 到 \(3n\) 的排列 \(P\) 的数量：
- 构造 \(N\) 个长度为 \(3\) 的序列 \(A_1,A_2,\ldots,A_n\)，满足 \(1\) 到 \(3n\) 的每个数恰好出现一次。
- 求出所有非空序列第一个元素的最小值 \(x\)，将 \(x\) 从序列中删去，加入 \(P\) 的末尾。
\(n\le 2000\)
题解
考虑对于一个序列 \(x_1,x_2,x_3\)，若 \(x_1 > x_2\)，则选了 \(x_1\) 以后一定会立刻选 \(x_2\)；其他两对类似。
于是我们可以将这样的一个序列分成若干小块，每个小块满足块首元素是块内最大值，并且满足块首元素递增。
由于我们保证了单个序列中块首元素递增，那么最终排列一定是所有小块按块首元素递增排列的结果。
这就意味着，对于一个合法排列，我们一定可以把该排列分成若干块，满足：
- 每块元素数量不超过 \(3\)；
- 块首元素是块内最大值；
- 块首元素递增排列。
但是满足以上条件的排列不一定合法，因为不一定能还原出原来的 \(n\) 个序列。
但是我们发现，单个序列的分块方式一定只有 \(3;1,2;2,1;1,1,1\) 四种，可以发现 \(2\) 的数量一定不超过 \(1\) 的数量。同时我们发现，在满足以上三个条件的情况下，只要满足该条件，一定可以构造出原来的 \(n\) 个序列。
所以我们只要在上述三个条件的基础上加上这个条件就构成了一个排列合法的充要条件。
假设块大小依次为 \(a_1,a_2,\ldots,a_k\)，我们考虑计算排列合法的概率。我们发现我们需要保证第 \(k\) 块的块首元素是整个排列的最大值，而每个位置成为排列最大值的概率是相同的，所以概率为 \(\frac{1}{n}\)。然后我们发现剩下的位置形成的排列仍然是等概率的，所以我们可以把它变成一个 \(n-a_k\) 的子问题。于是，合法的概率为 \[\prod_{i=1}^{k}\frac{1}{\sum\limits_{j=1}^{i}a_j}\]
排列数量只要再乘上 \(n!\) 即可。
于是我们就可以 DP 了。用 \(f_{i,j}\) 表示前 \(i\) 个位置，\(1\) 的数量与 \(2\) 的数量的差为 \(j\)。转移只要考虑下一块长度即可。
时间复杂度 \(O(n^2)\)。
E - Topology
题意
平面上有 \(n\) 个点，第 \(i\ (0\le i < n)\) 个点在 \((i+0.5,0.5)\)。对于这 \(n\) 个点的每一个子集 \(S\) 都给出了 \(A_S\in \{0,1\}\)。
你需要构造一个闭合曲线 \(C\) 满足对于所有 \(n\) 个点的子集 \(S\)，都有：
- \(C\) 能在不经过点集 \(S\) 的情况下连续移动到 \(x\) 轴下方当且仅当 \(A_S=1\)。
对「闭合曲线」、「不经过点集 \(S\) 的连续移动」的形式化定义以及输出方式参见原题。
\(n\le 8\)
题解
如果存在一个集合 \(S\) 满足 \(A_S=1\) 但存在它的一个子集 \(S'\) 满足 \(A_{S'}=0\)，那么一定不合法。我们可以通过构造证明其余情况一定合法。
考虑从第 \(i\) 个点向上射出一条射线 \(u_i\)，向下射出一条射线 \(d_i\)。
于是我们可以把一条曲线依次经过的射线编号顺次连接生成一个字符串，同样我们也可以根据这样的字符串生成一条曲线。
如样例 2 中的曲线在 \(S=\{0,1\}\) 时可以记为 \(d_1u_1u_0d_0\)。
我们可以发现曲线能移动到 \(x\) 轴下方当且仅当生成的字符串满足：
- 你可以通过不断删除连续两个相同的字符使得字符串成为空串。
接下来我们考虑 \(A=11\ldots 110\) 的情况，即只有 \(S\) 为全集时不能移动到 \(x\) 轴下方。我们可以递归地构造这样的字符串，记为 \(a_n\)：
- 当 \(n=1\) 时，\(a_n=u_0d_0\)。
- 当 \(n\ge 2\) 时，令 \(s\) 为 \(a_{n-1}\) 中所有字符的下标加 \(1\) 得到的字符串，构造 \(a_n=u_0su_0d_0s^{-1}d_0\)，其中 \(s^{-1}\) 表示 \(s\) 翻转后得到的字符串。
例如：
- \(a_1=u_0d_0\)
- \(a_2=u_0(u_1d_1)u_0d_0(d_1u_1)d_0\)
- \(a_3=u_0(u_1(u_2d_2)u_1d_1(d_2u_2)d_1)u_0d_0(d_1(u_2d_2)d_1u_1(d_2u_2)u_1)d_0\)
证明可以通过归纳证明，分别考虑 \(0\not\in S\) 和 \(0\in S,\exists 1\le i < n,i\not\in S\) 两种情况进行证明即可。
对于一般情况，我们只要对于所有满足 \(A_S=0\) 且对于所有 \(S'\in S\) 都有 \(A_{S'}=1\) 的集合 \(S\) 进行类似构造得到的字符串拼接起来即可。
一个非常宽的上界是 \(4n\cdot 3^n\)，可以通过。
F - Jewelry Box
题意
有 \(N\) 个商店，第 \(i\) 个商店卖 \(K_i\) 种珠宝，第 \(i\) 个商店的第 \(j\) 个珠宝重量为 \(S_{i,j}\)，价格为 \(P_{i,j}\)，数量为 \(C_{i,j}\)。
一个珠宝盒被称为好的当且仅当满足以下条件：
- 对于每个商店，珠宝盒中都恰好包含一颗该商店的珠宝。
- 对于所有 \(1\le i\le M\)，满足珠宝盒中商店 \(V_i\) 的珠宝重量小于等于商店 \(U_i\) 的珠宝重量加 \(W_i\)。
\(Q\) 次询问，每次询问 \(A_i\)，表示制作 \(A_i\) 个好的珠宝盒的最小总价格。
\(N,K_i\le 30,S_{i,j},M\le 50,Q\le 10^5,W_i\le 10^9,P_{i,j}\le 30,C_{i,j}\le 10^{12},A_i\le 3\times 10^{13}\)
题解
首先考虑只有一组询问的情况，即询问制作 \(A\) 个好的珠宝盒的最小价格。
假设对于每个商店我们已经选出了 \(A\) 个珠宝。那么我们贪心地考虑，一定是最小的放在第一个珠宝盒内，第二小的放在第二个珠宝盒内，以此类推。
于是我们可以对每个商店的珠宝按重量从小到大排序，然后记 \(x_{i,j}\) 为第 \(i\) 个商店中前 \(j\) 个物品选了几个。
对于一个限制 \((u,v,w)\)，对于 \(1\le j\le K_v\)，令 \(k\) 为 \(S_{u,k}+W_i\ge S_{v,j}\) 的最小的 \(k\)，不存在则令 \(k=K_u+1\)。那么这一限制等价于对于所有 \(j\) 都满足 \(x_{v,j-1}\ge x_{u,k-1}\)。
于是我们把问题转化成了一个线性规划问题：
- minimize \(\sum P_{i,j}(x_{i,j}-x_{i,j-1})\)
- subject to \[ \begin{cases} x_{i,j}\ge x_{i,j-1}\\ x_{i,j}\le x_{i,j-1}+C_{i,j}\\ x_{i,0}=0\\ x_{i,K_i}=A\\ x_{u,k}\le x_{v,j}\\ x_{i,j}\ge 0 \end{cases} \]
注意到求价格时是相邻两项作差，那么我们无需保证 \(x_{i,0}=0,x_{i,K_i}=A\)，只需要保证 \(x_{i,K_i}-x_{i,0}=A\) 即可，于是可以拆成 \(x_{i,K_i}-x_{i,0}\le A\) 和 \(x_{i,K_i}-x_{i,0}\ge A\) 两个限制。注意到 \(x_{i,K_i}-x_{i,0} > A\) 时一定不优，所以我们可以前一个限制。
于是我们可以把问题转化成标准型：
- minimize \(\sum x_{i,j}(P_{i,j}-P_{i,j+1})\)
- subject to \[ \begin{cases} x_{i,j}-x_{i,j-1}\ge 0\\ x_{i,j-1}-x_{i,j}\ge -C_{i,j}\\ x_{i,K_i}-x_{i,0}\ge A\\ x_{v,j}-x_{u,k}\ge 0\\ x_{i,j}\ge 0 \end{cases} \]
注意到系数矩阵的每行都有恰好一个 \(+1\) 和一个 \(-1\)，于是我们可以把问题对偶，系数矩阵的每一列都有恰好一个 \(+1\) 和一个 \(-1\)。
由于左边的和为 \(0\)，右边的和也为 \(0\)，而每个限制都是小于等于，那么所有限制一定都是取到等于。
于是我们可以根据网络流的流量守恒建立费用流模型。
图中的一个点对应对偶后的一个方程，也就是原问题的一个变量；图中的一条边对应对偶后的一个变量，也就是原问题的一个限制。对于原问题中 \(x-y\ge w\) 的限制，则从 \(x\) 向 \(y\) 连一条流量为 \(\infty\)，费用为 \(w\) 的边；对于原问题最小化的式子中变量 \(x\) 的系数 \(c\)，若 \(c>0\)，则从源点向 \(x\) 连一条流量为 \(c\)，费用为 \(0\) 的边，否则从 \(x\) 向汇点连一条流量为 \(c\)，费用为 \(0\) 的边，特别地，这些边必须满流。
我们可以首先利用所有 \(x_{i,j}\) 向 \(x_{i,j-1}\) 连的 \((\infty,0)\) 的边，将所有需要满流的边满流。可以发现这一定可以做到，并且流完以后得到的反向边为 \(x_{i,j-1}\) 向 \(x_{i,j}\) 的流量为 \(P_{i,j}\)，费用为 \(0\) 的边。
于是我们可以把源汇点去掉，只保留这些反向边，变成一个无源汇最大费用可行流的问题。
注意到边权与 \(A\) 有关的只有 \(x_{i,K_i}\) 向 \(x_{i,0}\) 连的流量为 \(\infty\)，费用为 \(A\) 的边。考虑将所有 \(x_{i,0}\) 缩成一个点 \(S\)，\(x_{i,K_i}\) 缩成一个点 \(T\)，就只有一条 \(T\) 到 \(S\) 的 \((\infty,A)\) 的边了。
为了使费用最大，每一次增广一定是从 \(S\) 流到 \(T\) 再经过这条费用为 \(A\) 的边流回 \(S\)。条件是 \(S\) 到 \(T\) 的这条增广路的费用 \(\ge -A\)。
根据费用流每次增广的凸性，我们可以直接二分得到增广次数。
时间复杂度 \(O(\operatorname{MCMF}(\sum K_i,\sum K_i+\sum K_{V_i})+Q\log \sum P_{i,j})\)。
