前言
没有前言。不会做 CSP2022 T3，更不会做 NOIP2022 T2。太菜了，太菜了，凡是思维题一个不会。或许拿几道 AtCoder 来做一做会有点帮助？带着这样的想法，将 POI 里的经典题暂时搁下。来做 ($\text{b}\check{\text{a}}\text{n}$) 做 ($\text{shu}\bar{\text{a}}$) AGC 吧！
目标: 2023 省选（拟定 4 月）之前，板刷完 AtCoder Grand Contest 内所有题目。2022 年 12 月 8 日起生效。
题号前面带 [*] 的为觉得比较好，值得复习的题。
题号前面带 [**] 的为 virtual participation 时未能自己做出的题。同样需要复习。
与 IOI2020 集训队作业 板刷记录 配合食用。
AtCoder Grand Contest 001 (2022.12.8 完成)
AT_agc001_a - BBQ Easy
直接贪心即可。
AT_agc001_b - Mysterious Light
发现当激光走了 $n$ 步之后就形成了平行四边形，然后类似辗转相减地形成新的平行四边形，递归计算。
AT_agc001_c - Shorten Diameter
直径的性质，即存在一个点或一条边的中点，使得所有点到这个点的距离为 $\frac{d}{2}$。枚举这个点 $O(n^2)$ 做。
[**]AT_agc001_d - Arrays and Palindrome
比较有趣的构造题。先考虑给定 $a,b$ 数组后的判定，将序列划分成的每个段 $[l,r]$，将点对 $(l,r),(l+1,r-1)\cdots$ 依次连边，最后看是否形成一个连通块。这要求至少连了 $n-1$ 条边，即 $a,b$ 数组中奇数的数量 $\le 2$。进而得到无解的判定条件以及 $a,b$ 数组错开一位的构造。
[**]AT_agc001_e - BBQ Hard
式子容易推，$\displaystyle{\sum_{i=1}^{n}\sum_{j=i+1}^{n}\binom{a_i+b_i+a_j+b_j}{a_i+a_j}}$。不能接受 $O(n^2)$，但可以 $O(V^2)$。考虑组合意义，即从 $(-a_i,-b_i)$ 走到 $(a_j,b_j)$，每次能向上或向右走的方案数，然后放在一起进行一遍 dp。
[**]AT_agc001_f - Wide Swap
对排列 $P$ 的逆置换 $Q$ 进行操作，若 $Q_i - Q_{i+1} \ge K$ 则可以交换，发现可以冒泡排序。将冒泡排序改为归并排序，修改归并的条件，仅当右段的当前位置能够与左段的剩余后缀交换才向左归并。
启发
- 在思考构造题时，先思考对于一组解是否合法的判定（想想 spj 该怎么写）。
- 当组合式化简无从下手时，去考虑这个式子的组合意义。
AtCoder Grand Contest 002 (2022.12.9 完成)
AT_agc002_a - Range Product
按照题意模拟。
AT_agc002_b - Box and Ball
直接模拟，$num_i$ 表示 $i$ 处球的个数，$ans_i$ 表示当前时刻 $i$ 处是否可能有红球。
AT_agc002_c - Knot Puzzle
若能找到 $a_i + a_{i+1} \ge L$，则合法。构造显然。
AT_agc002_d - Stamp Rally
比较板的整体二分，可撤销并查集维护所有编号 $\le mid$ 的边形成的连通块大小，$O(n\log^2)$。
[**]AT_agc002_e - Candy Piles
神仙博弈论题。将石子堆从大到小排序，发现每次操作要么消去左边一列，要么消去下面一行。然后就划分成了子问题。打个表找找规律，发现对角线上除了右上边界都相同，于是找到主对角线上的最大坐标递推即可。
[**]AT_agc002_f - Leftmost Ball
计数题，不是很会。考虑从右往左插入新的颜色 $k$，白色球一定在最左边，第一个颜色为 $k$ 的球需要插入到原序列的第一个非白色球之前，于是维护原序列的前缀白色球数量，进行 $O(n^2)$ 的 dp，组合数计算转移系数，前缀和优化一下。
AtCoder Grand Contest 003 (2022.12.9 完成)
AT_agc003_a - Wanna go back home
按照题意模拟。
AT_agc003_b - Simplified mahjong
贪心匹配，能够发现 $(i,i+1)$ 只会有 $\le 1$ 次，否则一定能够分别拆成 $(i,i)$ 和 $(i+1,i+1)$。
AT_agc003_c - BBuBBBlesort!
只考虑操作 $2$，发现可以做到对奇数/偶数位分别排序，操作 $1$ 的次数及奇数位上的偶数数量。
[*]AT_agc003_d - Anticube
刚开始自己写的时候，只考虑了 $\le \sqrt[3]{w}$ 的质因子，但大致思路是对的。
假设去除 $\le \sqrt[3]{w}$ 的质因子后剩下 $x$。至于 $\gt \sqrt[3]{w}$ 的质因子，可以发现若为 $2$ 个不同的质因子 $x = pq$ 则可以直接贡献到答案中（因为 $p^2q^2 > w$），否则 $x=1 \lor x=p \lor x = p^2$，直接分解计算。
[**]AT_agc003_e - Sequential operations on Sequence
vp 时，想到从后往前推坐标，每次 $\bmod q_i$，然后思考用数据结构维护，就不会了。
实际上，若 $q_i$ 递增，则每次从后往前 $\bmod q_i$ 后，找到序列中最后一个 $\le r$（$r$ 为余数）的继续取模，每次 $r$ 至少 $\times \frac{1}{2}$，总共会经历 $\log V$ 次取模，这是本题的关键性质。
于是用单调栈维护 $q_i$ 的递增序列，二分找出上一个 $\le r$ 的数暴力算贡献就好了，$O(n \log n \log V)$。
[**]AT_agc003_f - Fraction of Fractal
一眼分讨，但时间原因没有仔细想，看了题解觉得不是很难想。
我们称左右两个 level $1$ 拼到一起形成 $1$ 个连通块为左右连通，同理定义上下连通。若图形满足上下连通且左右连通，答案显然是 $1$。若既不满足上下连通又不满足左右连通，答案就是 $tot^{k-1}$，其中 $tot$ 表示黑色单元格数量。
剩下的情况就是只满足一种连通的情况了，以上下连通为例，发现每次拓展是对 $(\text{内部相邻上下黑格},\text{边界相邻上下黑格})$ 二元组的线性变换，对其进行矩阵快速幂即可。
启发
- 不仅仅是除法，倘若每次取模都满足模数 $p \le x$，则取模的次数也是 $O(\log V)$ 级别的。
AtCoder Grand Contest 004 (2022.12.10 完成)
AT_agc004_a - Divide a Cuboid
直接模拟。
AT_agc004_b - Colorful Slimes
挺有趣的题，我甚至在 B 上面花费了蛮久。挺不错的枚举 + 贪心。
[**]AT_agc004_c - AND Grid
没做出来绿题的构造。其实对着样例玩一玩应该能玩出来的。
AT_agc004_d - Teleporter
基环树，将 $1$ 连向自身，剩下来的点贪心，从距离大的往距离小的，每 $O(k)$ 个连向 $1$。
[**]AT_agc004_e - Salvage Robots
比较趣味的题，将机器人的移动转化为对整个棋盘包括 Exit 的移动，以 Exit 已经移动到的矩形的边界，设计 $O(n^4)$ 的 dp 状态，然后精细分析一下转移时能到达 Exit 的机器人范围。
[**]AT_agc004_f - Namori
黑白染色题。树以及带偶环的基环树都差不多，直接进行二分图黑白染色，每次操作相当于找到相邻的一黑一白进行交换。
对于树，每条边被操作的最小次数必然是子树内的黑白点数量之差。
对于基环树，先取其生成树计算，再考虑新加入的边的贡献。
若是偶环的基环树，考虑多出来的边 $(u,v)$，假设这条边将子树内的 $x$ 的黑点变成白点，则 $path(u,v)$ 上的边操作次数相应更改，能够发现新的贡献是类似 $\sum|a_i - x|$ 的形式，因此 $x$ 取中位数最优。
若是奇环的基环树，对 $(u,v)$ 进行操作会使得黑点/白点数量有 $2$ 的变化，因此操作次数是固定的，去掉这条边后按照树做即可。
AtCoder Grand Contest 005 (2022.12.10 完成)
AT_agc005_a - STring
直接模拟。
AT_agc005_b - Minimum Sum
按照笛卡尔树划分区间计算。
AT_agc005_c - Tree Restoring
容易想到先枚举直径 $d$，然后利用直径上延伸出来的菊花对 $a_i$ 进行构造，实际上能够做到 $O(n^2)$，不知道数据范围为啥是 $100$。
[*]AT_agc005_d - ~K Perm Counting
终于自己做出来一道有趣的的计数 dp 题了。外层进行容斥，统计有 $\ge x$ 个位置存在 $|i - a_i| = k$ 的排列数。发现直接 dp 可能会使得 $a_i = a_{i+2k} = i+k$ 的情况出现，但是 $\bmod 2k$ 形成的同余系互不干扰，对其分别计算，加一维 $0/1$ 状态表示 $i+k$ 是否被占用，就 $O(n^2)$ 做掉了。
[**]AT_agc005_e - Sugigma: The Showdown
神仙博弈论题。无限循环的条件很容易考虑，因此先手的目标就是要设法进入无限循环。这时应该将所有能形成无限循环的点忽略掉，只考虑在不循环的条件下的策略，就能发现一些有用的性质。
AT_agc005_f - Many Easy Problems
考虑固定 $k$ 时，一个点 $u$ 对答案的贡献。若以 $u$ 为根，则当且仅当$\ge 2$ 个子树内存在关键点时，对答案有 $1$ 的贡献，即 $\displaystyle{Ans = \sum_{u=1}^{n}\binom{n}{k} - \sum_{(u,v) \in E} \binom{siz_v}{k}}$。前面的组合数能够线性计算，后面的组合数实际上可以将阶乘与阶乘的逆元进行卷积，$O(n \log n)$ 得到。最后 $1\min$ 调出来，所以这场打的挺好。
启发
- 对于可能出现无限循环的博弈论题，若无限循环的条件很容易考虑，可以将所有能形成无限循环的点忽略掉，只考虑在不循环的条件下的策略，或许能发现一些特殊条件下有用的性质。
AtCoder Grand Contest 006 (2022.12.11 完成)
AT_agc006_a - Prefix and Suffix
枚举即可。
[**]AT_agc006_b - Median Pyramid Easy
凡是构造题都不会是吧。令 $p_n = x,\ p_{n-1} < x,\ p_{n+1} > x$，则无论经过多少次合并，都仍可以使得上述不等式成立，最终使得第一层的值为 $x$。
[**]AT_agc006_c - Rabbit Exercise
推一下式子，发现对 $i$ 操作后使得 $a_i \leftarrow a_{i-1} + a_{i+1} - a_i$。经典的交换差分数组，倍增维护差分数组的置换即可（怎么去年 NOIP 前没做这道题啊）。
[**]AT_agc006_d - Median Pyramid Hard
先套路地二分答案，将排列转化为 $01$ 序列。考察这个 $01$ 序列的层层合并，发现长度 $> 1$ 的连续段会保持不变，长度为 $1$ 的交替出现则会在合并时进行翻转。然后随便 check 一下就好了。
[*]AT_agc006_e - Rotate 3x3
特判掉一些显然不合法的情况后，容易发现这种 $3$ 个地翻转的情况需要分奇偶位讨论。然后要求奇数位的逆序对个数的奇偶性要与偶数位 $1,3$ 行颠倒次数的奇偶性相同，反之同理。必要性显然，因为相邻奇数位交换一次会交换中间偶数位的 $1,3$ 行。充分性不会证，构造出来就可以了吧。
[**]AT_agc006_f - Blackout
比较神的题目。先转化为图论模型，对点进行 $3$ 种颜色的染色，对于有向边 $(u,v)$，令 $col_v \equiv col_u + 1 \pmod{3}$。若无法染色，则说明经过 $(x,y),(y,z) \rightarrow (z,x)$ 的变换，能够使得当前弱连通块成为完全图。否则，若连通块种存在 $3$ 种颜色，则能够形成完全三部图。若存在 $< 3$ 种颜色，则无法形成新的边。对连通块分别处理，答案相加。
AtCoder Grand Contest 007 (2022.12.17 完成)
AT_agc007_a - Shik and Stone
直接 dp 即可。
AT_agc007_b - Construct Sequences
先构造 $a_i = i \times n$，然后令 $b_{p_i} = n^2 + i - a_{p_i}$ 即可。
[**]AT_agc007_c - Pushing Balls
不错的找规律题。把几种情况分别列一列，发现将一个等差数列变换后，相邻两个位置的期望距离仍为等差数列，并且首项和公差可以直接计算得到。于是 $O(n)$ 递推即可。
AT_agc007_d - Shik and Game
设 $dp_i$ 表示 $i$ 及以前的金币都拿到的最小时间，显然有 $dp_i = \min (dp_j + x_i-x_j + \max(T,2(x_i-x_{j+1})))$。里面的 $\max$ 维护一下分界点，外层用单调队列优化一下变成 $O(n)$。
[**]AT_agc007_e - Shik and Travel
考虑二分答案，转化为对所有路径长度 $\le L$ 的判定。考虑设 $dp_{u,i,j}$ 表示对于 $u$ 的子树中，是否存在 $u \to p_1 \cdots p_k \to u$ 的路径，使得所有叶节点都被访问，且 $u \to p_1, \ p_k \to u$ 的长度分别为 $i,j$，转移即从左右儿子合并。但显然这样复杂度会炸掉。
注意到若 $dp_{u,i_1,j_1} = dp_{u,i_2,j_2} = 1$ 且 $i_1 \le i_2, j_1 \le j_2$，那么 $(i_2,j_2)$ 显然不优。只保留最优的二元组，在合并子树答案时枚举左儿子的二元组，使用双指针找到最优的右儿子的二元组，最后进行去重。注意二元组翻转后仍然合法，因此需要使用归并排序时刻保证二元组有序。
考虑二元组数量的量级，设为 $f(u)$，容易知道 $f(u) \le 2 \times \min(f(ls(u)), f(rs(u)))$，类似启发式合并，我们知道 $\sum f(u) = O(n \log n)$，因此总时间复杂度为 $O(n \log n \log V)$。
[**]AT_agc007_f - Shik and Copying String
很妙的题。先考虑将 $T$ 划分为若干连续段，对每个连续段找到在 $S$ 中对应的字母的位置，就得到一个二元组 $(i,j)$ 表示要将 $S_i$ 覆盖到 $T_j,T_{j+1},\cdots$ 中去，需要满足 $i \le j$ 且不存在 $(i_1,j_1)$ 和 $(i_2,j_2)$ 使得 $i_1>i_2,j_1 从右到左扫描二元组，维护一个队列，在队列中加入 $(i,j)$ 的二元组。现在已有 $(i_1,j_1)$，加入 $(i_2,j_2)$，若 $j_2 \ge i_1$，则需要再用一步，否则只需要一步，将 $(i_1,j_1)$ 弹出。再考虑加入 $(i_3,j_3)$，这时将 $j_3$ 与 $i_1 - 1$ 作比较，操作基本同 $(i_2,j_2)$。 而答案就是队列中数的个数的最大值。注意特判 $i=j$ 的二元组。 小分讨，或者把 $\pm x, \pm y$ 拿出来跑最短路。 发现最终的序列中必然有至少一个长度 $\ge k$ 的连续段，枚举其位置，前缀和随便做。 转化为若干个前缀/后缀中至少出现多少个某个数。贪心，先从左往右考虑前缀，将数填入尽量靠前的格子里，然后从右往左填入尽量靠后的。做的时候判断下无解即可。 神题。考虑在排列 $p$ 中，$i$ 向 $p_i$ 连边，那么就形成了若干个环，其中 $i$ 之后的第一或第二个位置必须为 $a_i$。那么现在考虑 $i$ 向 $a_i$ 连边，则每个偶环可能被拆成两个长度相等的、在原环上位置相差 $2$ 的环，每个奇环最多被拆成一个连通块。并且无论奇环偶环，都可能变成一个大环上挂了若干条链的结构。那么枚举每个长度的简单环有多少个合并起来，挂了链的环讨论一下每条链的系数。 阳了好几天，所以这场的 F 咕了好久才做。 先考虑全是关键点的情况。我们希望对于一个连通块 $f(u,d)$ 在 $d$ 最小的时候进行统计，并且为了方便将全集单独统计，那么对每个点 $u$ 求出该点在树上的最长距离 $Mx_1$，需保证 $d < Mx_1$。同时不应存在 $f(u,d) = f(v,d-1)$。 考虑 $f(u,d)=f(v,d-1)$ 时会发生什么，容易知道 $u$ 和 $v$ 一定相邻，且以 $u$ 为根时，除 $v$ 外的其他子树内全部被覆盖。因此需保证 $d < \min_v(\max_{w\neq v} Mx_1[w])+2$，即 $d < Mx_2 + 2$，其中 $Mx_2$ 表示 $u$ 周围的点的 $Mx_1$ 的次大值。再考虑不是关键点，注意到若非关键点的 $u$ 使得 $d$ 最小，则 $u$ 至少覆盖了以 $u$ 为根时，某个关键点的整棵子树，因此求出 $D[u]$ 表示以 $u$ 为根时，包含关键点的子树的深度最大值。 而 $d \in [D[u], \min(Mx_1[u], Mx_2[u]+2))$，对其求和就可以得到答案。 倒过来贪心，记得开 $a_i$ 向 $i$ 连边形成一颗有根树，然后做树形 dp，贪心地合并儿子的最长链即可。 直接 dp，发现到 $dp_i$ 的转移是一段区间，可以用双指针找出，前缀和优化一下变成 $O(n)$。 容易发现这题是搬的POI2004 JAS。因此该题的解法也和那道题的做法相同。顺便复习一下吧。 将合并操作转化为树形结构，得到一棵操作树，其中一个节点要么为叶子，要么有 $k$ 个儿子。并注意到树上权值为 $1$ 的叶子结点会对答案有贡献，具体地，令根节点深度为 $0$，则深度为 $i$ 的权值为 $1$ 的叶子对答案有 $\frac{1}{k^i}$ 的贡献。 一个简单的想法是用 dp 枚举所有深度的 $1$ 的数量，但是这样会算重，原因是 $k$ 个 $1$ 的贡献相当于 $1$ 个上一层的 $1$，我们称这种情况为一次进位。那么在外层枚举总共有多少次进位操作，设为 $x$，并在接下来的计算过程中保证每一层的 $1$ 的个数严格 $< k$。令 $d=\frac{n+m-1}{k-1}$ 即操作次数，在钦定 $x$ 次进位操作后，令 $d' \leftarrow d-x, \ m' \leftarrow m - (k-1)x$，容易发现这时计算的结果就是进位 $x$ 次的结果。 具体如何计算，相当于将 $m'$ 个 $1$ 分配到 $d'$ 层中，每层个数不超过 $k-1$，直接 $O(n^2)$ 地 dp 就好了。 直接统计奇数个数的奇偶性即可。 挺有趣的题的。考虑差分数组，发现若选择 $-1$ 的起点为 $a_1$，则差分数组均为 $1$，否则差分数组中一定存在一项 $1-n$，并且其他项均为 $1$。先求出总操作次数 $num$，然后对于 $i \in [2,n]$，假设其作为起点的次数为 $cnt_i$，那么解一下方程 $(1-n)cnt_i + (num-cnt_i) = a_i-a_{i-1}$，再算出 $cnt_1 = num - \sum cnt_i$，合法当且仅当所有 $cnt_i$ 为非负整数。 先特判掉 $n=1$，然后选一个度数 $>1$ 的点作为根进行 dp，可以发现为了满足所有的 $a_i$，每个子树内向子树外连的边的操作次数是固定的，可以 dp 得到。 若存在 $a_i=1$，则胜负已经由 $\sum a_i-1$ 的奇偶性确定了。至于除掉 $\gcd$ 的操作，若 $\gcd$ 为奇数，则不会改变奇偶性。 考虑若初态 $\sum a_i-1$ 为奇数，则必然存在某个 $a_i-1$ 为奇数，因此存在 $a_i$ 为偶数。对这个偶数进行 $-1$ 操作，这时 $\gcd$ 一定是奇数。而 $a_i$ 不可能全为偶数，否则不满足初始状态的 $\gcd=1$，所以先手操作后会有 $>1$ 个奇数。 若初态为偶，先手会设法通过除以 $\gcd$ 的操作改变奇偶性，其必然会选择局面中唯一的奇数（若存在），将其 $-1$，否则后手将在下一步控制局势。因此若初态为奇，则先手能够保持必胜态，否则找到唯一的奇数，若不存在则必败，将其 $-1$ 后递归。 发现每次递归都会使得 $a_i$ 至少除以 $2$，因此时间复杂度为 $O((n+\log V)\log V)$。 可以发现，若两数互质，则先手可以确定这两个数的相对位置。在互质的数之间连边，则先手需要给这些边定向，后手则是在定向后形成的 DAG 上做字典序最大的拓扑排序，直接用堆维护。先手的策略为找到每个连通块中最小的点，从小到大枚举其相邻的点，得到一棵无向图的 dfs 树。按照这棵 dfs 树对原图的边定向，不在树上的边就不管了，这样能够最大程度使得数字大的点出现在数字小的之后。 从简单的情况入手。对于菊花图，根 $u$ 必胜当且仅当 $a_u > \min a_v$。对于非菊花图，考虑 $u$ 的子树是否必胜。若存在 $u$ 的儿子 $v$ 使得 $v$ 的子树必胜，那么 $u$ 一定不会往 $v$ 走。若存在 $u$ 的儿子 $v$ 必败，那么走到 $v$ 之后对方一定会走会 $u$，这与菊花图无异。那么子树 $u$ 必胜当且仅当 $a_u > \min_{v\text{必败}}a_v$。直接 $O(n^2)$ dp，或者用换根可以做到线性。 贪心让一辆车带尽量多的乘客即可。 二分答案，然后判断时模拟一下，让第 $mid$ 个从小往大贪心地合并。 赛时思维比较混乱。画了一些情况，发现排除了孤立点后，答案和每个连通块在原图上是否是二分图有关，但是又不知道 $(x,y)$ 不在同一个连通块里是什么情况。赛后看题解，才知道只要任何一个点处于非二分图中，那么整个新图的这部分贡献就是 $1$，否则是 $2$。 简单手玩一下，发现若 $s_0=\text{A}$ 则直接将 $s_0 \leftarrow \text{B}$。否则小球一定会走到最右边，然后对于 $i < n$，将 $s_i \leftarrow \lnot s_{i+1}$，同时 $s_n\leftarrow \text{A}$。这样以来，经过至多 $2n$ 次以后，序列会变成形如 看一眼，大概有个贪心的思路，就是找到尽量长的递增前缀，从第一个不递增的位置开始改成 $0$，然后减一，例如对 $1235223$ 构造 $1234999$，剩下来的数变成 $224$。但是发现对于 $224$，这样构造出来的会变成 $219$，不是个递增的数。那么改为找到最后一个前缀递增的连续段，将该连续段的第一个数减一，后面全部填 $9$，这样 $224$ 就构造出 $199$，以此类推。 考虑如何模拟该过程，维护当前的 $n$，前缀可以暴力清零，然后每次操作暴力高精度 $+1$，复杂度均摊 $O(n)$。如何找到最后一个连续段呢？可以用一个线段树，维护区间 $\min/\max$，在上面二分出下一个不同的位置，多带一个 $\log$。VP 的时候瞎写了一通，没想到直接一遍过了，震惊。 $St(i) = \sum_{j=1}^{i}t_j, \ Sp(i) = \sum_{j=0}^{i}p_j, \ Sq(i) = \sum_{j=0}^{i}q_j$。 其中 $t_i$ 表示区间 $i$ 的通过用时，$p_i$ 表示 $0 \to n$ 的车在站台 $i$ 的等待时间，$q_i$ 同理表示 $n \to i$ 的车。 $0\to n$ 的车，在路段 $i$ 占用的区间为 $(St(i-1) + Sp(i), St(i) + Sp(i))$。 $n \to 0$ 的车，在路段 $i$ 占用的区间为 $(-St(i)-Sq(i), -St(i-1)-Sq(i))$。看作是反过来行走，在 $\bmod k$ 意义下相同。 若是单向铁路，则要求两区间在模 $k$ 意义下无交。转化为一个区间的端点不被另一个区间包含，需要注意某些边界是闭还是开。 综合上式，令 $x_i = Sp(i) + Sq(i)$，有 $x_i \notin (-2St(i),-2St(i-1))$，即 $x_i \in [-2St(i-1), -2St(i)]$。 对 $x_i$ 的另一个约束就是，$x_i \ge x_{i-1}$。 考虑 dp。设 $dp_k[i]$ 表示第 $k$ 个约束后，使得 $x_k=i$ 的最小代价。考虑答案要我们求的部分，则代价应表示为 $x_k - x_0$，而 $x_0$ 可以为任意值。 每次操作时，给出模意义的区间为 $[l,r]$，则将 $[l,r]$ 以外的位置转移到 $l$ 上，然后设为 $+\infty$。线段树维护 $dp_k[i] - i$ 的区间 $\min$ 即可，$O(n\log n)$。 第 $2,4,\cdots,2n$ 大的数之和。 $col[u][i]$ 表示能够覆盖到 $u$，且剩余能覆盖距离为 $i$ 的最后一个被染的颜色，离线下来转移一下。 串长为字符集大小的 $2$ 倍，提示我们每种字符被用了 $2$ 次。考虑序列 $\{1,2,\cdots,k,p_1,p_2,\cdots,p_k\}$，这个序列的答案为排列 $p_1,\cdots,p_k$ 中的上升子序列个数。 考虑已有排列 $p_1,\cdots,p_{k-1}$，其上升子序列个数为 $x$，现在加入 $p_k$。若放到序列首，则 $x' \leftarrow x+1$。若放到序列末，则 $x' \leftarrow 2x$。如此可以构造出指数级别的答案。 对于球 $i$，若其不能与任何球交换位置，则对答案没有贡献。先去掉这些球。 对于颜色 $c$，若其最小的那个球不能和别的颜色的球交换位置，那么这种颜色的位置已经固定了，也把它们去掉。 容易发现，对于剩下的球，可以任意交换位置。那么假设剩下 $s_i$ 种颜色 $i$ 的球，则答案为 $\frac{(\sum s_i)!}{\prod s_i!}$。 不是很难的 E 。 可以发现骆驼只能跳 $O(\log V)$ 次，那可以对这 $O(\log V)$ 种驼峰的大小，求出从每个绿洲能够向左向右拓展到的边界，容易知道整个序列被划分为若干段。 考虑状压，对于每个状态 $S$，求出 $dp_L(S)$ 表示从左边开始走，经历了 $S$ 中的驼峰大小，能走到的最长前缀，$dp_R(S)$ 同理表示从右边开始走到的最长后缀。枚举状态 $S$，假设其除了初始的驼峰大小之外的补集为 $T$，若区间 $(dp_L(S),dp_R(T))$ 在初始驼峰大小的同一个段中，那么这个段就是 时间复杂度 $O((n+V) \log V)$。 很好的计数 dp 题。 首先看到这种奇怪的限制，先去找充要条件。容易知道 $b_i \in [i,2n-i]$，但光是这个条件还不够充分。 考虑现在有一个集合 $S$，中位数为 $m$。往里面塞两个数 $a$ 和 $b$，若 $a,b > m$，则中位数 $m'$ 变为 $m$ 的后继。若 $a,b < m$，则中位数 $m'$ 变为 $m$ 的前驱。否则，$m' \leftarrow m$。 也就是说，$b_i$ 与 $b_{i+1}$ 在前缀的集合中应该是连续的。形式化地说，不存在 $j < i$ 使得 $b_i < b_j < b_{i+1}$（或 $b_i > b_j > b_{i+1}$）。 这个条件充分吗？结合 $b_i \in [i,2n-i]$ 的条件，构造几个序列感受一下，好像充分了。 那么该思考如何计数了。下标越靠后限制越紧，考虑倒着做。我们每选择一个 $b_i$，就将区间 $(b_i,b_{i+1})$（或者 $(b_{i+1},b_i)$）给 ban 掉。$dp[i][L][R]$ 表示考虑到后缀 $i$，比 $b_i$ 小的数中，有 $L$ 个元素没被 ban，比 $b_i$ 大的有 $R$ 个没被 ban。转移时枚举那 $L/R$ 个元素作为新的 $b_i$，可以做到 $O(n^4)$，差分一下转移就能 $O(n^3)$ 了。 简单做一个 dp，$dp[i][0/1]$ 分别表示以 $i$ 结尾的上升/下降段长度。 发现这个限制很有意思，直接找一个点，向前向后能扩展就扩展即可。 比较有意思，首先能够发现蚂蚁之间的相对位置永远不会发生变化。两只蚂蚁相撞并掉头，实际上可以看作是穿过对方，然后交换这两只蚂蚁的编号。这样我们就求出了每只蚂蚁最终的位置，只不过不知道对应的编号。 由于蚂蚁间的相对位置并不发生变化，所以我们只要找到初始时第一只蚂蚁最终的编号，就能推出每一只蚂蚁对应的编号。 考虑交换编号的过程，假设第一只蚂蚁顺时针走，每碰到另一只蚂蚁，由于碰到的这只蚂蚁编号一定与自己相邻，所以自己的编号会在 $\bmod n$ 意义下 $+1$。如果其逆时针走，则同理在 $\bmod n$ 意义下 $-1$。因此可以考虑枚举其反方向的蚂蚁，通过小学奥数知识容易计算出在 $T$ 的时间内会相遇几次，如此求出其最终编号。 需要注意的是，对每只蚂蚁算出其位置后，一定要记得排序。并且若最终第一只蚂蚁与某只蚂蚁停在同一点，一定要根据自己的式子仔细思考一下边界情况。 并非很难的题目吧。先考虑 $dp[i][j]$ 表示 $i$ 次操作后有 $j$ 个红球的方案数，但是直接做会把颜色序列算重。所以考虑在 $j=0$ 或 $j=1$ 且在一次操作中先后取出了红球和蓝球时统计，增设一维 $0/1$ 状态表示是否到达过上述情况即可。 一开始看错题了，以为贡献是正方形面积之和，那样推出来的矩阵大小就比较大了。 然后转而发现贡献是面积的乘积，然后就是一道 sb 题了，随便推推 $3 \times 3$ 的矩阵吧。 为了方便起见，将 $C$ 中的值离散化到 $[1,n]$ 中，$A$ 和 $B$ 则二分找到最后一个满足 $\le C_i$ 的位置。 根据 Hall 定理，$\{X_1,\cdots,X_n\}$ 可以与 $\{1,\cdots,n\}$ 匹配的充要条件为，考虑初始值为 $s_i=-i$ 的序列 $s$，每次将区间 $[X_i,n]$ 增加 $1$，能够使得 $s_i \ge 0$。 不妨先钦定这 $n$ 张牌都是正面，则将某张牌 $i$ 翻到反面，会使得区间 $[B_i,A_i)$ 增加 $1$。若不考虑 $q$ 组询问中新加入的值，则问题就变成形如 “给定序列 $s_i$，你可以对若干区间进行 $+1$ 操作，使得最终 $s_i \ge 0$，最少需要进行多少次操作”。 而 $q$ 次询问，可以暴力枚举使用 $D_i$ 还是 $E_i$ 作为新加入的值，问题转化为对于每个 $i \in [1,n]$，预处理出 $Ans_i$ 表示将 $s_i,\cdots,s_n$ 的限制改为 $\ge -1$ 即可后，最少需要将多少个正面变成反面。 接下来一步非常结论，可以证明，设 $i$ 是最大的 $s_i < -1$ 的位置，$S=[l,r]$ 是 $l$ 最小的包含 $i$ 的区间，则最优解一定会选择 $S$。 证明：考虑某个不包含 $S$ 的最优解，其右端点最小的包含 $i$ 的区间为 $T$。 因此，用 这时只需要不停贪心选包含最左边的 $-1$ 而右端点最靠右的区间，与上面的贪心过程差不多，同样用一个 感性理解一下发现大约 $\log V$ 次之后就会出现奇数或是进入循环，于是稍微模拟一下就行。 由于边权都变成了偶数，因此可以发现一定是若干形如 $(u_1,u_2),(u_2,u_3),\cdots,(u_k,u_1)$ 的询问形成首尾相接的环，判断一下每个节点出现的次数是否都为偶数即可。 将前一次操作的 $k$ 次解锁与后一次操作的 $k$ 次移动放到一起看，可以在前一次操作中解锁后一次会移动到的格子，那么除了第一次操作的 $k$ 步之外都能随便走。BFS 处理一下起始点 $k$ 步以内能到达的位置，取这些位置到出口的距离最小值计算一下即可。 很厉害的结论题。如果树存在完美匹配，那么后手每次取跟先手对应的点即可。否则，先手每次取一个和叶子结点相邻的点，后手不得不取该叶子结点，然后将这两个人点从树上删去，容易知道会剩下若干个点，且跟这些点相邻的点都被先手染成了白色。 那么，问题转化为是否存在一个树上的完美匹配。直接一遍树形 dp 就好了。 正着做比较难，那么反过来考虑。假设第 $n-1$ 条被转化的链为 $(u_{n-1},v_{n-1})$，那么容易知道 $(u_{n-1},v_{n-1}) \in E_R \cap E_B$，其中 $E_R, E_B$ 分别表示红边与蓝边集合。 再考虑第 $n-2$ 条被转化的链。现在已知的信息是 $(u_{n-1},v_{n-1})$ 为蓝色，那么可能的点对 $(u_{n-2},v_{n-2})$ 要么本身就在 $E_B$ 中，要么就是由某条 $E_B$ 中的边与 $(u_{n-1},v_{n-1})$ 拼接而成。以此类推，第 $i$ 条链一定是由某条 $E_B$ 中的边与若干第 $>i$ 条链中的边拼接而成的。 这样思考起来略显麻烦，不妨考虑一种巧妙的转化。当我们考虑完第 $i$ 条链时，就将 $u_i$ 与 $v_i$ 两个点合并，得到新的边集合 $E_R',E_B'$。这时再去考虑第 $i-1$ 条链，容易发现其应满足 $(u_{i-1},v_{i-1}) \in E_R' \cap E_B'$。 因此，我们不妨模拟整个倒序的过程，使用 首先，可以看出元素 $1$ 并不影响其他元素是否为 high 或 low。即使我们先不考虑元素 $1$，序列的操作也相差无几。 令 $T$ 表示去除元素 $1$ 后，剩下的序列需要的操作步数。如果最终 $1$ 在序列首，那么答案为 $T$，否则答案显然是 $T+1$。那么现在我们希望知道进行若干次操作后 $1$ 在序列中的位置。 当 $T=0$ 时，显然 $1$ 的位置就是其在原序列中的位置。现在考虑 $T>0$ 的情况，并考虑在 $T-1$ 轮后序列的情况。假设 $T-1$ 轮后，$2,3,\cdots,n$ 所形成的序列的首位为 $f$，显然 $f>2$，否则要么序列在 $T-1$ 轮后就有序，要么在 $T$ 轮后仍然无序。不难知道，若 $T-1$ 轮后，$1$ 在 $f$ 与 $2$ 之间，则答案为 $T$，否则答案为 $T+1$。 接下来我们将证明一个重要的结论，即前 $T-1$ 轮中，$1,2,f$ 的循环顺序不会改变（我们称 $(a,b,c),(b,c,a),(c,a,b)$ 为相同的循环顺序）。 首先，让我们证明前 $T-1$ 轮中，除非其处于 $2,3,\cdots,n$ 之首，否则 $f$ 永远不会成为 high 元素。假设在某时刻，某元素 $x$ 为 high 且不在序列首。由于序列首一定是 high 元素，所以在这次操作后，必然存在一个元素 $y$ 移动到了与 $x$ 相邻的左边，并且 $y 现在，让我们回到原问题当中去。思考一下 $1,2,f$ 的循环顺序是否会产生变化： 于是我们证明了上述结论，即 $1,2,f$ 的循环顺序在前 $T-1$ 轮中不会改变。这样一来，我们可以通过 $1,2,f$ 在原序列中的循环顺序，判断 $T-1$ 轮后 $1$ 是否在 $f$ 与 $2$ 之间，依次区分答案是 $T$ 还是 $T+1$。 因此，$i,i+1,\cdots,n$ 的子问题从 $i+1,i+2,\cdots,n$ 的子问题转化而来。令 $T_i$ 表示 $i,i+1,\cdots,n$ 的子问题的答案，$f_i$ 表示该子问题中第 $T_i-1$ 轮后的首元素，$q_i$ 表示 $i$ 在初始序列中的位置，则转移如下： 原问题在 $O(n)$ 的复杂度内解决。 写题不看数据范围，不特判 $A>B$ 和 $n=1$，罚时增加 $5\min$。 $f(i,j) = 1 + [i 都说了连通块是树，那问你有多少个连通块不就是问森林中有多少棵树吗？直接 $|V| - |E|$ 就好了。所以这是手速场？ $A$ 和 $B$ 的公共前缀一定会在答案当中，那么把这段公共前缀去掉，现在新的 $L$ 和 $R$ 最高位一定不同。假设 $R$ 的最高位为 $d$，考虑其中的数能构成的区间。 容易发现没有别的区间能够被表示出来了。 那么答案就是这 $3$ 个区间的交了。注意可能 $R$ 并不存在次高位，此时没有第 $3$ 个区间。 考虑最终的情况，点的相对顺序一定是按照 $(v_i,x_i)$ 的二元组排序后的结果。那不妨先按照次二元组排序，并给点重新分配编号。 考虑将 $i$ 染色后，有哪些点会被染到，被 $i$ 染色的点一定是一个区间 $[l,r]$，使得 $l=\min\{j\mid x_j \ge x_i\}$ 且 $r = \max\{j \mid x_j \le x_i\}$。 求出每个点对应的区间后，问题转化为选择若干个区间，其并集为全集的方案数。dp 一下就可以了。 枚举最终串剩下的字符，然后模拟一下。 假设一共有 $x$ 种不同的颜色，显然每只猫能看到 $k$ 种颜色当且仅当存在另一只猫的颜色与它相同，否则它将看到 $k-1$ 种颜色。分类讨论统计一下序列 $\min/\max$ 以及个数即可。 根据样例 $1$ 的提示，可以按照每个 $h\times w$ 的矩形中都放一个 $-h\times w$，其他位置放 $1$ 来构造，但发现只有一行或一列时会出现问题。那么在每 $h\times w$ 的位置放一个 $-1000 \times h \times w + 999$，其他位置放 $1000$ 就可以了。 判断是否合法非常容易，因为可以发现操作相当于先令 $a_{n+1}=a_1\oplus a_2 \oplus\cdots\oplus a_n$，然后每次交换 $a_i$ 和 $a_{n+1}$。将 $a_1,\cdots,a_{n+1}$ 和 $b_1,\cdots,b_{n+1}$ 分别排序后看是否相同即可。 先考虑一种特殊情况，即所有数字互不相同，这是个经典的问题。那么每个数字有一个在序列 $a$ 中的初始位置和 $b$ 中的结束位置。对于所有 $1 \le i \le n + 1$，设 $p_{b_i}=i$，将 $i$ 与 $p_{a_i}$ 连边，这构成了若干个环。此时答案即是 $|E| + C - 1$，$C$ 是连通块数。至于原因，对长度为 $x$ 的环可以通过 $x-1$ 次操作完成，而和 $n+1$ 不在一个连通块中的环需要额外的 $1$ 次操作使得 $n+1$ 位置的数变为该连通块中的数。 考虑拓展到一般的情况，那么对于 $a_i \neq b_i$，直接在 $a_i$ 和 $b_i$ 之间连边即可。这样有的连通块可能不是环，但是没关系，仍可以用上述公式计算出答案。 挺简单的题，不知道为啥评黑（似乎我刚做完就被管理降成紫了）。 注意到 $n$ 非常小，考虑直接枚举火鸡对 $(i,j)$ 并判断是否合法。对于某个人 $i$，若希望 $a_i$ 存活下来，则需要满足在 $i$ 时刻之前 $b_i$ 没有被吃掉。因此可以从后向前考虑每个时刻，维护当前时刻必须存活下来的火鸡集合 $S$。如果某一时刻要求 $a_i$ 和 $b_i$ 都存活，那么显然就不合法了。 发现并不需要考虑所有时刻，只需要每次二分出再此之前的最后一个 $i$ 使得 $a_i \in S$ 或 $b_i \in S$。注意到每次二分之后，集合 $S$ 的大小至少增加 $1$，所以只需要二分 $O(n)$ 次。用一个堆维护一下 $S$ 集合中每个火鸡的上一个时刻，可以做到 $O(n^3\log n + m)$。 算不上很难的状压 dp 题。 既然是 DAG 上的博弈问题，先考虑将胜负转化为 SG 状态，发现先手必胜即为 $SG(1) \oplus SG(2) \neq 0$。统计 $SG(1) \oplus SG(2) = 0$ 显然要容易一些。 思考一张 DAG 上的合法 SG 状态，必然是将点集划分为若干 SG 值相等的层。对于 $SG=k$ 的层中的点 $p$ 以及任意 $i 注意到 $n$ 非常小，考虑状压 dp。假设已经确定了 $S$ 中的点的 SG 状态，考虑加入新的一层，点集为 $T$。发现若加入的一层 SG 值最大则不太好考虑，毕竟要向已经考虑过的每一层连边，但若加入的一层 SG 值最小就较为容易。具体地，对于 $i \in S$，需要让 $i$ 连向 $T$ 中的至少一个；对于 $i \in T$，$i$ 可以向 $S$ 随意连；同时 $T$ 中的点之间没有任何边。暴力枚举子集，稍加预处理，就可以做到 $O(n\times 3^n)$。 而现在要求 $SG(1) \oplus SG(2) = 0$，那么显然 $1$ 和 $2$ 需要在同一层，直接在枚举 $T$ 的时候加以判断即可。 就是随便瞎 dp 一下就可以了。 发现没法直接维护区间合法区间，因为区间的段数是指数级别的。但是若枚举一下有多少个 $+[C,D]$ 和多少个 $-[C,D]$，合法的区间就只有一段了，并且可以直接算出来。 很巧妙的转化，先开个桶统计一下 $a_j=i$ 的 $j$ 有 $num_i$ 个，将区间 $(i-num_i,i]$ 覆盖一次，可以发现区间 $[1,n]$ 中没有被覆盖的位置个数就是最终的答案，也很好维护。 这不是树上 Nim 博弈的板子吗？用 SG 函数随便搞搞就好了。 将一块积木看作是从一个插头状态向另一个插头状态的转移，容易发现这形成了一张有向图，其中点数是 $O(H)$ 级别，边数为 $n$。需要找到若干条路径覆盖每条边恰好一次，使得路径从 $C_i=0$ 的状态开始，到 $D_i=0$ 的状态结束。 容易知道，对于 $C_i=0$ 的状态，其入度需要 $\le$ 出度，对 $D_i=0$ 的状态则相反。先特判掉这种情况。接下来不妨对每个连通块分开考虑，若该连通块中不存在入度 $\neq$ 出度的点，那么就会没有一条合法的路径能够覆盖它，也判掉。容易证明剩下来的图均能够被若干合法路径覆盖。 考虑从左到右依次确定每一条折线。使用类似插头 dp 的方法，$dp[i][j][k][S]$ 表示考虑第 $i$ 条折线的第 $j$ 个转折点，其中第 $i-1$ 条折线在该行的位置为 $k$，第 $i-1$ 条折线与第 $i$ 条已确定的部分所构成的边界为 $S$。这样状态数是 $O(n^2m2^n)$，转移数 $O(1)$，但仍需要一定的优化。 注意到我们其实并不需要记录第 $i-1$ 条折线在该行的位置 $k$，仅需要根据折线 $i-1$ 在第 $j$ 个转折点的操作判断折线 $i$ 是否能够向左下转移。具体而言，如下图所示，若当前考虑到箭头所指的点，蓝色折线为第 $i-1$ 条折线，红色为第 $i$ 条已确认的部分，那我们不妨认为绿色折线就是第 $i-1$ 条折线。容易知道，将绿色折线看作第 $i-1$ 条折线并不会和蓝色折线对接下来的决策有任何不同。 因此，在枚举第 $i$ 条折线的转移时，顺便更新一下第 $i-1$ 条折线的位置。状态优化掉一维 $n$，复杂度 $O(nm2^n)$ 可以通过。 后面会更倾向于做题，题解可能不会再写的如此详细，甚至会干脆不写。毕竟写题解还是花了不少时间的。 WC2023 打铁了，没有 Au 跟打铁没啥区别。年前先去把 POI 做完。 AtCoder 居然出计算几何了。 比较常规的思路是，对于每个关键点 $P_i$，枚举所有其他关键点 $P_j$，显然只有在 $P_i$ 与 $P_j$ 的中垂线靠近 $P_i$ 的这一侧才会走到 $P_i$。那么能够走到 $P_i$ 的点集可以看作是若干个半平面的交，假设这个点集为 $S_i$。容易知道走到该点的概率为 $\frac{|S_i|}{|S|}$，其中 $S$ 为整个坐标系的点集。 当然我们不必真的去写一个半平面交。注意到整个坐标系 $S$ 可以看作是无限的。若 $S_i$ 为有穷集合，走到该点的概率可以忽略不计，我们不妨直接不考虑这些 $S_i$。而剩下来的 $S_i$ 为无穷集合的关键点，简单想象一下就会发现它们一定在由关键点构成的凸包上。那么原问题转化为以一个凸多边形的点集为关键点的新问题。 考虑上面这张样例 2 的图。对凸包上的点 $D$ 来说，会走到它的点集显然就是 $BD$ 的中垂线与 $CD$ 的中垂线上面一部分的交，对于其他点也是类似的相邻两边的中垂线之间的部分。如果这样还看不出来答案，不妨保留右上图中的有用的射线，再将整张图缩小得到右下角的形状。如此一来，每个点的答案显而易见，就是，两条相邻中垂线之间的夹角除以周角。 回到原题中，由于 $n$ 非常小，我们完全不必求出整个凸包再计算出中垂线的角度，只需分别以每个关键点为中心，对其他关键点极角排序，得到排序后相邻两关键点最大的间隔角度，再此基础上减去 $180\degree$ 就得到了答案。$O(n^2\log n)$。 越往后越咕咕咕了。 D 是很有趣的构造 校内的训练强度还是很高的。 计算逆序对个数即可。 有个比较显然的观察，即对于任意的 $y$，都存在唯一的 $x$ 使得 $x \le y$ 且 $x + y = 2^k$。那么将所有不同的数看作点，将能匹配的两个数之间连边，形成了一个森林（可能有的点可以和自己匹配，而这些点一定是连通块中的最小值）。显然能够从大往小贪心匹配，使得不能和自己匹配的点尽量匹配上。 显然答案具有可二分性，先二分字符集的大小设为 $k$。 容易进行一个贪心的匹配，即当 $A_{i-1} < A_i$ 时，直接在 $S_{i-1}$ 末尾添加若干个字符 考虑如何维护这个贪心，可以使用一个栈维护所有不为 诈骗题，看起来是一个博弈，但实际上容易发现先手一定会移动，否则倘若先手不操作，后手同样可以不操作以结束游戏。 依次考虑每一行，使用 set 维护所有能够到达的位置区间。对于该行的障碍 $(x,y)$，如果上一行能够到达 $(x-1,y)$，则直接更新答案。然后遍历 set 中的每个区间，将其右端点 $+1$，尽量合并能够合并的段。再根据当前行的障碍物将区间划分开来，不难发现复杂度是均摊的 $O(n \log n)$。 令 $pos_i$ 表示 $i$ 在最终序列中的位置。对于逆序对，很容易想到对于 $i < j$ 计算 $pos_i > pos_j$ 的方案数，而 $n \le 3000$，显然可以枚举点对 $(i,j)$ 并加以计算。 考虑倒序枚举所有的交换操作，并维护 $dp[k][i][j]$ 表示只考虑操作 $k \sim q$，使得位置 $i$ 的元素最终被移动到的位置 $end_i$ 大于位置 $j$ 的元素最终位置 $end_j$ 的概率（使用概率而不是方案数只是为了更好地进行转移）。dp 的初值容易发现就是 $dp[q + 1][i][j] = [i > j]$。 考虑交换操作 $(x,y)$ 对 dp 值的影响。对于 $i \notin \{x,y\}$，显然此次操作无论如何不会使得 $end_i$ 被改变，因此只有 $dp[k][x][i],dp[k][y][i],dp[k][i][x],dp[k][i][y]$ 这 $O(n)$ 个位置的值发生了改变。具体如何改变，显然 $dp[k][x][i] \leftarrow \frac{1}{2}(dp[k + 1][x][i] + dp[k + 1][y][i])$，容易 $O(1)$ 计算。 将 dp 数组的第一维滚动掉，那么时间复杂度降为 $O((n+q)n)$，空间复杂度 $O(n^2)$。 首先，若 $A_{2i-1} \neq -1$ 且 $A_{2i} \neq -1$，则位置 $B_i$ 的值是确定的，将这些位置从序列中去除掉以便于讨论。 设 $v_i$ 表示 $i$ 是否已经强制确定了在 $A$ 中的位置。题意容易转化为找到一个大小为 $n$ 的匹配，满足 $1 \sim 2n$ 中的每个值都在匹配当中，且对于满足 $i < j$ 的匹配 $(i,j)$，其权值为 $i$，需要满足 $v_i = 0$ 或 $v_j = 0$，计算其填入数组 $B$ 的方案数。 考虑使用线头 dp，设 $dp[i][j][k]$ 表示考虑了 $i \sim 2n$ 中的数，其中还有 $j$ 个 $v=0$ 的线头未匹配，$k$ 个 $v=1$ 的线头未匹配，此时的方案数。并根据 $v_i$ 的值决定 $dp[i][j][k]$ 从何转移而来： $v_i = 0$，$dp[i][j][k] \leftarrow dp[i + 1][j + 1][k]$，让 $i$ 匹配一个 $v=0$ 的线头。 $v_i = 0$，$dp[i][j][k] \leftarrow dp[i + 1][j][k + 1]$，让 $i$ 匹配一个 $v=1$ 的线头，这时需要在 dp 的过程中确定与具体哪一个线头进行匹配以确定在 $B$ 中的位置，因此附带转移系数 $(k+1)$。 $v_i = 0$，$dp[i][j][k] \leftarrow dp[i + 1][j - 1][k]$，容易理解，添加一个 $v=0$ 的线头。 $v_i = 1$，$dp[i][j][k] \leftarrow dp[i + 1][j + 1][k]$，匹配 $v=0$ 的线头。 $v_i = 1$，$dp[i][j][k] \leftarrow dp[i + 1][j][k - 1]$，添加一个 $v=1$ 的线头。 不难发现 $v_i=1$ 不能匹配 $v=1$ 的线头。 初始时 $dp[2n+1][0][0] = 1$，答案即 $dp[1][0][0]$。 此时对于匹配 $(i,j)$，仍有 $v_i = v_j = 0$ 的匹配未确定其在 $B$ 中的位置。但注意到这样的匹配数量是可以简单计算得到的，即 $n - \sum[A_{2i-1} \neq -1 \lor A_{2i} \neq -1]$，最后乘上其阶乘即可。 难以想象这是 AGC 的 F 题。连我也能切掉。 遇事不决先往后推几项，定义 $p \circ q = \{p_{q_i}\}$，则有 $f(p,q) = \{q_{p^{-1}_i}\} = q \circ p^{-1}$。 通过观察可以得知，$a_i$ 相当于在 $a_{i-1}$ 的基础上，将所有的 $p$ 替换为 $q$，$p^{-1}$ 替换为 $q^{-1}$，$q$ 替换为 $q \circ p^{-1}$，$q^{-1}$ 替换为 $p \circ q^{-1}$（我也不知道这步观察是怎么想到的，总之看起来很对）。我们称其为一次变换。 同样可以发现的是，从 $a_5$ 开始，之后的所有式子都含有 $q \circ p^{-1} \circ q^{-1} \circ p$ 的前缀，不妨将其设为 $A$。这有什么用呢？对 $A$ 做一次上述变换后，得到的结果仍然是 $A$。我们可以在接下来的推算中以 $A$ 代替所有这样的式子： 这样就看出规律来了，容易发现对于 $n > 6$ 有 $a_n = A \circ a_{n-6} \circ A^{-1}$。而 $\circ$ 运算具有结合律，因此可以用快速幂求出 $A^{k/6}$ 以及 $A^{-(k/6)}$ 做到 $O(n \log n)$ 计算答案。 数据范围很小以及奇怪的限制，一眼网络流。 对于某个前缀 $\le x$ 并且后缀 $\le x$ 的限制，套路地先枚举偷走的物品的总个数，将其都转化为前缀。 简单建立一下行和列之间的二分图，跑一下费用流即可。 居然还要特地开 一道不可多得的、将数论巧妙隐藏成图论的好题。 考虑如果正着做 $s \to t$ 的路径，就需要记录权值以及步数两个信息，不太容易考虑。倘若反过来考虑 $t \to s$ 的路径，就只需要记录当前权值，每经过一条长度为 $w$ 的边就令 $x \gets 2x + w$。 考虑使用 $(u, x)$ 表示当前节点为 $u$，路径权值为 $x$ 的状态。每经过一条边 $(u, v, w)$ 可以将 $(u, x)$ 变为 $(v, 2x + w)$，不妨在这两个状态之间连有向边。 现在我们有 $n \times M$ 个状态，其中 $M$ 表示模数，每次询问查询是否能从 $(t, 0)$ 走到 $(s, r)$。 注意到 $M$ 为奇数，那么 $\gcd(2, M) = 1$，由欧拉定理可得 $2^{\varphi(M)} \equiv 1 \pmod{M}$。 考虑从状态 $(u, x)$ 开始，反复走 $(u, v, w)$ 这条边，经过的状态形如 $(u, x) \to (v, 2x + w) \to (u, 4x + 3w)$。 每次到达某个状态，权值均为 $2^ix + (2^i - 1)w$ 的形式。当 $i = \varphi(M)$ 时，权值将变回 $x$。同时由于 $M \ge 3$ 且为奇数，因此 $\varphi(M)$ 为偶数，第 $i$ 步的状态恰好回到 $(u, x)$。 所以说，若状态 $(u, x)$ 能够到达 $(v, y)$，那么状态 $(v, y)$ 一定也能够通过某种方法到达 $(u, x)$。这意味着我们可以将状态之间的有向边改为无向边。使用并查集维护状态间的合并，可以做到 $\mathcal O((n + m) \times M)$。 假设有两条边与 $u$ 相连，分别为 $(u, v_1, a)$ 和 $(u, v_2, b)$，考虑这时将发生什么。 从状态 $(u, x)$ 开始，可以走到 $(v_1, 2x + a)$，再回到 $(u, 4x + 3a)$。同理可以走到 $(u, 4x + 3b)$。此时状态 $(u, 4x + 3a)$ 与 $(u, 4x + 3b)$ 会处于同一联通块中。而 $4$ 在 $\bmod M$ 意义下存在逆元，因此对于任意的权值 $x'$，一定能构造出 $x$ 使得 $x' = 4x + 3a$，因此状态 $(u, x)$ 与 $(u, x + 3(b - a))$ 连通。 由于题目保证整张图连通，因此求出所有边权之差的 $\gcd$，设为 $g'$。令 $g = \gcd(g', M)$，根据剩余系的相关知识，$(u, x)$ 会和 $(u, x + 3g)$ 连通。 令 $M' = \gcd(3g, M)$，可以将权值这一维从 $\bmod M$ 改为 $\bmod M'$。下文中将直接用 $M$ 来表示 $M'$。 考虑一个边权 $w$，其能够被表示为 $kg + z$，$z$ 是一个固定的常数。 如果将边权表示为 $kg + z$ 会略显麻烦，不妨将所有边权减去 $z$，并考察权值 $x$ 相应的更改。 注意到若使用 $(u,x)$ 表示原状态的 $(u, x + z)'$，则经过一条边 $(u, v, w + z)$ 后，原状态将更新为 $(v, 2(x + z) + w - z)'$，即 $(v, 2x + w + z)'$，恰好为新状态 $(v, 2x + w)$ 所对应的原状态。因此对于每个询问，我们现在只需考虑新的状态中 $(t, z)$ 是否可达 $(s, r + z)$。 经过边权的转化后，我们同样发现，一个状态 $(u, x)$ 能够到达的状态均能被表示为 $(v, 2^px + qg)$。根据性质二，当 $q \equiv q' \pmod{3}$ 时，$(v, 2^px + qg) \iff (v, 2^px + q'g)$，因此只需取 $q \in \{0, 1, 2\}$ 以简化状态。 由因为 $(u, 2^px) \iff (v, 2^{p + 1}x + qg) \iff (u, 2^{p + 2}x + 3qg) \iff (u, 2^{p + 2}x)$，所以同样令 $p \in \{0, 1\}$。 这样一来，所有 $(u, x)$ 可达的状态均能够被表示为 $(v, 2^px + qg)$，其中 $p \in \{0, 1\}, q \in \{0, 1, 2\}$，总状态数被简化为 $6n$，可以接受的范围内。 现在，问题就在于如何根据简化后的状态来判断 $(t, z)$ 是否可达 $(s, r + z)$ 了。 记新状态 $[u, p, q]$ 表示所有形如 $(u, 2^px + qg)$ 的状态。对于原图上一条 $(u, v, w + z)$ 的边，状态 $[u, p, q]$ 应连向状态 $[v, p + 1, 2q + w / g]$。 $(t, z)$ 能到达 $(s, r + z)$，显然等价于存在 $p,q$ 使得 $[t, 0, 0]$ 与 $[s, p, q]$ 联通，且同时存在 $k_1, k_2$ 使得 $r + z \equiv 2^{2k_1}z + (q + 3k_2)g \pmod{M}$。 注意到 $M \mid 3k_2g$，因此只需存在 $k$ 使得 $r + z \equiv 2^kz + qg \pmod{M}$。 预处理出 $[0, M)$ 中能够被表示为 $2^kz$ 的数，只需循环 $\varphi(M)$ 次，然后判断 $r + z - qg$ 是否在其中，即可 $\mathcal O(1)$ 回答询问。 综上所述，本题总时间复杂度线性。 分连通块考虑，不存在欧拉回路（有度数为奇数）显然无解。考虑计算每个连通块最多能被拆成多少条回路，判断其总和是否 $\ge 3$。 回路个数 $\ge 2$ 是显然的，只需判断是否存在度数 $> 2$ 的点。考虑什么时候一个连通块只能拆成 $2$ 条回路，一定是因为其只能构成 $2$ 个环。 真的是这样吗？仔细想想会发现如果存在点 $a, b$ 且 $a, b$ 之间恰有 $4$ 条路径时，dfs 找环能找出 $3$ 条环，然而能够拆出的回路数量只有 $2$。判掉这种情况，具体而言，注意到此时 $a,b$ 的度数均为 $4$，剩下点的度数均为 $2$ 且都在 $a, b$ 之间。剩下来的情况就全是 $\ge 3$ 了。 最后修改于 2025-07-01 Git 版本:
d2f4fc0启发
AtCoder Grand Contest 008 (2022.12.18 完成)
AT_agc008_a - Simple Calculator
AT_agc008_b - Contiguous Repainting
AT_agc008_c - Tetromino Tiling
T S Z 的积木没有用。O 的单独考虑。I J L 的枚举一下是否各取一个拼起来，剩下的同种类型两两匹配。AT_agc008_d - K-th K
[**]AT_agc008_e - Next or Nextnext
[**]AT_agc008_f - Black Radius
启发
AtCoder Grand Contest 009 (2022.12.21 完成)
AT_agc009_a - Multiple Array
long long。AT_agc009_b - Tournament
AT_agc009_c - Division into Two
AT_agc009_d - Uninity
[**]AT_agc009_e - Eternal Average
AtCoder Grand Contest 010 (2022.12.22 完成)
AT_agc010_a - Addition
AT_agc010_b - Boxes
AT_agc010_c - Cleaning
[**]AT_agc010_d - Decrementing
[**]AT_agc010_e - Rearranging
[*]AT_agc010_f - Tree Game
启发
AtCoder Grand Contest 011 (2022.12.24 完成)
AT_agc011_a - Airport Bus
AT_agc011_b - Colorful Creatures
[**]AT_agc011_c - Squared Graph
[*]AT_agc011_d - Half Reflector
ABABAB 的样子并开始循环，因此令 $k \leftarrow \min(k,2n)$。那么用一个队列维护模拟上述操作，取反操作直接打标记。AT_agc011_e - Increasing Numbers
[**]AT_agc011_f - Train Service Planning
AtCoder Grand Contest 012 (2022.12.25 完成)
AT_agc012_a - AtCoder Group Contest
AT_agc012_b - Splatter Painting
AT_agc012_c - Tautonym Puzzle
[**]AT_agc012_d - Colorful Balls
[*]AT_agc012_e - Camel and Oases
Possible 的。[**]AT_agc012_f - Prefix Median
AtCoder Grand contest 013 (2022.12.31 完成)
AT_agc013_a - Sorted Arrays
AT_agc013_b - Hamiltonish Path
[**]AT_agc013_c - Ants on a Circle
AT_agc013_d - Piling Up
AT_agc013_e - Placing Squares
[**]AT_agc013_f - Two Faced Cards
priority_queue 简单维护一下这个贪心过程，现在所有的 $s_i \ge -1$。priority_queue 即可。AtCoder Grand Contest 014 (2023.1.1 完成)
AT_agc014_a - Cookie Exchanges
AT_agc014_b - Unplanned Queries
AT_agc014_c - Closed Rooms
[**]AT_agc014_d - Black and White Tree
[**]AT_agc014_e - Blue and Red Tree
multiset 维护每个点相邻的点，并使用 map 统计每条边出现的次数。每次找到点对 $(u,v)$ 后，对 $u$ 和 $v$ 的 multiset 进行启发式合并。复杂度是优秀的 $O(n \log^2 n)$，且代码难度薄纱树剖之类的东西。[**]AT_agc014_f - Strange Sorting
AtCoder Grand Contest 015 (2023.1.2 完成)
AT_agc015_a - A+…+B Problem
AT_agc015_b - Evilator
AT_agc015_c - Nuske vs Phantom Thnook
[*]AT_agc015_d - A or…or B Problem
[**]AT_agc015_e - Mr. Aoki Incubator
[**]AT_agc015_f - Kenus the Ancient Greek
AtCoder Grand Contest 016 (2023.1.11 完成)
AT_agc016_a - Shrinking
AT_agc016_b - Colorful Hats
AT_agc016_c - +/- Rectangle
AT_agc016_d - XOR Replace
AT_agc016_e Poor Turkeys
[*]AT_agc016_f - Games on DAG
AtCoder Grand Contest 017 (2023.1.15 完成)
AT_agc017_a - Biscuits
AT_agc017_b - Moderate Differences
[**]AT_agc017_c - Snuke and Spells
AT_agc017_d - Game on Tree
AT_agc017_e - Jigsaw
[**]AT_agc017_f - Zigzag
AtCoder Grand Contest 018 (2023.1.20 完成)
AT_agc018_a - Getting Difference
AT_agc018_b - Sports Festival
AT_agc018_c - Coins
[**]AT_agc018_d - Tree and Hamilton Path
[**]AT_agc018_e - Sightseeing Plan
[**]AT_agc018_f - Two Trees
AtCoder Grand Contest 019 (2023.1.20 完成)
AT_agc019_a - Ice Tea Store
AT_agc019_b - Reverse and Compare
AT_agc019_c - Fountain Walk
AT_agc019_d - Shift and Flip
[*]AT_agc019_e - Shuffle and Swap
[**]AT_agc019_f - Yes or No
AtCoder Grand Contest 020 (2023.1.21 完成)
AT_agc020_a - Move and Win
AT_agc020_b - Ice Rink Game
AT_agc020_c - Median Sum
[**]AT_agc020_d - Min Max Repetition
[**]AT_agc020_e - Encoding Subsets
[**]AT_agc020_f - Arcs on a Circle
AtCoder Grand Contest 021 (2023.1.22 完成)
AT_agc021_a - Digit Sum 2
AT_agc021_b - Holes
AT_agc021_c - Tiling
AT_agc021_d - Reversed LCS
[**]AT_agc021_e - Ball Eat Chameleons
[**]AT_agc021_f - Trinity
AtCoder Grand Contest 022 (2023.1.22 完成)
AT_agc022_a - Diverse Word
AT_agc022_b - GCD Sequence
[**]AT_agc022_c - Remainder Game
[**]AT_agc022_d - Shopping
[**]AT_agc022_e - Median Replace
[**]AT_agc022_f - Checkers
AtCoder Grand Contest 023 (2023.1.23 完成)
AT_agc023_a - Zero-Sum Ranges
AT_agc023_b - Find Symmetries
AT_agc023_c - Painting Machines
[*]AT_agc023_d - Go Home
[**]AT_agc023_e - Inversions
AT_agc023_f - 01 on Tree
AtCoder Grand Contest 024 (2023.1.23 完成)
AT_agc024_a - Fairness
AT_agc024_b - Backfront
AT_agc024_c - Sequence Glowing Easy
AT_agc024_d - Isomorphism Freak
[**]AT_agc024_e - Sequence Glowing Hard
[**]AT_agc024_f - Simple Subsequence Problem
AtCoder Grand Contest 025 (2023.1.24 完成)
AT_agc025_a - Digits Sum
AT_agc025_b - RGB Coloring
AT_agc025_c - Interval Game
[**]AT_agc025_d - Choosing Points
[**]AT_agc025_e - Walking on a Tree
[**]AT_agc025_f - Addition and Andition
AtCoder Grand Contest 026 (2023.1.24 完成)
AT_agc026_a - Colorful Slimes 2
AT_agc026_b - rng_10s
AT_agc026_c - String Coloring
[*]AT_agc026_d - Histogram Coloring
[**]AT_agc026_e - Synchronized Subsequence
AT_agc026_f - Manju Game
AtCoder Grand Contest 027 (2023.1.29 完成)
AtCoder Grand Contest 028 (2023.2.5 完成)
AtCoder Grand Contest 029 (2023.2.6 完成)
AT_agc029_a - Irreversible operation
AT_agc029_b - Powers of two
AT_agc029_c - Lexicographic constraints
a，否则 $A_{i-1} \ge A_i$，这时必须去掉 $A_i + 1$ 及之后的字符，并且将位置 $A_i$ 的字符 $+1$，同时考虑进位的问题（进位可以暴力做，复杂度显然是均摊的线性）。a 的位置，上述操作都能够很好地完成。总时间复杂度 $O(n\log n)$。AT_agc029_d - Grid game
[**]AT_agc029_e - Wandering TKHS
[**]AT_agc029_f - Construction of a tree
AtCoder Grand Contest 030 (2023.2.12 完成)
[*]AT_agc030_d - Inversion Sum
[*]AT_agc030_f - Permutation and Minimum
AtCoder Grand Contest 031 (2023.4.20 完成)
[**]AT_agc031_d - A Sequence of Permutations
[*]AT_agc031_e - Snuke the Phantom Thief
long long，差评。[**]AT_agc031_f - Walk on Graph
性质一
性质二
性质三
实现
AtCoder Grand Contest 032 (2023.4.25 完成)
AT_agc032_c - Three Circuits