ARC205
20250907
ARC205 A
首先有一个操作上界是第一步可以操作的方案数，然后我们发现，一定可以构造出这样的方案，然后做完了。
ARC205 B
仍然是考虑上界，一个点的黑色邻边和一开始的奇偶性必须相同。然后考虑在此限制上取到上界，我们发现一定可以通过调整法调整非上界的情况。
ARC205 C
显然合法当且仅当不同方向的段不交，并且同方向的段不包含。
一个简单的判断的方法是，按照 \(s\) 排序，要求 \(t\) 递增。
然后两个方向分别标号，做完了。
ARC205 D
dp 或者贪心。
考虑 \(f(x)\) 表示 \(x\) 子树内最多匹配，然后如果有一个子树的剩余点数超过其他的剩余和，那么需要拆掉其他子树的匹配来做。
ARC205 E
meet in the middle。对低 \(10\) 位暴力更新前缀和，高 \(10\) 位查询的时候再暴力枚举子集。
ARC204
20250908
ARC204 A
考虑这样操作有取 \(\max(C,\cdots)\) 的，我们可以枚举最后一次取到 \(C\) 的操作，这样最终的值可以表示为 \(\max_i v_i\)，\(v_i\) 表示第 \(i\) 个操作取到 \(C\)，之后都不考虑对 \(C\) 取 \(\max\) 的答案。
做一个差分，答案是 \(F(R)-F(l-1)\)。
\(F(R)\) 表示 \(\max_i v_i\leq R\) 的方案数。可以 dp，设 \(f(i,j)\) 表示 dp 到 \(a_i\)，加入到了 \(b_j(j\leq i)\)，\(\max_{k\leq i}v_k\leq R\) 的方案数。
然后转移就是 \(f(i,j)\to f(i+1,j)\) 以及 \(f(i,j)\to f(i,j+1)\)。
ARC204 B
考虑对置换环 dp，然后考虑设 \(f(l,r)\) 表示当前环是原环 \([l,r]\) 部分的点。注意到一定存在一次操作，其端点是 \(l\) 或 \(r\)。所以枚举另一点 \(k\)。
然后有转移 \(f(l,r)=f(l,k-1)+f(k,r)+[a_l\equiv a_k\pmod n]\)。
但是复杂度 \(O(n^3k^3)\)，过不了。
然后注意到，我们其实只要枚举 \(a_l\equiv a_k\pmod n\) 的 \(k\)，以及 \(k=l+1,k=r\) 的情况就可以覆盖所有答案了。
因为一个没有贡献的操作是不急于做的，完全可以（通过 \(k=l+1,r\) 缩小边界）把机会让给有贡献的操作。
ARC203
20250909
ARC203 A
注意到最优策略是，每组选一半人都赢，一半都输，然后注意 \(m\in\text{odd}\) 的时候还可以有一个赢。所以答案是 \(n\lfloor\frac{m}{2}\rfloor+[m\in\text{odd}]\)。
ARC203 B
考虑如果有 \(>1\) 个 \(1\)，那么 \(0\) 可以随便移动，所以只要 \(1\) 的个数相同就行了。
如果有恰好 \(1\) 个 \(1\)，那么如果 \(1\) 在两端点，那么无法移动。特判一下。
ARC203 C
\(k< n+m\) 是简单的。
考虑 \(k=n+m\)，分类讨论：
- 一条长度为 \(n+m-2\) 的路径，随便打穿其他两堵墙，方案数 \(\binom{n+m-2}{n-1}\binom{n(m-1)+(n-1)m-(n+m-2)}{2}\)。
- 去除一个格子四周都被打穿的方案数（被算了两遍），枚举这个格子，有 \(\binom{n+m-4}{n-2}(n+m-3)\)。
- 考虑打穿长度为 \(n+m\) 路径的情况。
发现路径一定是有恰好一次向左或向上。然后考虑向左的情况。
这个向左操作的上一次和下一次操作都要是向下，所以我们先不考虑这个，这样路径方案数是 \(\binom{n+m-4}{n-3}\)，然后插入这个“下左下”的方案数，要求后面必须有一个向右的操作，所以方案数是 \((m-1)\binom{n+m-4}{n-3}\)。
所以答案是 \(\binom{n+m-2}{n-1}\binom{n(m-1)+(n-1)m-(n+m-2)}{2}-\binom{n+m-4}{n-2}(n+m-3)+(m-1)\binom{n+m-4}{n-3}+(n-1)\binom{n+m-4}{m-3}\)。
ARC203 D
只考虑 \(n>2\)，至少有 \(1\) 个 \(0\) 的情况。
考虑 \(00\) 段最后只能变成 \(0\dots 0\)，并且其他段无法变成全零段。
如果不存在 \(0\dots 0\) 段，可以简单分类讨论两侧的数：
- \(0\{0,1\}^*0\)，此时一定有 \(B=010\)。
- \(0\{0,1\}^*1\)，有 \(B=01\)。
- \(1\{0,1\}^*0\)，有 \(B=10\)。
- \(1\{0,1\}^*1\)，有 \(B=11\)。
所以我们先找到 \(A\) 中长度大于 \(1\) 全零的段，然后以这个分子情况考虑，发现两个这样的段中间填一个 \(1\) 就可以构造出来，设 \(c\) 是长度大于 \(1\) 全零的段的个数，中间的方案数是 \(3c-1\)。
然后考虑左右两侧，讨论是类似的：
对于左侧不是全零段：
- \(a_1=0\)，那么 \(B_L=01\)。
- \(a_1=1\)，那么 \(B_L=1\)。
右侧同理。
设 \(vL,vR\) 表示左右端点是否不是全零段。
也就是答案是 \(3c-1+[vL] (1+[a_1=0])+[vR] (1+[a_n=0])\)。