A. Ladder
题意：给出 \(n\) 个木棍，长度分别为 \(d_1,d_2,\dots,d_n\)。你需要 \(k+2\) 个木棍，其中两个长度恰好为 \(x\)，\(k\) 个长度恰好为 \(y\)。你可以削断已有的木棍，求是否可能。
\(1 \le n \le 10^5, 0 \le k \le 10^5, 1 \le x, y \le 10^9, 1 \le d_i \le 10^9\)
题解：求出 \(cx\) 和 \(cy\) 分别表示有多少木棍长度大于等于 \(x\) 或者 \(y\)，然后根据 \(x\) 和 \(y\) 的大小判一判即可。
B. 36 Puzzle
题意：有一个 \(6 \times 6\) 的格子，依次填满了 a-z0-9 这 \(36\) 个字符。你希望将它排好序，每次可以选一行或者一列循环位移若干个单位。构造一个操作顺序。
题解：可以发现如果我们能够实现交换相邻两个格子的话，那么就可以不断通过交换两个格子来达成目的。
考虑交换 \((i,j)\) 和 \((i,j+1)\)，可以发现只需要对格子 \((i,j)\) 执行 ULURULURULURU 就可以达成目的。类似的，如果要交换 \((i,j)\) 和 \((i+1,j)\) 的话，只需要对格子 \((i,j)\) 不断执行 LULRLULRLULRL 即可。
C. Message
题意：有一个 \(b\) 进制数的编码，数字 \(i\) (\(1 \le i \le b - 1\)) 的编码为 \(s_i\)。现在给出一个长度为 \(n\) 的字符串，你需要找到里面一个最大的 \(b\) 进制数。
\(3 \le b \le 50000, \sum |s_i| \le 500000, 1 \le n \le 300000\)
题解：由于要求这个数最大，那么首先是要长度最长，之后再是字典序最大。
先考虑长度最长，那么我们可以对 \(s_i\) 倒着建立 AC 自动机，然后令 \(dp(i)\) 表示以 \(i\) 开始的后缀最多能够多长。显然，只需要倒着在AC自动机走一遍，每次求出长度最短的匹配串即可。做完这一步之后，可以发现 \(dp(1) \ge dp(2) \ge \dots \ge dp(n)\)。
接下来考虑字典序最大，对于第一位，我们知道它的起始位置只能在那些 \(dp(i)=dp(1)\) 的 \(i\) 上，结束为止最晚可以在 \(dp(i)=dp(1)-1\) 的位置上。于是我们把 \(s_i\) 按照正着建立 AC 自动机，把 \(dp(i)=dp(1)\) 或者 \(dp(i)=dp(1)-1\) 的位置拿出来在自动机走，找到一个数字最大的串即可。之后我们就可以把这个前缀去掉，考虑下一位，按照上面方法搞即可。
可以发现，每个位置 \(i\) 只会最多被用两次，因此整个算法是线性的。
D. Arithmetic Sequences
题意：给出 \(n\) 个数，\(a_1,a_2,\dots,a_n\)，你需要找到一个最长的等差子序列。
\(1 \le n \le 2000, 0 \le a_i \le 10^9\)
题解：先给所有数排序。考虑枚举公差 \(d\)，那么对于 \(i < j\) 并且 \(a_i + d = a_j\) 的，构建一条从 \(i\) 到 \(j\) 的有向边。这个DAG的最长路就是 \(d\) 对应的答案。
复杂度\(O(n^2)\)。
E. Subsequence
题意：给出 \(n\) 个数 \(a_1,a_2,\dots,a_n\)，求出它的一个最短的maximal nondecreasing subsequence。
\(1 \le n \le 10^6, 0 \le a_i \le 10^6\)
题解：应该是这个论文 Finding Shortest Maximal Increasing Subsequences and Domination in Permutation Graphs，但是复杂度是 \(O(n \log^2 n)\) 的，过不了。
首先，我们可以令 \(a_i = a_i \cdot n + i\)，使得任意数都互不相同。考虑论文里的转移方程，令 \(dp(i)\) 表示以 \(i\) 结尾的 Maximal Increasing Subsequences 的最短长度。把 \((i,a_i)\) 看成二维平面上的点，那么把所有 \(x < i, y < a_i\) 的点 \((x, y)\) 都拿出来，然后考虑那些处于边界上的点 \((x, y)\) 们，\(dp(i)\) 的值就是 \(dp(x)\) 的最小值加上 \(1\)。
用分治来优化这个dp，假设当前区间是 \([l, r)\)，令 \(m=\frac{l+r}{2}\)，求出 \(i \in [l, m)\) 里所有 \(dp(i)\) 值，对 \(j \in [m, r)\) 里 \(dp(j)\) 值的贡献。
把 \([l, r)\) 里的所有位置按照 \(a_i\) 从小到大排序。可以发现，对于 \([l,m)\) 里的点，需要维护一个 \(x\) 递增，\(y\) 递减的序列 \(A\)。对于 \([m, r)\) 里的点，也需要维护一个 \(x\) 递增，\(y\) 递增的序列 \(B\)，并且这个序列按照 \(y\) 坐标会把 \(A\) 序列切成一块块的。那么 \([l, m)\) 里所有 dp 值对某个 \([m, r)\) 里 \(dp(i)\) 的贡献，就是对应那一份 dp 值的最小值加 \(1\)。
我们可以用一个单调栈套单调队列的数据结构来维护，第一层单调栈维护序列 \(B\)，第二层维护切出来的每一块 \(A\)，每一块从队尾到队首仅保留 dp 值变小的那些。
- 加入一个 \([l.m)\) 的点的时候，我们需要把 \(A\) 序列里面不合法的点都弹栈，然后把这个点加进去。加进去的时候需要考虑栈顶属不属于新切出来的一个块，如果不是，这个点需要单独成为一个块。
- 加入一个 \([m,r)\) 的点的时候，可能会弹走 \(B\) 序列里一些点，这个时候会发生 \(A\) 里某些块的合并，只要保证从队尾到队首的 dp 值的性质即可。最后考虑栈顶这个块，看看是不是一个新块，如果是的话用最小值加 \(1\) 更新下 dp 值即可。
预先处理好归并树的话，复杂度就是 \(O(n \log n)\) 的。
F. Algebra is Awesome
题意：对于一个排列 \(\sigma\)，定义 \(D(\sigma)=\{\sigma^k: k \in \mathrm{N}\}\)。
现在给出 \(m\) 个长度为 \(n\) 的排列 \(\sigma_1,\sigma_2,\dots,\sigma_m\)。对于每个 \(i\)，求出有多少 \(j\) 满足 \(j < i\) 并且 \(D(\sigma_i)=D(\sigma_j)\)。
\(1 \le n \le 100, 1 \le m \le 10^4\)
题解：对于每个 \(S(\sigma_i)\)，我们需要找个一个字典序最小的 \(p_i\)，使得 \(S(p_i)=S(\sigma_i)\)。
考虑将排列环分解，并且按照最小元素的大小将所有环排好序，假设环长依次为 \(n_1,n_2,\dots,n_m\)。考虑第一个环，我们需要找个一个 \(s_1\)，使得 \(\gcd(s_1,n_1)=1\)，并且 \(s_1\) 对应的环上元素要是最小的。
在这个基础上，我们考虑第二个环，同样也得找一个 \(s_2\)，满足\(\gcd(s_2,n_2)=1\)，并且 \(s_2\) 对应的环上元素要是最小的。
依次类推，可以得到 \(m\) 个同余方程组
\[\begin{array}{c} x \equiv s_1 \pmod {n_1} \\ x \equiv s_2 \pmod {n_2} \\ \cdots \\ x \equiv s_m \pmod {n_m} \end{array} \]
我们在保证方程有解的情况下，依次确定每一个 \(s_i\) 即可。方程有解当且仅当对于任意的 \(i\) 和 \(j\) 都有 \(s_i \equiv s_j \pmod{\gcd(n_i,n_j)}\)。
G. Bus Lines
题意：给出一棵 \(n\) 个点的树，第 \(i\) 条边连接 \(a_i\) 个 \(b_i\)，最多被使用 \(c_i\) 次。
你需要找出最多的路径数目，使得起点和终点都是叶子，每条边使用次数不能超。
\(2 \le n \le 10^5, 1 \le a_i, b_i \le n, 1 \le c_i \le 10^6\)
题解：随便找一个非叶子节点作为根节点，然后考虑从叶子开始往上贪心。对于每个点 \(u\)，维护 \((up_u, free_u)\) 表示这个点能够往上提供多少条边，以及在这些提供的边中，可以在 \(u\) 的子树内自由匹配成 \(free_u\) 对。
考虑 \(u\) 的父亲 \(p\)，以及他们之间的容量限制 \(w\)。显然如果 \(up_u \le w\)，不需要做任何事情；否则，我们需要舍弃部分 \(up_u\)。为了最大化，不妨可以先用 \(free_u\) 消耗掉一部分 \(up_u\)，直到 \(up_u \le w\) 或者 \(free_u\) 等于 \(0\) 为止。也就是说 \(\min(\lceil \frac{w-up_u}{2} \rceil, free_u)\) 这些一定对答案产生贡献，可以直接计入答案里。
那么接下来怎么合并 \(u\) 的儿子的结果到 \(u\) 里来，考虑 \(u\) 只有两个儿子 \(v_1\) 和 \(v_2\)。令 \(x=\min(up_{v_1},up_{v_2})\)，显然我们可以将这 \(2x\) 配对下，然后将剩下来的留给 \(v_1\) 或者 \(v_2\) 自己的子树去配对。也就是说
\[up_u = up_{v_1}+up_{v_2} \]
\[free_u=x+\min(\lfloor \frac{up_{v_1}-2x}{2} \rfloor, free_{v_1})+\min(\lfloor \frac{up_{v_2}-2x}{2} \rfloor, free_{v_2}) \]
由于一些奇偶性的问题，还需要考虑 \(x=\min(up_{v_1},up_{v_2})-1\) 是否会更优。
如果超过 \(2\) 个儿子的话，可以两个两个合并计算。
最后答案就是 \(\min(\lceil \frac{w-up_u}{2} \rceil, free_u)\) 的贡献和加上 \(free_{root}\)。
H. Coal Mine
题意：有一个 \(n \times m\) 的格子，你需要给每个格子标上 \(1\) 到 \(k\)。使得所有标号为 \(i\) 的格子关于位置 \((x_i,y_i)\) 中心对称。坐标 \((x_i,y_i)\) 一定在某条格子边的中点。
\(1 \le nm \le 1500, 1 \le k \le 100\)
题解：把所有格子黑白染色，可以发现中心对称的一对格子一定一黑一白。于是把中心对称的格子建立一条边，搞出一个二分图。直接跑最大匹配即可。
I. Chocolate is Tasty
题意：有一块 \(n \times m\) 的巧克力，有若干个小孩围成圆桌。每个男孩会选择巧克力较长的边切下一条，每个女孩会选择巧克力较短的边切下一条。
给出一个字符串 \(s\)，表示每个小孩是男的还是女的，求出从哪个人开始分巧克力，才能使得最多人能够吃到巧克力。
\(1 \le n, m \le 10^6, 1 \le |s| \le 10^6\)
题解：维护长边减去短边的差，对于男孩显然是 \(+1\)，对于女孩是 \(-1\)。那么一段字符串可以看成一个折线，不妨把这段折线的最低点放在 \(x\) 轴上，然后维护折线最左端和最右端的高度 \(L\) 和 \(R\)。考虑一个 \(n \times m\) (\(n \ge m\)) 的巧克力要经过这段折线，我们想要求出最后这块巧克力会变成什么样。
令 \(d=n-m\)。显然，如果 \(d \ge L\)，我们仅需要把折线整体往上移动 \(d-L\) 即可。那么最终 \(R+d-L\) 就是巧克力长边减短边的差。我们可以列出方程
\[\begin{array}{c} n^\prime+m^\prime=n+m-S, \\ n^\prime-m^\prime=R+d-L \end{array} \]
其中 \(S\) 是折线的段数。那么就可以解出最终巧克力的边长。
如果 \(d < L\)，可能会有操作导致长短边交换，不太能够直接列出方程。但是可以发现只和 \(L-d\) 的奇偶性有关，如果是偶数那么最终差为 \(R\)，否则为 \(R+1\)。因此我们也可以类似的列出一个方程求出边长。
显然，当边长都是正整数的时候，我们呢可以继续操作，否则就终止了。至此，我们有了一一个 \(O(1)\) 判定的方法。
接下来就可以双指针维护极大的合法区间，还需要一个单调队列维护区间最小值。
J. Game
题意：有一个长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\)。两个人轮流玩游戏，每次可以删掉左边的数或者右边的数。
有 \(k\) 个终止序列，第 \(i\) 个序列长度为 \(m_i\)。一旦操作出一个终止序列，那么这个人赢了。求出最优策略下，是先手必胜还是后手必胜。
\(1 \le n \le 10^6, 0 \le a_i, w_i \le 10^9, \sum m_i \le 3 \times 10^6\)
题解：令 \(win(l,r)\) 表示 \(a[l..r]\) 从这个子串开始，先手能否必胜。分以下几种情况考虑：
- \(a[l..r]\) 本身就是终止序列，那么先手肯定必败
- \(a[l+1..r]\) 或者 \(a[l..r-1]\) 是终止序列，那么先手只要操作一下就必胜了
- \(a[l+2..r]\) 是终止序列，那么先手肯定不会去取 \(a[l]\)，所以和 \(win(l,r-1)\) 的状态有关
- \(a[l..r-2]\) 是终止序列，类似的，先手肯定不会取 \(a[r]\)，所以和 \(win(l+1,r)\) 的状态有关
- \(a[l+1..r-1]\) 是终止序列，显然不管先手怎么操作，后手总是能够必胜的
- \(a[l+2..r-1]\) 或者 \(a[l+1..r-2]\) 是终止序列，先手肯定能必胜，可以对于前者拿掉 \(a[l]\)，后者拿掉 \(a[r]\)
- 对于剩下的其他情况，必然有 \(win(l,r)=win(l+1,r-1)\)。因为
- 如果 \(win(l+1,r-1)\) 是必败的，那么显然 \(win(l,r)\) 也是必败的
- 如果 \(win(l+1,r-1)\) 是必胜的，那么有 \(win(l+2,r-1)\) 或者 \(win(l+1,r-2)\) 是必败的。对于前者，先手可以拿掉 \(a[l]\)，那么无论后手怎么操作，都会到达状态 \(win(l+2,r-1)\)。后者也是类似的。
因此直接按照上面的情况考虑即可。复杂度是 \(O(n + \sum m_i)\)。
K. Tic-tac-toe
题意：给出一个 Tic-tac-toe 的局面，判断是不是两个都很聪明的人下出来的，或者其中一个很聪明的人下出来的，或者都不是。
题解：显然我们可以用一个小于 \(3^9\) 的数来表示所有局面。令 \(dp(mask)\) 表示局面 \(mask\) 是先手必胜，还是平局，还是必败。
可以发现不在 \(dp(\cdot)\) 里的局面都是不能达到的。如果两个人都是最优策略的话，结果肯定是平局。因此可以直接沿着 \(dp(\cdot)\) 数组遍历出所有合法状态。