本来是周末更，但是去了 CTT，源码在学校电脑里，于是鸽了两天。
9 AGC062D Walk Around Neighborhood
不会判无解，什么水平。
把 \(D_i\) 排序，容易发现如果 \(D_n>\sum_{i<n}D_i\) 的话那么一定无解。否则，前面的数能走到的所有点到原点的曼哈顿距离一定是一个区间，并且左端点小于 \(D_i\)（相邻做差即可构造）。所以可以证明条件是充分的。
然后枚举最大半径 \(r\)，尝试判断 \(r\) 是否合法。首先证明一个引理：\(\frac{D_n}{2}\leq r\leq D_n\)。这是因为要跳跃 \(D_n\)，所以半径不会小于 \(\frac{D_n}{2}\)。进一步地，如果我们跳到曼哈顿距离为 \(D_n\) 的边界上，那么一直反复横跳，最后跳回来，一定可以构造出解。
上面的证明其实提示了我们一个策略：跳到曼哈顿距离为 \(r\) 的边界上，然后一直反复横跳，最后跳回来。代数地描述，实际上是把 \(D\) 分成两个集合，使得两个集合都能跳到边界上。
考虑分析能够跳到边界上的条件。首先，如果 \(\leq r\) 的数的和 \(\geq r\)，那么一定合法（构造是先直着跳若干步，然后一步跳到边界上）。否则，考虑 \(x>r\)，如果 \(\leq r\) 的数 \(\geq x-r\)，那么也合法（构造是跳到 \((x-r,0)\)，然后一步跳到 \((-r,0)\)），剩下的情况均不合法。
所以枚举 \(r\) 的时候找到最小值和次小值分到两个集合即可，利用 bitset 实现背包，背包的值域可以只开到 \(\max D_i\)。
https://atcoder.jp/contests/agc062/submissions/47979826
10 AGC061B Summation By Construction
图构造题。
其实我并不知道怎么想出来的，很多时候只是凭感觉。
感谢pjykk 佬的题解。
首先，颜色为 \(n\) 的方案是显然的：邻接矩阵上的一条从右上到左下的路径。
考虑主动强化一下限制，如果每条路径都是这个形态能否构造。题解给出了 \(n\) 为奇数的构造：先构造 \(n\)，随后 \(i\) 和 \(n-i\) 配对，构造完 \(i\) 的路径之后接着之前的路径构造 \(n-i\)，超出矩阵的位置循环往前面填。
考虑偶数怎么填。仍然仿照奇数的填法，先填完 \(n\)，然后填 \(n-1\)，注意此处 \(n-1\) 是先下后右。然后对于 \(i\geq 3\)，将 \(n-i\) 和 \(i\) 配对，路径都是先下后右。然后特殊处理一下 \(1,2\)。
https://atcoder.jp/contests/agc061/submissions/4798096
不太会构造啊，之后尝试看一下world.construct(me)，虽然感觉还是很玄学。
11 AGC060B Unique XOR Path
啥比诈骗题，线性你 \(n=30\) 是想干嘛/fn
不太好做，所以肯定有神必充要条件。不会找，所以考虑构造一些平凡的情况。考虑形如 RRRR……RDDDD……D 类型的路径，此时直接把路径上所有数都看成 \(0\)，然后副对角线上全放 \(1\) 就可以了。
仿照这个思路进行构造：把路径上的点都赋成 \(0\)，然后对于每个拐角引出一条斜线，斜线上赋为一个数。那么合法的条件就是我们放的数线性无关，显然不会超过 \(k\) 个。
所以充分条件是拐角不超过 \(k\) 个，证明它是必要的。事实上只要把拐角上的数找出来，如果线性有关，那么找到一个异或和为 \(0\) 的集合就可以调整到另一条路径，所以不合法。
但是有一点问题，就是这样的图形：
00*
*00
显然两个 * 不会同时经过，此时构造方案两个 * 上的斜线一定是相同的数。特判一下就行。
https://atcoder.jp/contests/agc060/submissions/47984495
12 ARC128E K Different Values
tyw 老师秒了，但是我搞了好久/ll
考虑怎么判断有解。首先有显然的贪心方案：每次取最大的。事实上存在充要条件：
- \(\max a_i\leq \lceil\frac{\sum a_i}{k}\rceil\)。
- \(\sum [a_j=\max a_i]\leq (\sum a_i-1)\bmod k+1\)。
归纳是不难证明的。
考虑贪心，每次找到最小的填进去。问题在于如何在加了限制的条件下判断填完一个数之后剩下的是否合法。其实只要判一下比较急的元素的个数是否和 \((\sum a_i-1)\bmod k+1\) 相等就可以了，如果相等就选一个，否则选一个最小的能填的。复杂度 \(\mathcal{O}(n\sum a_i)\)。
https://atcoder.jp/contests/arc128/submissions/47987017
13 ARC128D Neq Neq
孩子终于会推结论了，不过这个比较简单。
考虑怎么判断集合 \(S\) 是合法的，注意到每个间隙之间是独立的，所以可以单独对每个间隙做，问题变成了判断一个序列能否删掉只剩最左和最右两个数。
尝试推一些条件，发现如果两个相邻数相等显然不合法，先特判掉。发现剩下的情况不太好搞，考虑大力构造一些合法的情况。不妨假设开头元素 \(x\) 和末尾元素 \(y\) 满足 \(x\neq y\)，发现构造不出来。不妨再假设存在一个 \(z\) 满足 \(z\neq x\) 且 \(z\neq y\) 且 \(z\) 是离 \(x\) 最近的合法元素，那么序列形如 \(xyxyxy\cdots xyz\cdots y\) 的形式，显然 \(z\) 可以把开头到它前面的数都删掉，分类讨论 \(z\) 后面一个元素 \(w\) 的取值：
- \(w=x\)，分两种情况讨论：
- \(w\) 到 \(y\) 之间没有 \(z\) 使得 \(z\neq x\) 且 \(z\neq y\)，此时仿照上面可以用 \(z\) 把右边也消掉。
- 存在 \(z\)，那么归约到了形式相同的子问题。如果假设存在 \(z\) 就是合法的充要条件，那么这一步里面我们归约到了形式相同的子问题，所以根据假设，一定可以把 \(w\) 到 \(y\) 之间都删掉。
- \(w\neq x\)，此时把 \(z\) 删了没影响。
所以我们得到了充要条件：存在 \(z\)。
考虑 \(x=y\) 的情况，此时有 \(z=x+1\)，如果 \(z\) 右侧找不到 \(z'\)，那么序列是 \(xzxz\cdots xzx\) 的形式，除了中间长度为 \(1\) 的情况都合法。
所以充要条件是：要么中间长度不超过 \(1\)，要么有至少三种颜色。DP 容易线性。
https://atcoder.jp/contests/arc128/submissions/47990255
14 AGC016F Games on DAG
感觉比较简单。
容易想到按照 SG 值分层做。如果枚举 SG 值的划分方案，那么判断方式是：相同集合中的所有数没有连边，SG 较大的集合中的每个点向每个 SG 值较小的集合都有连边。
所以可以直接 DP：设 \(f(S)\) 表示已经确定 \(S\) 集合的 SG 值和入边的方案数，每次把入边算一算就好了。
https://atcoder.jp/contests/agc016/submissions/48005809
15 ARC091F Strange Nim
稍微观察一下可以发现 SG 值满足递推关系：\(sg_i=\begin{cases}i/k&k|i\\sg_{i-i/k-1}&\text{otherwise}\end{cases}\)，如果 \(k\) 比较小的话可以直接暴力跳，否则跳的一步会比较短。但是注意到如果按照 \(i/k\) 分段的话段数会比较少，并且同一段的跳跃是等差数列，所以可以直接跳到段头。
不太会证 \(k\) 较小的复杂度啊，但感觉是 \(\sqrt{n}\) 级别的。hzk 老师说 \((\frac{k-1}{k})^k=\frac{1}{e}\)，所以复杂度大概是 \(k\log n\) 的，分治一下就是 \(\sqrt{n\log n}\) 了。
然后直接暴力跳过了/cf
https://atcoder.jp/contests/arc091/submissions/48007823
怎么还在做简单题/fn
16 AGC061E Increment or XOR
很厉害啊！没想到这也能 DP。
如何考虑 \(+1\) 操作是一个问题。注意到一次 \(+1\) 操作会把 \([0,i-1]\) 推成 \(0\)，然后把 \(i\) 处的 \(0\) 变成 \(1\)。如果我们钦定没有操作进位到 \(i+1\)，那么把数拆成 \([0,i]\) 和剩余部分来观察，前一半构成了一个新的子问题，而后一半可以通过记录每个操作的奇偶性来得到每一位的具体值。
更为具体的，如果我们找到进位最高的一次操作 \(k\)，假设进位到 \(x\)，那么对于所有 \(M\) 次操作，\([1,k)\) 会构成一个子问题，其起点状态是 \(S\)，终点状态是一个 \([0,x-1]\) 位为 \(1\)，\(x\) 位为 \(0\) 的数，如果记录中间异或操作使用的奇偶性，可以得到每一位的具体值；\((k,M]\) 同样会构成一个子问题，其起点状态是 \([0,x-1]\) 为 \(0\)，\(x\) 位为 \(1\) 的数，终点状态是 \(T\)，如果记录中间异或操作使用的次数，同样可以得到每一位的具体值。所以，假如找到最高进位位置，则原问题分成两个独立的子问题。
所以我们构建了一个和区间 DP 类似的模型。可以得到状态：设 \(f(i,0/1,0/1,msk)\) 表示只考虑前 \(i\) 位，其起点 / 终点状态是否为 \(S/T\)，使用了异或操作的奇偶性状态为 \(msk\) 的最小花费。转移分为两种：
- 第 \(i\) 位不操作，那么判断第 \(i+1\) 位经过 \(msk\) 操作之后是否匹配终点状态，直接转移。
- 第 \(i\) 位操作，那么状态变化为 \(f(i,x,1,msk_1)\to f(i,1,1,msk_2)\to \cdots\to f(i,1,y,msk_m)\)，转移到 \(f(i+1,x,y,\oplus_{i=1}^m msk_i)\)。因为我们钦定 \(i\) 是最高位置，所以需要判断操作过程中第 \(i+1\) 位是否会进位，也即进位操作时 \(i\) 是否为 \(0\)。可以采用 Dijkstra 式的转移。
复杂度为 \(\mathcal{O}(2^{2n}\log V)\)。
https://atcoder.jp/contests/agc061/submissions/48012160
17 AGC060D Same Descent Set
题目要求：
其中 \(S\) 描述一个不等关系，\(x\in S\) 当且仅当 \(x\) 和 \(x+1\) 之间的符号是小于号。
考虑怎么求 \(f(S)\)，你大力容斥一下：
把平方拆开写成两个式子，然后把 \(S\) 扔到后面去：
然后其实比较好做，思路是钦定它们共同的断点然后 DP。把 \(|T_1\cap T_2|\) 拆成 \(|T_1|+|T_2|-n+|\overline{T_1}\cap\overline{T_2}|\)，然后把前面三项拆出去，后面那一项在转移的时候带 \(1\) 的系数即可，根据二项式反演的结论可以说明它是对的。
然后你分治 NTT 一下。
https://atcoder.jp/contests/agc060/submissions/48020667
18 AGC060E Number of Cycles
感觉是能做的，但是我做的时候不会一点/kk
先考虑怎么判断合法。尝试观察 \(\text{cyc}(a\circ b)\) 的形态，但是没啥用，因为这东西一片混乱。如果观察合法的 \(m\) 的分布，可以发现：答案为一个区间内所有的奇数或者偶数，这是因为交换 \(b\) 中的两个数 \(x,y\)，对环数量的贡献只能是 \(-2,0,2\)。所以转而求最小值和最大值。
结论：最大值一定是 \(n+\text{cyc}(a)\)，此时 \(b_i=i\)。因为交换 \(b\) 中的两个在同一个环内的数是不劣的。
结论：最小值只会是 \(2\) 或者 \(3\)。
考虑一个策略：\(i\) 从小到大确定 \(b_i\)，每次尽量选择 \(u\) 使得 \(u\) 和 \(i\) 在 \(b\) 的环中不连通且 \(u\) 和 \(a_i\) 在 \(c\) 的环中不连通。可以证明对于 \(i\leq n-2\)，\(u\) 都是存在的。这是因为所有入度为 \(0\) 的点之多一个和 \(u\) 联通，而入度为 \(0\) 的点有 \(n-i+1\) 个。所以 \(b\) 的环中有一个不合法，\(c\) 的环中有一个不合法，而有三个选择，所以一定能找到合法的。对于 \(i=n-1\)，\(u\) 也能保证满足与 \(b\) 不联通。
构造出最小值，存在从最小值到最大值的方案：环上每个点依次与 \(1\) 交换。显然其中一定有 \(m\)。维护环数比较麻烦，但是环数是单调的，所以二分一下就可以了。
https://atcoder.jp/contests/agc060/submissions/48022030
感觉很多题都是像这样随便造一个策略然后证明最优性啊。
19 gym104821D Red Black Tree
vp 的时候编了好久 Slope Trick 并带偏 hzk 思路，hzk 指出维护差分数组之后问题得到快速解决/qd
容易写出 DP：
- \(f_{u,i}=\sum f_{v,i}\)。
- \(f_{u,i}=\min(f_{u,i}+w_0,f_{u,i-1}+w_1)\)，其中 \(w_0,w_1\) 为设为 \(0/1\) 的代价。
容易发现 DP 是凸的，但是使用 Slope Trick 并不好维护，原因是不好锁定斜率为 \(0\) 的点，甚至未必存在。尝试维护差分数组，则转移为单点加和维护闵可夫斯基和。使用堆维护 DP 值，并使用类似长链剖分的方式合并子树，复杂度为 \(\mathcal{O}(n\log n)\)。
https://codeforces.com/gym/104821/submission/234905436
std 做法是用 vector 分别维护正数和负数，可以做到线性。
20 gym104821K Grand Finale
vp 的时候去吃饭了，赛后过的。
注意到如果顶到了上限那么上限是多少其实并不重要。对于这个阶段，可以 DP 一下：\(f_{i,j}\) 表示当前堆顶的牌是 \(i\)，有 \(j\) 个 Q，最少需要几个 B 才能把牌出完。
然后考虑如果没有顶到上限怎么做。注意到顶到上限之前用 Q 就是一换一，用 W 就多拿一张牌。决策既要考虑 Q 的个数，W 的个数，在没满的情况下最远到达的距离，分析起来较为复杂。不妨枚举使用的 Q 的个数 \(i\)，那么策略是如果能用 Q 就先用 Q，没用 Q 就用一个 W，然后扩充背包上限。如果当前已经能满足在满背包情况下能出完牌，那么用当前牌的数量更新答案。
时间复杂度 \(\mathcal{O}(n^2)\)。
https://codeforces.com/gym/104821/submission/234921526
21 gym104821E Extending Distance
转对偶图最大流，然后费用流解决。
代码摆了/shui
22 2023 集训队互测 Round 16 最后的晚餐
暴力可以做到 \(\mathcal{O}(3^{(n+12)/3})\)。
先考虑 \(f(A)\) 的求解方式。
对于 \(a_i\leq 11\)，有策略：
- 如果当前前缀和末尾不是 \(9\)，那就放 \(11\)。
- 否则，如果存在，任意选择一个数放上去。
- 否则，放 \(11\)。
、
直接 DP 可以做到平方，但是 \(f(A)\) 存在更简单的形式。如果到不了 1.2，那么可以取到上界 \(S/10\)，其中 \(S\) 是所有数的和。否则，可以取到另一个上界 \(n\)。于是，答案是 \(\min(S,n)\)。
\(a_i\leq 12\) 的问题在于 \(1\) 未必能够完成进位。如果只有偶数和 \(1\)，则答案有上界 \(n-c_1/2\)。扩展这个结论，注意到只有奇数能够改变奇偶性，所以 \(1\) 如果想进位，必须和另外一个奇数配对。于是可以找到答案上界 \(n-\max(0,c_1-c_3-\cdots- c_{11})/2\)。
以下给出构造：
- 如果当前前缀和末尾小于 \(8\)，那么有 \(12\) 则放 \(12\)，否则使用上面的策略。
- 如果当前前缀和末尾等于 \(8\)，那么：
- 如果有偶数，放偶数。
- 否则，放 \(11\)。
- 否则，放任意奇数。
- 否则，放 \(1\)。
- 如果当前前缀和末尾等于 \(9\)。
- 如果有 \(1\)，放 \(1\)。
- 否则，放任意奇数。
- 否则，放 \(11\)。
随后可以 DP 解决。求出 \(h_1(x,y)\) 表示偶数中选了 \(x\) 个数，和为 \(y\) 的方案。\(h_2(x,y)\) 表示奇数个数减去 \(\max(0,c_1-c_3-\cdots- c_{11})/2\) 是 \(x\)，和为 \(y\) 的方案数，需要计算：
把后面的式子的 \(x+z\) 提出来，再通过讨论 \(y\bmod 10+w\bmod 10\) 与 \(10\) 的大小关系，即可拆开暴力枚举，时间复杂度 \(\mathcal{O}(n^2)\)。
https://www.luogu.com.cn/paste/1bd2evx7
23 2023 集训队互测 Round 17 棋盘
感觉憨憨，可惜我不会构造/cf
最简单的构造是构造 \(2\) 的幂次。然后你其实可以考虑转化进制，构造出来 \(3\) 的幂次和 \(6\) 的幂次，比 \(2\) 的幂次优一点。
然后正解的构造是构造斐波那契数列，大概是先放两格，然后不停在外面围 \(4\) 个各自，然后求一下 \(k\) 的斐波那契拆分就好了。
24 2023 集训队互测 Round 17 区间切割
我们希望每次切割的时候缩减区间长度尽可能多，但是可能存在一些离端点很近的元素。但是可以注意到：
- 如果 \(l\leq x\leq \frac{2l+r}{3}\)，那么切割 \(x\) 相当于 \(l\gets \max(l,x)\)。
然后就好办了，对于三等分点外的操作是平凡的，可以直接处理。对于一次非平凡操作，区间长度至少变为原来的 \(\frac{2}{3}\)。扫描线解决区间操作，复杂度为 \(\mathcal{O}(n\log^2n+m\log n)\)。