AtCoder Regular Contest 105 题解
A - Fourtune Cookies
题意
给定四个整数 \(A,B,C,D\)，判断是否可以选择一个或更多个数使得这些数之和等于剩下的数之和。
题解
排序，只有 \(A+D=B+C\) 和 \(A+B+C=D\) 两种情况。
B - MAX-=min
题意
有 \(N\) 个数 \(a_i\)，不断执行以下操作，直到所有数相等：
- 将所有等于最大值的数减去最小值。
求最后每个数的值。
\(N\le 10^5,a_i\le 10^9\)
题解
显然执行题目中的操作不会改变所有数的 gcd。
于是求出所有数的 gcd 即可。
时间复杂度 \(O(N+\log a_i)\)。
C - Camels and Bridge
题意
有 \(N\) 个球，第 \(i\) 个球的重量为 \(w_i\)。你可以将这些球按任意顺序在数轴上排列，相邻两个球的距离为任意非负实数。
你需要满足 \(M\) 个限制，第 \(i\) 个限制为数轴上任意长度为 \(l_i\) 的开区间（即不包含左右端点）中的球重量之和不超过 \(k_i\)。
求最右边的球与最左边的球的距离的最小值，或输出无解。
\(N\le 8,M\le 10^5\)
题解
枚举球的顺序，令 \(x_i\) 为确定顺序后从左到右第 \(i\) 个球的坐标，那么可以根据限制得到 \(x_i\) 之间的若干限制。
根据这些限制跑差分约束即可。注意到每条边只会从前往后连，所以可以直接从前往后 DP。
时间复杂度 \(O(M\log M+N!\cdot N^2\log M)\)。
D - Let's Play Nim
题意
有 \(N\) 个包，第 \(i\) 个包有 \(a_i\) 个金币。另外还有无限个空盘子。
A 和 B 玩游戏，A 先手，两人轮流操作，每次操作如下：
- 若存在一个包有金币，那么选择一个有金币的包，将这个包的所有金币放到任意一个盘子上；
- 若不存在包有金币，那么选择一个有金币的盘子，取走一个或更多个金币。
不能操作的人输。判断先手是否有必胜策略。
\(N\le 10^5,a_i\le 10^9\)
题解
发现包为空以后是一个 Nim 游戏。Nim 游戏先手必胜的条件是异或和大于 \(0\)。
若干个数的最大值若超过这些数总和的一半，那么异或和一定大于 \(0\)。这是因为异或的本质是不进位加法，由于最大值大于其他数的和，那么最大值一定大于其他数的异或和，所以总异或和一定不为 \(0\)。
当 \(N\) 为奇数时，最后的 Nim 游戏 B 是先手，而 B 需要使得最大值超过总和的一半很简单，只需要不断将金币最多的包放到金币最多的盘子上即可，可以证明一定满足条件。所以 \(N\) 为奇数时一定是 B 获胜。
当 \(N\) 为偶数时，最后的 Nim 游戏 A 是先手。A 为了使得最大值最大，一定是每次选最大值放到一个固定的盘子上。而 B 为了使得 A 选的数之和尽量小，每次也会选择最大值放到其他盘子中。
在这样的策略下，假设 \(a\) 从大到小排序，若存在 \(a_{2i-1}>a_{2i}\)，那么 A 一定可以达到目标；否则 B 只要每次做与 A 类似的操作可以保证异或和一直为 \(0\)。
时间复杂度 \(O(N\log N)\)。
E - Keep Graph Disconnected
题意
有一个 \(N\) 个点 \(M\) 条边的无向图 \(G\)。定义一个图是好的当且仅当 \(1\) 和 \(N\) 不连通且没有自环和重边。保证一开始的 \(G\) 是好的。
A 和 B 玩游戏，A 先手，两人轮流操作，每次操作为在保证 \(G\) 是好的前提下加入一条边。
不能操作的人输。判断先手是否有必胜策略。
\(N,M\le 10^5\)
题解
显然最后两个图一定是两个分别包含 \(1\) 和 \(N\) 的完全图组成的。令两个完全图的大小分别为 \(A,B\)，那么新加的边数为 \(\frac{N(N-1)}{2}-M-AB\)。也就是说，最后获胜的人与 \(AB\) 的奇偶性有关。
当 \(N\) 为奇数时，\(A\) 和 \(B\) 必有一个是偶数，那么 \(AB\) 一定为偶数，只需要判断 \(\frac{N(N-1)}{2}-M\) 的奇偶性即可确定胜者。
当 \(N\) 为偶数时，记 \(x\) 和 \(y\) 为一开始 \(1\) 和 \(N\) 所在连通块的大小。
若 \(x\) 和 \(y\) 奇偶性不同，那么其他连通块中大小为奇数的一定有奇数个，先手可以先将 \(x\) 和 \(y\) 操作成同奇或同偶，然后跟着后手操作即可。
否则，若先手需要的 \(AB\) 奇偶性与 \(xy\) 奇偶性不同，那么后手一定必胜，否则先手必胜。
时间复杂度 \(O(N+M)\)。
F - Lights Out on Connected Graph
题意
注意以下题意相较于原题意有一步简单的转化。
给定一个 \(N\) 个点 \(M\) 条边的无向图 \(G=(V,E)\)。你可以选择 \(E\) 的一个子集 \(E'\) 得到无向图 \(G'=(V,E')\)。
求有多少 \(G'\) 是连通二分图。对 \(998244353\) 取模。
\(N\le 17\)
题解
不妨令一个二分图的权值为黑白染色方案数，即 \(2^c\)，其中 \(c\) 是连通块数。
于是我们可以求出 \(g(S)\) 表示点集为 \(S\) 时所有二分图的权值之和。
接下来我们考虑求出 \(f(S)\) 表示点集为 \(S\) 时所有连通二分图的权值之和。
考虑用所有二分图的权值之和减去不连通的二分图权值之和。令 \(x\) 为 \(S\) 中任意一个点。考虑枚举 \(x\) 所在的连通块 \(T\)，那么权值之和即为 \(f(T)g(S-T)\)。
时间复杂度 \(O(2^NM+3^N)\)。
