A - Table Tennis Training
给定位置 \(1\sim n\)，一开始有两个人在 \(a,b\)，每一次每个人可以任意向左或向右走一步，如果在边上不能越界但是可以不动，问最少多少步结束后两个人在同一个位置。\(n\leqslant 10^{18}\)。
直接枚举向中间贴（只有 \(a,b\) 奇偶性相等时才可以）还是都先向左/向右，如果奇偶性不同有个人需要等一步，三种情况取最小值即可。
B - Voting Judges
有 \(n\) 道题，一开始的评分分别是 \(a_i\)，现在有 \(m\) 个评委，每个评委可以任选恰好 \(v\) 道题将其评分 \(+1\)，最后评分前 \(p\) 大的题会被选中，问有多少题可以被选中。\(n\leqslant 10^5,m\leqslant 10^9\)。
先把 \(a\) 降序排序，前 \(p\) 个一定合法，然后考虑剩下的，设有 \(k\) 个数比 \(a_i+m\) 大，若 \(k\geqslant p\) 肯定不合法。然后考虑剩下的情况，我们发现给前 \(p-1\) 道题和后 \(n-i\) 道题怎么投都无所谓，因为我们只需要保证最后 \(a_i\geqslant a_p\)，所以我们优先给这些题投多余的票，如果没有多余的票了，那么合法；反之设每个评委还多出 \(t\) 张票，那么合法当且仅当 \(\sum\limits_{j=p}^{i-1}{a_i+m-a_j}\geqslant mt\)，这相当于每个这之间的题目还可以投 \(a_i+m-a_j\) 张票不会超过 \(a_i\)，注意到这个数一定不超过 \(m\)，所以我们只需要保证总空位不小于总票数（证明考虑我们每一次添加 \(a_i+m-a_j\) 个球，然后排成一排，分别和评委 \(1,2,\dots m,1,2,\dots m,\dots\) 对应，可以发现 \(k\) 和 \(k+m\) 对应的 \(j\) 一定不一样，也就是说同一个评委不可能在一道题上投两次）。
C - Domino Quality
用 \(1\times 2\) 的多米诺填 \(n\times n\) 的棋盘，要求覆盖了每一行和每一列的骨牌数量均相等，构造方案或输出无解，\(n\leqslant 1000\)。
不难发现 \(1,2\) 无解，手玩出 \(3-7\) 的答案，然后设 \(k=n\bmod 4\)，在左上角填 \(k+4\) 的答案，然后一直顺着对角线填 \(4\) 的答案，这样显然合法，记得特判 \(n=3\)。
D - Problem Scores
求满足以下限制的长为 \(n\) 的数列 \(A\) 的数目：\(1\leqslant A_i\leqslant n\)；\(A\) 单调不降；对任意 \(0<k<n\)，任何一个大小为 \(k+1\) 的子集和严格大于任何一个大小为 \(k\) 的子集和。\(n\leqslant 5000\)。
日常不会套路题。我们可以发现，当前 \(\lfloor\dfrac{n+1}{2}\rfloor\) 个题的分数大于后 \(\lfloor\dfrac{n}{2}\rfloor\) 个题的分数时这个序列合法（因为这个限制最紧，证明考虑任意删除两个元素）。考虑对原序列的差分序列 \(C\) 计数，特殊的，我们这里令 \(C_0=1\)，则 \(\sum C_i<n\)。若 \(n\) 为奇数，我们把限制条件列出来，则有（为了方便以下均省略下取整符号）： \[ \begin{aligned} \sum\limits_{i=1}^{\frac{n+1}{2}}\sum\limits_{j=0}^iC_j&>\sum\limits_{i=\frac{n+1}{2}+1}^n\sum\limits_{j=0}^iC_j\\ 2\sum\limits_{i=1}^{\frac{n+1}{2}}\sum\limits_{j=1}^iC_j&\geqslant\sum\limits_{i=1}^n\sum\limits_{j=1}^iC_j\\ 2\sum\limits_{i=1}^{\frac{n+1}{2}}(\frac{n+1}{2}+1-i)C_i&\geqslant \sum\limits_{i=1}^n(n+1-i)C_i \end{aligned} \] 对 \(n\) 为偶数的情况也类似地推下式子，最后我们有 \[ \sum\limits_{i=1}^nB_iC_i\leqslant 0 \] 其中 \[ \begin{equation} B_i= \begin{cases} i-2 &i\leqslant \frac{n}{2}+1\\ n-i+1 &\text{otherwise} \end{cases} \end{equation} \] 注意到由于原序列单调不降，故 \(C_i\geqslant 0\)，注意到只有 \(B_1\) 为负，所以我们考虑最后确定 \(C_1\) 的值，列出对 \(C_1\) 的所有限制可得： \[ C_1\leqslant n-1-\sum\limits_{i=2}^nC_i\\ C_1\geqslant \sum\limits_{i=2}^nB_iC_i\\ C_1\geqslant 0 \] 注意到若 \(\sum\limits_{i=2}^n(B_i+1)C_i=k\)，则合法的 \(C_1\) 数量为 \(\max(0,n-k)\)，所以只需要跑一个完全背包，复杂度 \(O(n^2)\)。
E - Balancing Network
现在有 \(n\) 条线 \(m\) 个平衡器，平衡器从左往右，第 \(i\) 个平衡器连接了 \(x_i,y_i(x_i<y_i)\)，你需要给平衡器定向，定向后的平衡器若是从 \(x_i\) 指向 \(y_i\)，则你从 \(x_i\) 走到这个平衡器时会跑到 \(y_i\)，你需要给出满足和不满足以下条件的定向方案或判断无解：从每根线的最左面出发一直向右走，最后都会走到同一根线的最右面。\(n\leqslant 50000,m\leqslant 100000\)。
满足条件
假设我们最后全走到了 \(t\)，我们记录 \(vis_i\) 表示现在从 \(i\) 开始走是否会走到 \(t\)，我们从右往左添加平衡器，一开始只有 \(vis_t=1\)，若现在添加的平衡器为 \((x,y)\)，分类讨论：
- 若 \(vis_x=vis_y=0\) 或 \(vis_x=vis_y=1\) 怎么调都不会改变。
- 若 \(vis_x=1,vis_y=0\)，把平衡器设为 \(y\rightarrow x\) 可以让 \(vis_y\) 也变成 \(1\)。
- 若 \(vis_y=1,vis_x=0\) 类似上面。
注意到这等价于把 \(vis_x\) 和 \(vis_y\) 都赋值为两者的或，所以我们可以用 bitset 来加速枚举，每一位表示终点为 \(i\) 的答案，这样添加一个平衡器就等价于把两个 bitset 或起来，复杂度 \(O(\dfrac{nm}{w})\)。
不满足条件
由于 \(m>0\)，所以若 \(n=2\) 一定无解。下面的构造方式证明了 \(n>2\) 时一定有解。
我们设 \(end_i\) 表示 \(i\) 目前最后会走到哪里，\(siz_i\) 表示最终会走到 \(i\) 的线的数量。那么我们只需要保证对任意 \(i\)，\(siz_i<n\)。我们依旧从后向前添加平衡器，一开始 \(end_i=i,siz_i=1\)。假设现在添加的是 \((x,y)\)，我们发现，这等价于要不然把 \(end_x\) 改为 \(end_y\)，要不然把 \(end_y\) 改为 \(end_x\)。注意到这会使 \(siz_{end_x}\) 或 \(siz_{end_y}\) 加上 \(1\)，所以当 \(siz_{end_x}=n-1\) 时定向为 \(x\rightarrow y\) 即可，\(siz_{end_y}=n-1\) 时同理，注意到由于 \(n>2,2n-2>n\)，所以不会出现两个都为 \(n-1\) 的情况。如果两个都不为 \(n-1\) 任意定向即可。复杂度 \(O(n+m)\)。
F - Histogram Rooks
给定 \(n\times n\) 的棋盘，现在第 \(i\) 列只有最底下 \(h_i\) 个位置没被扣掉，现在往棋盘上未被扣掉的格子上放若干个车，使得每个没被扣掉的格子要不被某个车占领，要不可以被某个车攻击到（车不能跨过被扣掉的格子），求方案数。\(n\leqslant 400\)（可以改为 \(3000\)）。
我们称题目中的条件为“被覆盖”。考虑容斥，钦定某些位置一定未被覆盖，并计算每个行连续段的贡献，假设钦定 \(k\) 个位置未被覆盖，则容斥系数为 \((-1)^k\)。
我们注意到每一列都是连续的，所以我们考虑钦定某些列中存在未被覆盖的格子。设某个行连续段的长度为 \(len\)，这个行连续段有 \(p\) 列被钦定未被覆盖。我们考虑这 \(p\) 列中在这一行的格子是否被钦定，若一个都没有被钦定，则剩下 \(p-len\) 个格子随便填，方案数为 \(2^{len-p}\)；若至少有一个格子被钦定，则剩下格子都不能填，方案数为 \(1\)，枚举钦定的格子数，带上容斥系数，这部分的总贡献是 \(\sum\limits_{i=1}^p(-1)^i\dbinom{p}{i}=-[p\not= 0]\)，所以这个行连续段的贡献为 \(2^{len-p}-[p>0]\)。
其实我们刚才那个容斥是假的，因为我们并没有保证存在钦定未被覆盖的格子的列真的存在了未被覆盖的格子（这句话有点绕，就是说对每个包含这列的行连续段我们都没钦定到这个列的格子，这样就算多了），为此我们再套一层容斥：设 \(S\) 表示我们上面钦定的列的集合，\(T\) 表示 \(S\) 中一定不存在被钦定未被覆盖的格子的列的集合，那么这一层的容斥系数为 \((-1)^{|T|}\)。
现在假设某行的连续段的长度为 \(len\)，这个行连续段有 \(p\) 列在 \(S\) 中，\(q\) 列在 \(T\) 中，那么现在这个行连续段的贡献变为了 \(2^{len-p}+\sum\limits_{i=1}^{p-q}(-1)^i\dbinom{p+q}{i}=2^{len-p}-[p\not=q]\)。注意到我们并不关心 \(q\) 具体的值，我们只在乎 \(p\) 是否等于 \(q\)，关于 \(q\) 的容斥系数我们只需要在向 \(T\) 中添加元素时同时加上即可。
现在考虑如何加速这个过程，考虑分治，如果我们每次取当前列的区间内的最小值，发现最小值到底端的行连续段都一致可以一起计算，就可以把区间分为两个子问题再合并，合并时只需要考虑当前列是否加入 \(S\) 和 \(T\)（其实就是笛卡尔树）。
所以只需要设状态 \(f(i,j,0/1)\) 表示当前 dp 到了矩形 \(i\)，\(|S|=j\)，\(T\) 是否等于 \(S\)。
由于我们只会访问 \(O(n)\) 个连续的行连续段，所以总复杂度 \(O(n^2\log n)\)，如果预处理转移系数可以达到 \(O(n^2)\)。