换种方式来写。
XXII Open Cup，Korea：
A. Automatic Sprayer 2
这个构造场上过的不少，但是真实难度并不低。
考虑如果我们能解出每一行，每一列的和 \(r/c\)。那么根据一定有解这个事实，我们一定能构造出一个合法的矩阵，考虑以下的网络流模型：
建立二分图，左行右列。然后 \(s\) 连向所有行容量 \(r\)，所有列连向 \(t\) 容量 \(c\)。任意行连向任意列容量均为 \(\infty\)。
则一组最大流就对应了一个矩阵的方案。显然贪心地流即可，换言之：
for i in [1,n] :
rest = r[i]
for j in [1,m] :
ans[i][j] = min(rest,c[j])
c[j] -= ans[i][j],rest -= ans[i][j]
总可以构造出合法解。
现在压力来到如何求 \(r/c\)。
一个错误的方向是：尝试变成一维的情况然后求解。但是如果仔细思考以下，会发现 \(r,c\) 根本就不能独立变成一维情况。
考虑到我们拥有方程： \(b_{x,y} = \sum_{i}r_i\times |x-i| + c_i\times |y-i|\)。还有方程 \(\sum r = \sum c\)。结合起来的话，我们暴力高斯消元肯定是能解出 \(r,c\) 的，问题就是不够快。因此考虑利用前面这部分方程来快速消元。
注意到 \(b_{x,y}\) 和 \(b_{x+1,y}\) 的话，\(c_i\) 这部分的贡献完全一致，而考察 \(r_i\) 的贡献，形如 \(,...2,1,0,1,2,...,\)。事实上如果我们把 \(b_{x,y}\) 减去 \(b_{x+1,y}\)，会发现得到的 \(r_i\) 贡献的序列长成 \(-1,,...,-1,1,...,1\) 这样。而如果我们再把 \(b_{x-1,y}\) 和 \(b_{x,y}\) 减去，那么这两个序列只在 \(r_x\) 的贡献上有差异：前者系数为 \(-1\)，后者系数为 \(1\)。
因此我们两个差相减后再除二就得到了 \(r_x\)。形式化地：\(r_x = \frac{(b_{x,y}-b_{x+1,y}) - (b_{x-1,y}-b_{x,y})}{-2}\)，这里 \(y\) 可以任取。类似我们能解出 \(c_y\)。
但是发现一个很关键的问题：就是我们要用到 \(b_{x-1}\) 和 \(b_{x+1}\)。所以事实上我们只能算出 \(r_{2\sim n-1}\)，还有 \(c_{2\sim n-1}\)。对于 \(r_1,r_n,c_1,c_n\) 我们还需要其它的计算方式。
由于这个时候只有四个未知数了，也许直接跑高斯消元就可以了，但这样也太麻烦了。我们考虑找到一个四元方程组然后取之。观察 \(n^2\) 个元素对应的方程组：发现大部分方程里四个未知量都出现。但是有时候，比如 \(x=1/n\) 或者 \(y=1/n\) 的时候，就会少出现一些未知量。比如 \(b_{n,n}\) 的方程里没有 \(r_n\) 和 \(c_n\)。那我们就可以得到一个二元方程组：\(k_1 r_1 + k_2 c_1 = b\)。事实上注意到 \((n-1)(r_1+c_1) = b_{n,n} - \sum_{i=2}^{n-1}(r_i+c_i)\times (n-i)\)，所以我们直接得到了 \(r_1\) 和 \(c_1\) 的和。
类似地其实 \(r_1+c_n\)，\(r_n+c_1\)，还有 \(r_n+c_n\) 的和都可以求出。问题是这四个方程不是线性无关的。此时用上 \(\sum r = \sum c\) 作为第四个方程即可。这里需要手动模拟一下消元，但会比最开始暴力跑高斯消元方便很多（那样的话矩阵元素还会变成实数）。
这样我们就在 \(O(n^2)\) 的时间内解决了本题。
B. Cilantro
这道题没有那么难想，但是思维含量也并不低，场上的数据也印证了这点。
首先发现一件事情：只要 \(a\) 序列和 \(b\) 序列的 \(1\) 个数相等，则我们一定能找到一种 \(a\) 的出入栈方式使得其等于 \(b\)。构造方式也非常容易，我们贪心扫描即可，每次先尝试取出栈顶元素，如果不行，再考虑当前的 \(a_i\)，然后决定是压入栈中还是直接弹出即可。
既然这样，我们能让 \(a_i\) 第一个被弹出的话，一个必要条件是 \(a_i = b_1\)。然后我们考虑 \(a_{1},a_{2},...,a_{i-1}\) 此时是依次位于栈中的。而后面 \(\gt i\) 的部分可以拼出任意序列的话。此时有一个错误的想法：就是我们尝试在 \(b[2,n]\) 中找到一个 \(a_{i-1},a_{i-2},...,a_{1}\) 的子序列，则有解等价于能找到这样一个子序列。
但这实质上有问题，因为我们并不能完全自由的安排 \(a_{i-1},a_{i-2},...,a_{1}\) 的出现：假如我们在一个时刻想要把 \(a_{i-1}\) 扔出来，那 \(\gt i\) 的元素就不能有人留在栈中，对于更前面的元素也是同理的。
如果我们能让 \(a\) 中 \(\gt i\) 的部分的 \([x,y]\) 段和 \(b\) 中的 \([l,r]\) 匹配，那么我们就可以从 \(\lt i\) 的那些 \(a\) 里抽一个连续段出来，依次和 \(b_{r+1},b_{r+2},...,\) 去匹配，显然我们也只能在这些时刻把 \(a_{1},a_{2},...,a_{i-1}\) 拉出去和 \(b\) 匹配。
因此考虑这样一个贪心：我们从小到大枚举 \(i\) 的时候，维护两个指针 \(l,r\)，初始 \(l=r=n\)。当我们的 \(i\) 从 \(j\) 变到 \(k\) 的时候，我们就需要把 \(a[j,k)\) 依次和 \(\lt r\) 的位置匹配上。所以我们依次考虑 \(a_j,a_{j+1},...,a_{k-1}\) 的匹配位置。如果 \(a_j = b_{r}\)，那么我们直接把两者匹配上就行。否则 \(b_{r}\) 就是去和 \(a_l\) 匹配的：我们不断向前同时缩小 \(l,r\)，直到 \(a\) 这部分的 \(1\) 和 \(b\) 这部分的 \(1\) 个数相同即可。然后这个时候我们重新尝试把 \(a_j\) 和 \(a_{r-1}\) 匹配，如果还是不行，那就继续缩减 \(l,r\)。直到说 \(l\lt i\) 或者 \(r=i\) 了为止。
这样我们就在 \(O(n)\) 的时间内解决了这个问题。
E. Goose Coins
算是一道中规中矩的题。
看上去这么恐怖的背包一定是需要挖掘性质：注意 \(c_i\) 总是 \(c_{i-1}\) 的倍数，这启发我们把状态看作一个数，第 \(i\) 位（其中 \(i\lt n\) ）始终不超过 \(\lt c_{i+1}/c_{i})\)，然后最高位可以取任意值。
这样我们得到的实质上是花费硬币最小的解：考虑利用数位 dp 的思想，从高维开始把一些大数位（也就是面值大的硬币）分解为更小的硬币向下推。
只考虑最大值，显然最小值没有区别。令 \(dp(i,x,y)\) 表示考虑了 \(\gt i\) 的数位，然后一共选了 \(x\) 个硬币，我们向第 \(i\) 位传递了 \(y\) 枚硬币过去，此时的最大答案。那么暴力枚举转移，也就是枚举第 \(i\) 位保留了多少枚硬币，这是 \(O(k)\) 的。这样这个 dp 就是 \(O(nk^3)\) 显然无法通过。
当然这其实犯蠢了，我们转移的时候直接讨论是否保留至少一个硬币，如果是，则转移到 \(dp(i,x+1,y-1)\)，否则直接全部扔给 \(i-1\) 就行了。也就是在做类似完全背包的那个复杂度优化。这样时间复杂度 \(O(nk^2)\) 可以通过。
G. Lamb's Respite
最开始没有过的时候觉得它很恶心，最后发现其实是存在很好的实现方法的。
首先有经验的话会发现这个题目非常像 IOI2021 分糖果这道题，区别是这里碰到 \(0\) 就直接死了，那么感觉会方便一些。很显然分成三段来讨论：中间那段是锁血的，那我等价于判断是不是有一次碰到了这个界，如果是的话直到锁血结束血量都是 \(\lceil \frac{H}{10} \rceil\)，和第一/三段里碰到 \(0\) 就死是类似的。
先来考察第一段里如何判断是否碰到 \(0\)：发现等价于有一个连续段的 \(\sum a\) 是 \(\le -H\) 的，必要性和充分性都很好说明，那我们求的就是区间最小子段和。如果没有碰到过 \(0\)：考虑全局最大前缀和所在的位置 \(p\)（我们把时刻 \(0\) 也考虑进去），如果有多个就考虑后面那个。显然时刻 \(p\) 我们的血量 \(=H\) 且后续不再有顶到 \(H\) 的情况。因此 \(sum-sum_{p}\) 就是血量的下降值（这里 \(sum\) 是 \(a\) 的前缀和）。所以我们还要支持求最大前缀和的值。
发现后面两段有点小问题，就是初始生命值不是 \(H\) 了：这里有一步很妙的事情，就是我们不妨认为初始生命值是 \(H\)，然后在开始前额外遭受了一次攻击。这样我们就不需要再去考虑任何多的事情了！
上述的信息都可以直接用线段树维护，时间复杂度 \(O(n+q\log n)\)。
K. Three Competitions
场上差一点通过了，有点可惜。
首先会发现根据抽屉原理任意两个人之间总有一个人能击败另一个人，所以这是个竞赛图。
竞赛图两点可达性，考虑利用其缩点后是链的性质，只要能快速缩点即可。
根据兰道定理，按照出度升序排序后，所有 \(sum_i = \dbinom{i}{2}\) 的位置划分开，就对应了链上的一个节点。
所以问题变成求每个点的出度。
场上有点急，写了个 bitset 没过。冷静一下我们发现其实就是三次二维数点减去一次三维数点就好了。时间复杂度 \(O(n\log^2n + q)\)，其实这种情况的三维数点能 \(O(n\log n)\) 但意义不大。
CCPC Online 2023
C. Clique Challenge
很神的题！第一次知道可以解决 \(m\le 1000\) 的无向图最大团和团数目（最大团数目也可以）的算法，并且没有用到任何科技。
考虑把点按照度数排序然后重标号。则一个人向标号更大的点最多只有 \(\sqrt{2m}\) 个点连边。
那么我们枚举标号最小的点，这样就只有 \(v=\sqrt{2m}\) 个点和它有连边，我们考虑这 \(v\) 个点的团数目即可。
注意到 \(v\le 44\)，考虑折半。那么假设左边的点集是 \(S\)，右边的是 \(T\)。我们枚举 \(S\) 后可以求出 \(X\) 表示说右边的点，\(X\) 内的点和 \(S\) 的每个点都有连边。那么我们就只用知道 \(X\) 子集内有多少个合法的 \(T\)，直接高维前缀和一下即可。令 \(v:=\frac{v}{2}\) 我们就在 \(O(v2^{v})\) 的时间内解决了这个问题，常数很小。
最坏情况下有 \(\sqrt m\) 个 \(v=\sqrt{2m}\) 的点，所以这个算法的最坏复杂度是 \(O(m\times 2^{\sqrt{2m}})\) 的，但是远远跑不满，且常数非常小。事实上还存在 \(O(2^v)\) 解决一个点的情况的算法？所以复杂度能做到更优来着。
G.GCD of Pattern Matching
如果不是场上过了非常多我就放弃了，最后才做出来（
先考虑我们枚举一个 \(p\) 然后检查是否能让所有数都是 \(p\) 的倍数。
考虑如果我们确定了使用哪些数码，那我们随意找一个方式填进去，然后我们发现用交换操作能得到所有这个数码构成的数。则交换前和交换后都要是 \(p\) 的倍数，那你考虑假设我们交换前的位权和分别是 \(a,b\)。然后数字差为 \(c\)，那么就要求 \((a-b)\times c\) 是 \(p\) 的倍数。事实上我们总能让 \(c=1\)，所以就要求 \((a-b)\) 是 \(p\) 的倍数。
那么我们把初始的那个值和所有 \(a-b\) 去取 \(\gcd\) 就好了。
不过有点小问题：注意到最高位不能为 \(0\)，所以当 \(m=2\) 的时候最高位那个类只能填 \(1\)，没有人能和他换。
然后 \(\Sigma = m\) 的情况就做完了，因为字符集是确定的，但是 \(\Sigma \lt m\) 的时候怎么办？
alpha 提出了一个转化：我们搞一个中转站，初始的时候我们随便选 \(\Sigma\) 个数码填好，把剩下的 \(m-\Sigma\) 个数码扔进中转站。然后我们除了互换两个等价类的数码以外，还多了一个操作：选择一个等价类，然后把中转站的某个数码换出来，再把本来的数码换进中转站。如果位权和为 \(a\)，且数字差为 \(c\)，则我们就需要让 \(a\times c\) 是 \(p\) 的倍数。类似地我们总能让 \(c=1\)，除了 \(m=2\) 的时候最高位的等价类固定为 \(1\)。因此我们只需要把答案再和每个位置的位权和取 \(\gcd\) 即可。
这样的话有 \(O(\Sigma^2)\) 次取 \(\gcd\) 操作：唯一瓶颈在于第一部分里，我们对于两两等价类的位权和的差，把他们求 \(gcd\)。也就是有 \(a_1,a_2,...,a_k\)，要求两两差的 \(\gcd\)。其实我们求 \(a_1\) 和其他人的 \(\gcd\) 就好了，这样只有 \(O(\Sigma)\) 次求 \(\gcd\) 操作，即可通过。
H. Hurricane
过的反而比 G 少很多，真是奇妙。
容易想到：枚举一个点 \(u\)，考虑其邻点集合 \(S\) 以外的点，到他的距离都是 \(1\)。
那么对于一个 \(v\in S\)，什么时候 \(dis(u,v)=2\)？当且仅当存在一个点 \(w\) 使得 \((u,w)\) 和 \((v,w)\) 之间都没有连边。
发现如果说 \(dis(u,v) \gt 2\)，那么意味着两个人里有一个人的 \(deg\) 要大于等于 \(\lceil \frac{n}{2} \rceil\)。而这样的点只有 \(O(\frac{m}{n}) = O(\sqrt m)\) 个。
因此我们对这些点特殊处理，跑一下 bfs 即可，可以用并查集做到 \(O((n+m)\log)\)，当然这个 \(\log\) 非常小，其实补图最短路还有严格的 \(O(n+m)\) 做法，因此这个题可以做到 \(O((n+m)\sqrt m)\) 的复杂度。