Kto wygrał?
就是按 $(\sum,cnt_{10},cnt_{9},…,cnt_{0})$ 比较。
Liderzy
之根每种颜色的数量有关，每次选一个最多的尽可能将少的抵消即可。实现可以维护两个指针做到 $O(n)$。
还可以维护剩余数的个数，每次减去 $2 \times cnt-1$，因为只会选择少的数，所以多的数的个数不会受影响。
证明：每个集合的绝对众数一定是原本个数就最多的，所以是一段后缀。
❤ Modernizacja Bajtocji
操作一涉及两个元素，启示我们进行连边。先不考虑操作二，发现连通块只会是树或基环树，树就是有一个没有，基环树就是全都有，并查集维护即可。
加上操作二，发现树和基环树删掉一个点后都不会改变剩下的点的状态，那么建虚点即可。
🍬 Znaczki pocztowe
❤ Alchemik Bajtazar
操作是可逆的，那么可以构造一个中间状态，只需考虑如何从中间状态达到某个状态（次数限制减半）。
菊花图是极好的，可以先将需要加的边加上。再考虑删边，对于加边 $(x,y)$，可以将 $(1,x)(1,y)$ 连起来，最后得到一张新图，需要将新图上的某些点删点，满足删某个点时该点存在邻点，按 dfs 序倒序删除即可。
操作次数大概为 $2n+2m$。
❄ Grupa permutacji
不会群论。
题中置换复合形成的结果可以看成置换群的子群，有个很好的性质，对于所有能得到得排列第 $i$ 位上的值，第 $i$ 位为该值得方案数是相同的，对于多元组也成立。
证明 大概就是存在逆元，然后形成双射。
然后我们可以将所有给定的置换环的二元组 $(i,j),(p_i,p_j)$ 连边。对每个连通块，记 $a,b$ 分别为 $i
由于只需关注连通性，所以可以随机找一个子集的复合连边，随机 $O(\log n)$ 就可以了，时间复杂度 $O(n^2\log n)$。
生成子群阶数 计算生成子群元素个数。
可以先用上述方法计算 $p_1$ 的取值个数，然后计算 $p_1=1$ 的元素个数。
发现每个环都对应一个 $p_1=1$ 的置换，于是对于边 $u,v$ 加入 $1 \leadsto u \circ u \to v \circ v \leadsto 1$，用上述方法将生成元缩减到 $O(n)$ 即可。
❤ Obrazy
由于满足整除限制，所以先用最小的判是否合法，合法后贪心用最大的显然是对的，直接做是 $O(n^2)$ 的，因为两块某边的长度为 $d_i$ 的倍数，只会递归一边。
可以做到 $O(n)$，就是从小到大用正方形，每次占据的都是一个矩形。
🍬 Żelki
注意到一颗糖豆能买多次。然后跑同余最短路就行了。
❄ Splatanie ciągów
先考虑都是单调递增区间的最小稳定性，设 $|A| \ge |B|$，发现可以通过调整使得 $B$ 中元素不会出现在最长得递增区间中，那么相当于将 $|A|$ 分成 $|B|+1$ 份。
对于一般情况，记 $A$ 中极长单调区间的长度为 $a_i$，相当于将所有 $a_i$ 分成总共 $|B|+1$ 份（$B$ 同理，就是反过来）。
考虑枚举 $x$ 做，发现两种限制至少满足一个，所以可以分别统计，加起来再减总数。然后发现有用的 $a_i$ 需要满足 $a_i-2 \ge x$，于是只有 $O(\frac{n}{x})$ 段，枚举再用数据结构优化即可。时间复杂度 $O(n\log^2n)$。
Łamigłówka 3
就是每次找到可以最后一个涂的就行吧。
❄ Desant 3
Nep？！算搜索吗，感觉。
有 $O(2^nm)$ 暴力，然后特殊之处在于答案对 $2$ 取模。
感觉很难想啊，每个位置标 $1,0,-1$ 表示准备好了，没准备好，不确定。对于操作 $(x,y)$
- $a_x=a_y=-1$，$x,y$ 选择 $(0,1)/(1,0)$ 会得到同样的结果，就抵消了，所以选择 $(0,0)/(1,1)$ 递归下去。
- $a_x,a_y$ 都确定，直接模拟。
- $a_x,a_y$ 有一个不确定，发现根据确定的位置和 $0/1$，操作后只会进行交换或不变。
得到最终序列后 $O(n^2)$ 统计答案即可。
每次递归会删两个 $-1$，所以时间复杂度 $O(2^{\frac{n}{2}}(m+n^2))$。
😄 Kolorowy las 需要 LCT，我不会啊。
💔 Bardzo Ulubiony Ciąg
发现求前缀和后相当于六个点的和，可以做到 $O(n^3)$，实现就是枚举中间的区间的左端点和左边的区间，然后枚举右端点和右边的区间。有一些细节。
❤ Żarówki
不存在奇环就黑白染色，操作变为交换。存在感觉方案数是 $2^{n-1}$ 因为异或和不变。确实是，可以先将奇环上的一条边删掉，然后其他边可以使得颜色随意交换，删掉的边可以控制 $0,1$ 的数量。
❄ Kraniki
可以简单 $O(\frac{n^2}{w})$。然后发现能到达某个区间的区间是一段阶梯状的，高度最高的就是直接支配点，倍增维护。
❤ Dzielniki
这集我看过。可以先变成随机数，然后二进制按位确定，不确定就递归下去。记忆化搜索就过了。
❄ Monety
不知道怎么想到的，将极长同色后缀的元素的权值设为 $2^{m-1}$，其他元素的权值为后面元素权值的 $\frac{1}{2}$，当且仅当两个颜色的权值和相同时后手必胜，否则权值大的始终胜利。
然后数位 DP，由于是要确定一段后缀，所以再记录 $\ge 2^{m-2}$ 的数的和。
证明就是考虑权值最小的点。
❄ Autostrada 2
可以建出下图
$f(i,j)$ 即为图上 $s_i$ 到 $t_j$ 的最短路。
先考虑如何求出 $f$。$f$ 是满足四边形不等式的，即 $f(a+1,b)+f(a,b+1) \ge f(a,b)+f(a+1,b+1)$。
证明
$a+1 \leadsto b$ 与 $a \leadsto b+1$ 必然存在交点，取某个交点 $X$，有
通过四边形不等式可以得到，对于下图的点 $X$，存在一个分界点 $p_X$ 使得 $a \le p_X$ 的 $s_a$ 到 $X$ 的路径经过 $Z$，$a > p_X$ 的 $s_a$ 到 $X$ 的最短路径路径经过 $Y$。
有三种方法可以求得 $f$
分治。显然。
LCT。好像是动态维护最短路树，很可惜我并不会 LCT。
可持久化线段树
对每个点 $X$ 开一棵线段树维护 $s_i$ 到 $X$ 的最短路 $f(i,X)$。
$f(*,X)$ 来自 $f(*,Z)$ 的一段前缀和 $f(*,Y)$ 的一段后缀，用可持久化线段树维护。
查询分界点可以线段树二分。
如果某一列上的路径权值均为 $0$，那么可以将该列整体删除。考虑先重构边权使其在满足所有 $f$ 的条件下产生尽可能多的全 $0$ 列。
考虑从下往上从左往右依次填权值，初始权值如下，这时满足了 $f(*,n)$ 的限制。
有结论，对于当前枚举到的边，在考虑了所有填过的边和 $f$ 的限制后，边权取最大值最优。
如下图，枚举到黄色的边，那么该边受到的限制来自 $f(*,t_4)$ 和 $B_i$。考虑求出 $f(*,C_1)$，那么黄色边的边权 $W = f(s_4,C_1) - f(s_4,A_2)$。
直接考虑 $f(*,C_1)$ 并不方便，将 $f(*,C_1)$ 差分得到 $g(*,C_1)$。
- 来自 $t_4$ 的限制：$g(i,C_1) \le g(i,t_4)$，证明类似四边形不等式的证明。
- 来自 $B_i$ 的限制：记 $p_{B_i}$ 为 $B_i$ 的分界点，对于 $a \le p_{B_i}$ 有 $g(a,C_1) = g(a,B_i)$。
可以用可持久化线段树维护 $g$。
需要找到分界点，找到最小的 $i$ 满足 $f(i,A_2)+W=f(i,C_1)$ 的 $i$ 即可，可以线段树二分实现。
LeafSeek orz
LCT 也是可以做的，好像是延续官解 II 做法。
类似题目：[PA 2020] Tekstówka。
- 图片来自官解。
