10-30 题
Joke - 题目 - QOJ.ac
先把 \(q\) 按照 \(p\) 排序，这样不会影响答案。
先假设我们已知所有的 \(q_i\)，怎么求合法 \(s\) 的方案数。考虑把 \((i,q_i)\) 画到二维平面上，那么我们可以画一条不降的折线表示 \(a_{1,i}\) 的取值，此时折线下方的点 \(s_i=1\)，上方的点 \(s_i=0\)。
可以对本质不同的折线计数，我们先把折线的顶点都取到给定的点上。相当于要选出一个点集使得存在一条折线分割这个点集与它的补集，问有多少种选法。考虑到若一个点被选，那么它右下角的点都要被选，所以两条折线不同当且仅当前缀严格最大值的位置集合不同。
折线的顶点现在只能选到前缀严格最大值，所以转化成了求 \(q_i\) 上升子序列的个数。
加入 \(q_i=0\) 的情况，可以 DP，设 \(f_{i,j,k}\) 表示前缀最大值为 \(j\)，且折线上选了 \(k\) 个 \(q_i=0\) 的点。转移容易做到 \(O(n^4)\)。
\(k\)-coloring - 题目 - QOJ.ac
\(k=1\) 的情况是跑欧拉路径，当且仅当有 \(0\) 个或 \(2\) 个奇度数点时存在欧拉路径。
\(k=2\) 的情况，找出任意一棵 DFS 树，对于树边发现直接走就是对的（路径即欧拉序），考虑到还要返祖边，只要来回跳一次返祖边即可。
\(k=3\) 的情况，如果我们已经求出了 \(k=2\) 的路径为 \([a_1,a_2,a_3,a_4,a_5,a_6\dots]\)，那么我们可以执行以下策略：\(a_1\to a_2\to a_3\to a_2\to a_3\to a_4\to a_5\)，此时 \(a_5\) 当成 \(a_1\) 反复执行相同策略。
对 \(k>3\) 的情况，可以在每次走边前反复跳就可以归约到 \(k-2\) 的问题。
因此这道题对于 \(k>1\) 的情况都是一定有解的。
Permutation Recovery - 题目 - QOJ.ac
考虑一个排列建边 \(i\to p_i\)，那么发现逆排列中就会有 \(p_i\to i\) 这条边。
因此对 \(j\to a_{i,j}\) 连边，然后把所有相反的边两两组成无向边。发现此时只要找出 \(k\) 组 \(n\) 的置换环即可。
考虑给每条边定向，可以跑一遍欧拉回路。对于一条边 \(u\to v\) 我们在左部点 \(u\) 和右部点 \(v\) 之间连一条边，转化为二分图匹配问题，要求划分出 \(k\) 对完美匹配。
这叫做正则二分图匹配问题，方法就是每次找到一组完美匹配，然后把匹配边全部删掉（一定要删掉而不能保留反向边），不断做这个过程。证明依靠 Hall 定理。
Excluded Min - 题目 - QOJ.ac
Mex 可以为 \(x\) 当且仅当小于等于 \(x-1\) 的数至少有 \(x\) 个。我们要找到最大的 \(x\)。
要注意 \(x\) 不可二分。
考虑从大到小扫描 \(x\)，维护 \(cnt-x\) 的最值，每次把满足 \(cnt-x\ge0\) 的区间拿出来删掉。难点就在如何对一堆特定区间做加法操作。
注意到若 \(a\) 区间包含 \(b\) 区间，那么 \(a\) 的答案比 \(b\) 的大。考虑只保留极大的区间，这样区间的 \(l\) 是递增的，每次做加法操作都是对一个区间。
考虑删掉区间 \(i\) 后加入哪些极大区间，找到被删区间的前驱和后继，那么要找到 \([l_i,l_{nxt}-1]\) 内右端点最大（相同则选取左端点更小的）的区间，若右端点大于 \(r_{pre}\) 则可以加入。加入后将 \(l_{nxt}\) 置为新加入的区间的 \(l\) 然后不断加入。
用线段树做，复杂度 \(O((q+n)\log n)\)。
Angle Beats 2.0 - 题目 - QOJ.ac
一个 \(L\) 形可以被表示为：在上下和左右各取一个点。
考虑建图，上下连一条边，左右连一条边，现在要对每条边选出一个端点，选出的端点不交。那么 Center 要连自环表示必选。
考虑到每个连通块的贡献是独立的，对于一个连通块，显然满足 \(m\ge n-1\)。
\(m>n\) 则无解；若 \(m=n\) 则是基环树，当有自环时贡献为 \(1\) 否则为 \(2\)；当 \(m=n-1\) 时考虑有一个点必定不被选，枚举这个点，从这个点开始就能确定所有边的选法，因此贡献为点数。
答案就是所有连通块的贡献乘积。
Juggler's Trick - 题目 - QOJ.ac
考虑一个串什么时候能被删空。结论：充要为长度为 \(r+b\) 的倍数且，\(R,B\) 的个数之比等于 \(r:b\)。
证明：
考虑把串每 \(r+b\) 个分段，那么一定存在两段使得一个段 \(R\) 的个数大于等于 \(r\)，另一个段 \(R\) 的个数小于等于 \(R\)。考虑从一个段增量移动到令一个段的过程中，由于 \(R\) 的个数每次只会增减一，所以一定有一个时刻使得 \(R\) 的个数为 \(r\)，这个时刻的段则可以被操作。不断操作即可。
考虑 DP，设 \(f_i\) 表示考虑完前 \(i\) 个数最多能执行的操作数。每次枚举 \(i\) 结尾的删空的一段，可以做到 \(O(n^2)\)。
考虑每个 \(R\) 写一个 \(-b\)，每个 \(B\) 写一个 \(r\)，然后对于 \(W\) 一种序列全部写 \(-b\)，另一种全部写 \(r\)，那么求这两种序列的前缀和 \(u_i,v_i\)。此时 \(j\) 能转移到 \(i\) 当且仅当 \(u_i-u_j\le 0\le v_i-v_j\) 且 \(r+b \mid i-j\)。CDQ 分治优化即可。
Maximal Subsequence - 题目 - QOJ.ac
每个结束点求出 LIS \(f_i\)，然后给 \(j<i \land f_j+1=f_i\) 的 \(j,i\) 连边，那么我们要找到 \(f_i=1\) 到 \(f_i=L\) 的最小割。
转化为求最大流，要选出最多的最长上升子序列。
把一条最长上升子序列在坐标系上连起来，选出的两个最长上升子序列的连线是不交的。
先把所有点按照 \(f_i\) 分层，对于同一层的点的 \(a\) 一定是递减的。每次取出每层的第一个点组成一个 LIS，把这些点删掉，然后把不属于 LIS 的点也删掉，被删掉的点一定是每层的开头一段。check 一个点是否属于一个 LIS 需要看下一层的第一个点是否大于它，且上一层要有点在其之前。用 vector 维护每层的点即可。
复杂度 \(O(n\log n)\)。