写在前面的话
我从今年 \(7\) 月末开始断断续续地写 ARC 的题目，\(9\) 月中旬的时候已经做了少量的题了，还有许多 F 没写，一方面是因为我水平太差看不懂题解，另一方面是因为一种题写多了总是有一种无聊的感觉的。所以到此为止吧，把这些日子水的题放在这篇博客中吧，以后再写 ARC 的题大概会放在对应的专题里，这篇三万字的随笔就用以纪念这段奇怪时光吧。
ARC125
A
贺的想不到吧。
B
转成平方差的形式，然后对于每个较小数统计较大数的取值个数即可，是根号的，可以通过。
C
AT 特有的细节题。不想说。
D
思考什么样的子序列是不合法的，显然如果两个数对应到原序列中中间存在多个中间的那个数那么一定是不合法的，因为这样必然存在两个不同的子序列是本质相同的。于是猜想令 \(f_x\) 为特定数结尾的子序列方案数，那么它的条件应该是上一个数不应该比上一次出现的位置更靠前，这是显然的。对于其它数也有这样的限制，画画图发现似乎是充要的，于是用树状数组维护单点修改区间查询即可，复杂度线性对数。
E
感觉还是挺巧妙的。首先它是一个网络流的形式，最大流转最小割，思考怎么求。图有重要的性质，由于中间的边是无差别的，也就是说左边的决策和右边的决策实际上可以分开来看，枚举割掉的糖果数量，假设留下来的糖果数量是 \(t\)，那么每个人存在两种决策，一种是割掉自己的边，一种是割掉所有的 \(t\) 条中间边，两边显然都是可以贪心维护的。然后前面两种决策只会有至多一个转换点，找出来就可以线性去做了。
F
抛开树的表象发现问题就是一个背包存在性问题，打表或者分析发现对于一个容量 \(x\)，存在一个最小的物品 \(\text{mn}\) 和一个最大的物品 \(\text{mx}\)，其中的所有值都是可以取到的。而根据经典结论不同的物品只会有 \(\sqrt{n}\) 个，所以分批做一个多重背包或者二进制拆分一下都可以通过。
ARC126
A
可能的决策很少，然后感性上理解最优方案应该是可以贪心出来的，所以枚举优先级的顺序并贪心取最大值即可。
B
最长上升子序列板子。
C
大概把最后的答案分成两类，以 \(\text{mx}\) 为界，如果答案大于这个值最优惠的方法就是把所有元素补到期望的答案，这是容易计算的。如果比它小则说明答案的取值范围比较小，考虑直接枚举最后的答案是什么，问题变成了补全的代价，维护前缀和即可在调和级数的复杂度内暴力解决。
D
主要是要学会拆贡献。如果钦定了一些数要算代价，发现由于是冒泡排序的形式所以答案应该是逆序对的个数。但是如今有了一些杂质在中间，那么杂质应该是会被跨越的，产生的代价就是两边比较少的那边的钦定的点的数量。于是就可以 \(f_{i,x}\) 表示前 \(i\) 个数钦定了集合 \(x\) 的位置的最小代价，转移就是考虑当前数选或者不选就可以了。
E
你需要学会搞结论。大概就是认为一个状态有一个势能 \(H\)，其值为排序后的 \(\sum\limits_{i<j}a_j-a_i\)，分析发现无论如何一次价值为 \(x\) 的操作都会造成至少 \(2x\) 的损失，而如果每次只操作相邻的两个数的话就只会恰好消耗 \(2x\) 的势能，所以答案就是初始势能。权值线段树维护即可。
ARC127
A
跳过。
B
跳过。
C
显然从高位向低位进行选择并动态维护当前剩下的 \(\text{rk}\)，于是问题变成了如何维护那个数。然后你会发现暴力进行二进制加减法复杂度是正确的，然后就没了。
D
\(a_i\oplus a_j\ne b_i\oplus b_j\) 意味着二者必然在某一位是不同的并且更高的位是相同的。枚举这一位是什么，取出更高的那些位得到新的数列 \(a,b\)，满足第二个条件即是 \(a_i\oplus a_j=b_i\oplus b_j\)，也就是 \(a_i\oplus b_i=a_j\oplus b_j\)，现在的问题变成了如何找到那些使得特定位的异或不同的位置，显然等价于找到那些同位异或和不同的那些数，也就是说一对 \(a_i\ne b_i,a_j=b_j\) 的数对 \((i,j)\) 会产生贡献，先按高位异或和分类，然后把所有数分成了三类，枚举前者计算贡献即可。复杂度啊，可能枚举位有个 \(k\)，归类上开个桶不太优雅所以应该是线性对数的，然后每个数计算的时候无论是 insert 还是 query 的复杂度都是 \(k\)，所以整个复杂度是 \(O(nk^2+kn\log n)\)，而且似乎是跑不满的。
E
你就画一下嘛，然后发现似乎最后的集合和具体操作形式并没有太大的关系，所以大可指定一个顺序并计算。一个显然是指定是一串连续的 \(1\) 钦定其单增，然后拓展成什么一定删最后一个还存在着的数，再拓展成集合任意时刻保持单增，到此问题已经是可做的了。然后写一下，交，过了，没了。
ARC128
A
北风掠过像你的容颜。
B
北风掠过像你的容颜。
C
如果没有上界的限制直接找一个后缀摊平是最优的，但是有上界的限制。所以每次去掉选择的后缀之后再选择一遍即可，复杂度是 \(O(n^2)\) 的，可以通过。
D
忘了是哪个米奇妙妙合集里面的题了。
用 \(f_x\) 表示前 \(x\) 个数可以留下的集合数量，考虑转移，发现一个合法的转移点 \((x,y)\) 应该满足这个区间可以删除得只剩下两端的两个元素，考虑其条件。首先应该满足不存在相邻元素，其次应该满足元素数量不小于三，可以发现这是充要的。于是维护两个指针辅以前缀和即可。
E
大贪心题。
思考有解的条件。把原序列分成一些块，显然不应该有多于块的数量的元素，其次令最后一块的大小为 \(t\)，那么正好等于块的数量的元素也不应该多于这个数。发现这些条件是容易判断的，而数据范围又很小，所以可以贪心地一个个填数。当前最小的数如果等于块的数量那肯定是很好的，如果不是要思考把这个位置占了之后下一个状态是否合法，判断一下即可。
ARC129
A
差分一下，然后从高到低考虑答案。
B
北风掠过像你的容颜。
C
北风掠过像你的容颜。
D
需要推一些柿子。
记第 \(i\) 个位置操作次数是 \(p_i\)，那么最后应该满足 \(a_i+2p_i-p_{i-1}-p_{i+1}=0\)，字母太多了，考虑令 \(d_x=p_x-p_{x-1}\)，那么 \(a_x+d_x-d_{x+1}=0,d_{x+1}=d_x+a_x\)。展开一下可以用 \(d_1\) 来表示每一个 \(d\)，这样就达到了将字母化简的目的。具体来说：
\[\sum\limits_{x\in[1,n]}d_x=\sum\limits_{x\in[1,n]}(d_1+\sum\limits_{i\in[1,x-1]}a_i)=nd_1+\sum\limits_{x\in[1,n]}(n-x)a_x \]而显然 \(d\) 的和是零，并且 \(a\) 的和也是零，所以可以得到 \(nd_1=\sum xa_x\)。于是就可以得到 \(d_1\) 啦。
最后考虑还原出一个 \(p\) 序列。显然都是正的，并且都和 \(p_n\) 正相关，故 \(d\) 的前缀和对 \(p_n\) 产生一些限制，取这些限制中最严格的一个即可。
E
应该大概也许是网络流。感觉像是一堆板子拼起来的模型，但每个板子我都不会。
每个点对应了一些值，我们希望选择其中一个（也就是类似于切糕的模型），那么应该从源点连出一条链，每条边对应一个取值，选择一个权值等价于断掉一条边。然后就是这道题中那个绝对值的限制，感觉非常不好做的样子，因为既然选择了一条链那么相当于对于一个前缀或者后缀所需要的代价。于是应该把一个绝对值拆成很多段，每段被贡献当且仅当两个元素的取值分别在左右端点的两边。至此连边是简单的，具体而言以一个点第一次大于左端点的位置为终点，以第二个点第一次大于右端点的位置为起点连边，这样一来如果第二个点断点在右端点后面并且第一个点在左端点前面就会产生一个通路，然后就需要考虑断掉中间的边，于是就可以正确地表达题目中的关系了。
ARC130
A
对每个连续块分别处理即可。
B
非常经典的题目，对于每一行每一列记录最后出现的颜色并计算贡献即可。
C
有点细节。枚举最后两个数，显然加起来超过十是很好的；然后前面的数应该尽量凑九，然后要注意尽量不选九，因为最后长数可以留一串九进位。
D
考虑根节点是大点还是小点，确定之后其他点直接黑白染色（或者说大小染色）。从下到上考虑贡献，用 \(f_{x,y}\) 表示当前子树 \(x\) 中根节点排名为 \(y\) 的方案数，随便优化一下就可以做到 \(O(N^2)\)。
E
题意是说给定一个数列，每次找到最小的数并记录坐标，然后把这个位置上的数加一。给出记录下来的序列，找到字典序最小的合法的序列或者判断无解。
又是一个 AT 特有的观察性质的细节题。我只看懂了大概的思想。发现给出的序列应该被分成一些段，并且段内的当时值是相同的，并且相邻段的差值恰好为一，于是以此为切入点进行构造。实现上需要考虑一段是否是完整的以及是否合法等细节，输出也是需要注意的。脑子比较混乱。
ARC131
A
很简单的构造。
B
五种颜色，还是四相邻。无脑判断即可。
C
对 \(n\) 的奇偶性分类讨论。先说奇数，直觉上来说应该是必赢的，可以证明。
假设当前异或和为 \(s\)，如果数列中存在 \(s\)，那么选择这个数即可获得胜利。其它的情况可以按值把元素分类，然后希望选择一个数使得后手不存在选另一个数的方案让两个数异或和恰为 \(s\)。把集合们按 \(s\) 互补两两配对，如果有落单的盲选这个即可。剩下的就是两两配对的情况了，然而似乎并不存在这种情况。然后然后分类讨论云云。最后发现尼玛数列互不相同那不是很傻逼。
于是奇数可以误伤转移到下一轮，显然是必胜的；偶数要么一击致命，要么把奇数留给后手，让后手必胜自己寄掉。然后就没了。
D
显然应该尽量靠近，考虑一定有一个点在 \([0,D]\) 的范围内，并且其余的点在两边均匀分布，证明上调整一下就出来了。于是枚举中心点的位置并动态计算答案取最大值即可。
E
考虑满足不存在斑斓三角形的方法，大概方法就是考虑一个点的入边颜色全部相同，这样一定能保证两条边颜色相同。问题转化成给定连续数分三组，组内和相同的方案数。答案是显然的。
ARC132
A
简单讨论大小关系即可。
B
简单分类讨论。
C
简单的状压DP，记录周围十个数的使用情况正常转移即可。
D
考虑 \(n\) 个 \(1\) 会形成 \(2n\) 个无用空挡，于是思考如何最大化有用的，即相邻相同和与边界相邻的情况数。题目限制相当于给定了一些区间，并且这些区间具有可以高效转移的性质。考虑用 \(f_x\) 代表前 \(x\) 个 \(1\) 最多能产生多少有用的空隙，然后思考当前 \(1\) 和哪些 \(1\) 连续，显然存在一个分界点，二分出来取后缀最大即可。注意边界，复杂度为 \(O(n\log n)\)。
E
感觉被诈骗了。遇到这种问题应该先考虑最终形态是否有什么特殊性质，发现就这道题而言是有的。会发现最终的 形态应该是中间存在一个空隙，两边有连续的一直绵延到边界的脚印。于是想到每个空隙称为幸运儿的概率。发现成为幸运儿当且仅当两边都不经过这个空隙，令 \(n\) 个方块并且不会碰到特定边界的概率为 \(f_x\)，发现这玩意似乎可以递推。考虑当前块在排列中的位置，令为倒数第 \(y\) 个，那么前面的可以忽略，后面的就转化成了一个规模为 \(y\) 的子问题。于是有 \(f_{x}=\sum\limits_{i=0}^{x-1}f_{i}\dfrac{1}{2x}\)，维护一下前缀和就能常数转移了。然后计算贡献即可，复杂度 \(O(n)\)。
ARC133
A
扣掉一个数当且仅当这个数后面有更小的数。特判单增即可。
B
相对比较有启发性。发现有倍数关系的数对只有 \(O(n\log n)\) 对，于是可以把对应下标攒成一堆二元组，于是一个合法的取数方案就变成了两个维度分别严格上升的元素集合。按其中一维排序，给第二维做最长上升子序列即可。为了第一维严格，第一维相同的元素按第二维降序排列即可。
C
正难则反。考虑每个数被扣除的和的最小值，可以发现有方案使得和是行和列的较大值（前提是要合法，即余数相同），随便构造即可。于是就没有了。
D
前缀异或和差分一下，问题变成了一个区间内异或和特定的数对数量。整理可以得到后面两位的值，而前面的值等于本身或者等于零，于是枚举最后两位前面搞数位 DP 即可。写起来没什么。
E
妈的感觉被诈骗了。
考虑最后答案 \(\ge k\) 的方案数，发现最后的值只和最有一个相同的夹层的颜色有关，如果没有相同的夹层，那么将会保持初始值不变。于是有些人开始了对夹层期望的探寻，许久之后被告知这玩意是对称的，蛤蟆麻了。就和之前的某个题一样，\(k=x,k=n+1-x\) 两个阶段下黑色和白色的数目是相同的，因为概率是相反的。所以只需要把不存在夹层的方案找出来，剩下的情况除以二贡献即可。
ARC134
A
顺序结构题。
B
简单题。
C
把重要角色和次要角色一一绑定，然后暴力计算组合数即可。
D
首先应该保证前半部分字典序最小，所以第一个数应该贪心地选最小的。此时如果发现对应的数有比最小的数还小的（或者相等），那么选择保留这一对显然是最优的。如果没有，那么应该选择前面所有的最小数对应该不劣，最后考虑前半部分后面一丢丢的数对就可以了，即什么时候选进来可以让答案更优。发现后面那个数无关紧要，选择前面的数即可，分类讨论一下和后面第一个选择的数的大小关系即可。
E
很具象的一道题。
有一些显然的确定态，比如如果存在奇数（并且并不是全都是 \(1\)）那么先手选择模 \(2\) 即可让后手去世。接下来就是全都是偶数的情况了，似乎并不是很好分析的样子，于是考虑对 \(4\) 取模再进行讨论。如果存在余数为 \(2\) 的，那么模 \(4\) 即可让对手去世。于是问题就变成了如果全都是 \(4\) 的倍数的情况，然后再对 \(12\) 取模。如果有余数为 \(4\) 或者 \(8\) 的，那么可以对 \(12\) 取模，最后剩下一堆 \(4\) 和 \(8\)。分讨一波：全都是一个数，那么显然有必胜的策略（模 \(3\) 即可），即先手必败；混杂的情况如果对方模 \(3，5，7\)，存在奇数先手必胜；如果对方模 \(6\)，那么只剩 \(2,4\)，先手必胜，其它情况显然。最后只剩全都是 \(12\) 倍数的情况了。由于 \(a_i\le 200\)，可能的数的数量不是很大，直接状压即可。方案统计是简单的。
ARC135
A
尽量分割成 \(2,3\) 时最优，于是暴力记忆化搜索即可，感官上状态数很少，可以通过。
B
随便做。
C
发现任意操作都相当于是整个数列异或上一个数，于是枚举每个数考虑对每一位的影响暴力计算答案取最大值即可。
D
首先需要做一个转化。把原来的表格黑白染色，并把黑色的格子取反。这样做有两个好处：一个是新表格的答案和原表格的答案是一样的，因为一个数取反之后绝对值不变；另一个是说这样一来每次操作中每一行每一列都恰好涉及一个白格子和一个黑格子，也就是说这一排的数的和是不变的。
于是答案就很显然了，即每行绝对值之和和每列绝对值之和的较大值。当然可以尝试着去大概证明一下。
首先有一个结论是任意满足行和列和和原表格相同的数都可以由原表格通过一系列操作得到，大概就是可以从一个角落向其它角落操作，最后只有一行一列没被确定，由于和是相同的，所以最后的那一行一列和原表应该也是相同的，这是必要性。
充分性可以通过构造过程来证明，此时问题就变成了希望找到一个表使得其行列和合法并且元素绝对值之和等于我们的答案。思考一下什么时候前者满足而后者不满足，肯定是存在一行中存在两个数一正一负，加起来抵消了，绝对值就产生了浪费。避免这种浪费的方法就是让元素和所在行列和的符号保持一致，于是每次暴力找到一对行和列符号相同就能避免这种浪费。如果找不到了，那么说明有一方已经全零了，剩下的就填充相反数即可，容易发现这样构造出来的表格元素绝对值之和就是前文的答案。
E
多头说得好，这玩意一看就具有阶段性，看不出来打表也能打出来。
量化分析一下。显然贪心地来做，即 \(a_{i}=(\lfloor\dfrac{a_{i-1}}{i}\rfloor+1)i\)，记 \(b_i=\dfrac{a_i}{i}\)，那么可以得到 \(b_i=\lfloor\dfrac{b_{i-1}(i-1)}{i}\rfloor+1=i-\lfloor\dfrac{b_{i-1}}{i}\rfloor+1\)，于是发现将 \(b\) 差分之后的值只和 \(\dfrac{b_{i-1}}{i}\) 有关。
首先给一个比较松的上界。由于每走 \(k\) 个数必定遇到倍数，所以 \(a_i<x+i^2\)，故而有 \(b_i<\dfrac{x}{i}+i\)。考虑分治，令 \(B=x^{\frac{1}{3}}\)，那么前 \(B\) 个点的段数显然是 \(O(B)\)，而 \(B\) 处 \(b\) 的取值都已经是 \(x^{\frac{2}{3}}\) 级别的了，差分值是在 \(x^{\frac{1}{3}}\) 级别的，后面的值只会减不会增，所以段数也是 \(O(B)\) 级别的。所以二分每个段的端点计算贡献复杂度是对的。
二分条件，考虑 \(b\) 的差分数组变化的条件。假设当前计算出来的公差是 \(d\)，合法的右边界 \(r\) 应该满足 \(\dfrac{b_{r-1}}{r}=\dfrac{b_l-x(r-l)}{r}=\dfrac{b_l}{l+1}\)。即没有下降的空间即可。然后通过楼上的分析可以得到更加简洁的柿子从而去掉一只 \(\log\)，在这里就不写了。
然后来考虑贡献问题。假设当前左右边界为 \(l,r\)，\(b\) 是一个首项为 \(c\)，公差为 \(d\) 的等差数列，令 \(f(l,r)\) 为等差数列求和，\(g(l,r)\) 是一个区间的平方和，那么贡献应该是：
\[\sum\limits_{i=l}^r(c-ld+id)i=(c-ld)f(l,r)+dg(l,r) \]计算即可。另外发现 998244353 能被 \(6\) 整除。比较强。
ARC136
A
贪心。可以把 BB 换成 A，可以把 BA 换成 AB。
B
直观上觉得只要数集相同，那么就是可以变换的。大概方法就是每次找到正确的数把它挪到数列的端点，这样显然是可行的。但是在相反的三个上出现了问题，原因在于只剩最后两个数时方向可能是反着的。分析发现每次移动改变两对数的相对位置，那么逆序对奇偶性应该不变，判断一下即可。如果存在相同的数发现是不用判断奇偶性的，一定存在合法的方案。
C
显然差分，环上问题就在环上差分，得到一个数列。感官上和正负有关，而正负值之和为零，而每次操作都能让一个地方加一另一个地方减一，猜想答案是差分数组中正数的和。操作中需要保证数不小于零，每次挑极长正数即可，有效消耗了差分数组。然后解决掉剩下的部分就可以了，表现出来就是正数的和与数列中最大值取 max 输出即可。具体操作方法是考虑两个量（差分值和最大值）的消耗情况。如果后者大，那么发现不存在为 \(0\) 的元素，全局减就能消耗一个后面值；如果前面大，那么找到一个最大值连续段就能消耗前者；如果一样大，说明至少没有浪费的，刨掉山谷就能得到一个双赢的方案。于是就正确了。
D
高维前缀和。写起来非常不优雅。
E
思考两个数什么时候会建立联系。首先两个偶数本身就有边，然后考虑奇数和偶数。令 \(x\) 为最小的奇数的质因子，那么奇数要到达最近的偶数必须要加上或者减去这个数。奇数和奇数也是一样的，发现通过奇因子不如偶因子实在，所以条件仍然如前面所说的。于是乎每个奇数就有了一个区间，一个数不想被ban就只能让自己的区间和这个区间有交，把每个数的区间找出来差分找最大值即可，可以做到线性。
ARC137
A
直觉上答案会出现在区间的边际上，暴力枚举一些即可。证明不会。
B
找最大子段和与最小子段和即可，线性。
C
需要用到一个技巧，即决策包容性。是说如果一个状态可以到达一个子状态（一个就够了）的所有子状态，那么这个状态就是必胜态。证明上考虑对这个子状态分类讨论，如果是必输那么状态必赢，如果必赢那么存在子状态必输，那么状态仍然是必赢的。考虑这个问题，如果最大值和次大值没有靠拢，那么最大值减一就是那个子状态，显然这个状态的所有子状态都可以由原状态转移过来，所以就是必胜的。至于相邻的情况，由于先手不能让后手有机会，只能让后面的数连续，决策是唯一的，求一下决策数判奇偶即可。
D
学到了两个技巧。首先就是对数列 \(a\) 做 \(k\) 次题目所述的前缀和，那么应该有：
\[a^k_n=\sum\limits_{i=0}^{n-1}\binom{i+k-1}{k-1}a^1_{n-i} \]具体含义就是考虑贡献的路径计数，总共需要跳 \(k\) 步，于是就有上面那个式子。也就是说如果上面那个组合数是奇数那么对答案就有贡献，否则没有。此时需要另一个技巧，即用卢卡斯来拆分组合数。
\[\binom{i+k-1}{i}\%2=\prod\limits_t\binom{(i+k-1)_t}{i_t}\%2 \]要得到 \(1\) 必须满足不出现 \(\binom{0}{1}\)。也就是说 \(i+k-1\) 应该包含 \(i\)。如果前者存在进位，那么肯定会破坏某个位置上的 \(1\)，所以 \(k-1\subseteq\complement_ui\)。做一次高维后缀和即可。
E
好东西。有两种思考方式。
一种是考虑让面包进行流转。首先假如我们已经获得了 \(114514\) 块面包，但事实上我们并没有这些面包，于是我们就需要付出一些代价。代价分为三种，一种是取消掉免费面包的订单，一种是取消付费面包的订单，一种是花费一些代价雇佣面包师来做这些面包，希望最小化三者的和。表现在模型上就是连 \((i-1,i,0)\)，\((i-1,i,d_i)\)，\((l_i-1,r_i,c_i)\)，限定一下流量（本来就只借了这么点面包啊）跑最小费用最大流即可。
另一种是正着考虑。想着往最小费用循环流上靠拢。考虑连 $(i,i+1,0/-d_i) $ 表示得到的钱的相反数，然后连 \((r_i+1,l_i,c_i)\) 表示雇佣的钱的相反数，求最小费用循环流。而最小费用循环流的方法大概就是将每一条负边变成三条边，一条反边和两条连向源汇点的边，删删减减和上面的模型是相同的。然而感觉并没有上面那种方法直观。
ARC138
A
交换两个数最少的操作次数应该是距离，所以枚举每个前面的数找最近的更小的数即可。
B
模拟。
C
猜想可以取到最大的一半数。令最大的一半数是 \(1\)，小的是 \(-1\)，画出折线图，从最高点开始新建起点一定能保证没有冒头的点，即符合题意。
D
考虑差分，那么差分出来的数应该是一堆满足 \(\text{cnt=k}\) 的数，而这些数应该是要构成所有的这些数的。那么考虑把它们都丢进线性基，如果能丢满说明有解，构造上线性基中得到了 \(k\) 个上述的基底，参照格雷码把这些基底组合起来即可。
E
感觉很巧妙的题目。
首先将数列转化成图的形式，具体而言是对于所有 \(a_i>0\) 的点连边 \((i,a_i-1)\)。观察这张图，发现每个点都有至多一个出度和一个入度，并且一定是从后往前连边，也就是说每张图应该都是一个链的集合。进一步观察发现这些链的划分和原数列是双射关系，而由于链的连边是有顺序的，所以链的划分等价于把原集合划分成一些不相交的集合，这对后面的计数有帮助。
观察合法序列对应的图，发现选出来的数对应了 \(2k\) 个点，记为 \(p_1,p_2\dots p_{2k}\)，发现它们要求回文地连边，并且边和边之间是包含的关系。考虑以最中心的那条边为基准把这 \(k\) 条链上的点划分成前后两个部分，两个部分都是 \(k\) 条链，将链尾和链首拼起来就是一组合法的方案（我们要求的那 \(k\) 条边就是那 \(k\) 对链首和链尾的连边）。
于是就有了柿子：
\[\text{ans}=\sum\limits_{i,j}\binom{n+1}{i+j} \begin{Bmatrix}i\\k\end{Bmatrix} \begin{Bmatrix}j\\k\end{Bmatrix} \sum\limits_{t} \begin{Bmatrix}n+1-i-j\\t\end{Bmatrix} \]我声称有了上面的解释这个柿子会非常容易理解，有一个点是说由于建出来的图包含 \(0\) 号点，所以柿子中是 \(n+1\)。后面那堆显然是可以优化的，复杂度 \(O(n^2)\)。
F
很有启发意义。这场是真的喜欢计数，建议明年主持 NOI 命题工作。
直接计数显然会重复，于是考虑如何去重。正如第一篇题解说的那样，对于这类问题一般有两种思路，一种是思考哪些状态可达（即几乎抛开操作过程来考虑问题），另一种思路是说考虑给操作序列进行一个排序，每次从最小的那个转移过来。本题用到了第二种思路。
顺序上，我们认为横着切比竖着切更小（小是指操作之间钦定的顺序），方向相同时越靠左、越靠下切越小，那么考虑正常转移。枚举一个操作，然后思考减去这个操作并不是最小的情况，也就是说存在一个更小的操作能达到相同的目的。那么应该有两种可能，一种是说同向但数值更小，一种是说异向但能达到相似的效果，具体画个图就可以分析出来了。然后就没什么了，复杂度是 \(O(n^6)\)，但常数是肉眼可见的小。
ARC139
A
憨的。
B
感觉没有那么naive。
首先用 \(1\) 去更新一下后面两个决策的价值。然后有一个较为显然的东西是说 \(\text{lcm}\) 为周期，周期内应该贪心取最大的。周期外由于范围很小，可以直接枚举一种决策的次数，取最小值即可。复杂度是正确的。
C
考虑无脑构造。令 \(a=3x+y,b=3y+x\)，然后发现一个数对合法当且仅当其中一个数是合法的，即 \(8|3a-b\)，即 \(3a\equiv b(\text{mod}8)\)。而每个 \(a\) 对应的合法 \(b\) 除了需要满足上面的条件以外还要满足存在对应的合法 \(x,y\)。计算就可以得到一个范围，并且该范围随着 \(a\) 移动单向移动，所以贪心去取一定最优。开 \(8\) 个 \(\text{set}\) 即可。
D
经典地考虑最后答案 \(\ge k\) 的方案数。用 \(f_{x,y}\) 表示第 \(x\) 轮有 \(y\) 个数不小于 \(k\) 的方案数，考虑转移，发现需要分类讨论，并且呈现出一个向中心靠拢的趋势。于是枚举非中心的点，方案数就是路径统计，中心的方案整体减空白即可。
ARC140
A
考虑尽量缩短循环节长度，枚举即可。
B
顺序结构。
C
大概策略是上下横跳，这样能构造出来一个比较优的数列。有一些细节。
D
很不错的一道题啊。
把问题转化成最后会剩下多少个环，毕竟每个连通块都应该恰好包括一个环。发现有一些环是固定的，有一些是游走的，后者由树提供。然而直接计算不是很好计算的样子，考虑拆开来，计算每种长度下环的出现次数。用 \(f_{x,y}\) 表示前 \(x\) 棵树凑出来一个大小为 \(y\) 的环的方案，转移比较容易，即 \(f_{x,y}=f_{x-1,y-1}\times(y-1)\times\text{size}+f_{x-1,y}\)，优秀的点在于要知道当前这棵树插在哪就需要知道环的大小，于是就有了这个状态设计。最后计算贡献加起来即可，后面就没什么说的了。
E
限制上感觉很根号。于是分成一些块，然后考虑块和块之间的关系。先考虑 \(1\)，发现内部构造并无关系，所以以主对角线填上为基准块，其它的对基准块进行位移。令第块 \((x,y)\) 的位移量是 \(f(x,y)\)，那么我们希望的实际上是 \(f(a,l)-f(a,r)\ne f(b,l)-f(b,r)\)，即希望不同行相同的差距能产生不同的位移。想到令 \(f(x,y)=xy\)，验证之后发现合法。其他数字相似地位移即可。
ARC141
A
数据范围很小，可以进行一个大的枚举分讨。
B
简单 DP。
C
搬当时写的题解。
首先对原括号序列画折线图，具体方法就是如果是左括号就往上走，否则就往下走。试想，如果整根线一直都在水平线上方，那么一定存在一个序列 \(1\dots 2n\) 是合法的，也就是说此时数组 \(p\) 也一定等于这个值。
然而事实不总是这样的，这是因为折线图还有低于水平线的部分，对于这部分容易想到在此之中左右括号数量相等（这样才能刚好升到水平线上），所以策略是找第一个左括号然后找第一个右括号，交替进行直到把折线又拉回到水平线上为止。
所以我们得到了一个非常重要的结论，如果 \(p_{2i}<p_{2i-1}\) 的话，那么 \(p_{2i}\) 对应的位置应该是左括号，\(p_{2i-1}\) 对应的位置应该是右括号。同理，会发现数组 \(q\) 决定的是水平线以上的部分，两个部分合并起来应该就是完整的数组，所以如果看到重合或者未覆盖的地方就说明不存在合法解。最后求出答案之后验证一次就可以了。复杂度可以做到线性。
D
\(n\) 个选出来的数对应着 \(n\) 个奇因子，而奇因子需要不同的 \(n\) 个而总共又只有 \(n\) 个，所以大概的框架就搭建起来了。记某个奇因子配凑了 \(p_x\) 个 \(2\)，那么对于 \(a|b\)，应该满足 \(p_a>p_b\)，于是就可以建图啦。大概可以正着反着各跑一次拓扑求出每个 \(p\) 的范围，然后对于每个数思考其奇因子是否在计算得到的范围之内就可以了。
E
感觉所有的带权并查集题目我都比较难以理解。
大概思路是说斜着的转化成行，然后用带权并查集维护行和行的连通块，合并的时候用裴蜀定理可以得到和 \(\gcd\) 的关系，更新答案即可。其实并没有完全看懂呜呜呜。
ARC142
A
憨的。
B
构造。考虑一行之内大小交错，行间则单调排列。这样可以使得每个点上下大小关系抵消，左右的又保持一样，于是就合法了。
C
处在 \(1,2\) 最短路径上的点一定到两个点距离和最小，于是找到这个距离。但是这个距离可能是 \(3\) 或者 \(1\)，对这样的情况进行一点分类讨论即可。
D
应该把整棵树划分成一些链，每条链带了一条白色的尾巴，这样显然可以构造方案。至于如何构造唯一方案，思考这些毛毛虫需要满足哪些条件。首先头和头不能相邻，尾巴和尾巴不能相邻。还有一个就算不能有一条虫的脑袋顶别人的身体，这样会产生歧义。相似地尾巴和身体也不能直接接触。最后就可以大力 \(f_{x,0/1/2/3/4/5/6/7}\) 来暴力转移了，分别表示是单脑袋，是有身体的脑袋，是单尾巴，是有身体的尾巴，是有前驱后继的身体，是有前驱的身体，是有后继的身体，是一截什么都没有的身体。应该是这样吧。
E
很好的一道题。大前提是每个数应该被补到一个较高的水平，该水平有两个标准。一个是不应该比原来的 \(a_i\) 低，因为补到 \(a_i\) 不劣；一个是不应该比每个关系中 \(b\) 的较小值低，因为这样就不合法了。
此时需要观察仍然不合法的数对性质。发现形式大概如此：存在 \(a_i\ge b_i,a_j<b_j\)，也就是说每个数都被划分成了两类，一类是小于的，一类是大于的，并且一个限制中恰好包含了两类数各一个。于是考虑把两类数放在两边，思考每一个限制如何满足。
从小的向大的连边，那么只需要小的满足或者大的满足即可，并且小的满足是一劳永逸的。于是每个点建立一个点，从源点向这个点连代价边，然后这个点向限制的大点连边，要求其不小于给定的数。后面需要用到一个比较经典的模型，即 \(i\) 向 \(i-1\) 连 \(\infin\) 边，\(i\) 向汇点连 \(1\) 边，这样要断只能断后缀，达到了选择一个数的目的。跑最小割即可。
ARC143
A
选择结构。
B
猜想最多只有一个数满足条件，分析一下发现应该正确的。然后简单统计即可。
C
考虑像经典 nim 游戏一样，思考后手什么时候可以跟随先手进行操作，发现这一轮操作等价于将每个数模上一个 \(a+b\)。总会有一个余数集合，思考一些比较简单的情况，即每个数都小于 \(x\)，那么后手无脑跟进是正确的。否则如果存在数大于 \(x\)，那么再次分类讨论。如果 \(x\le y\)，那么先手先把所有大余数 ban 掉之后就变成了一个后手必败的场面。最后就剩一个 \(x>y\) 的情况了，如果不存在二者之间的数那么先手必胜，因为不存在一个数减去 \(y\) 之后还比 \(x\) 大；如果存在的话那么后手必胜，容易分析得到。
D
题目中的操作很像拆点，而连边就相当于是给无向边定向。于是考虑从拆点之前的意义思考，问题变成了给定一个无向图，希望给图中每一条边定向，使得旧图中桥最少。画图发现高一棵 dfs 树出来从上到下连边是不错的。
E
一看就是从叶子开始考虑，然后逐层向上，搞出一个 DAG 后贪心搞字典序最小的操作序列即可。
ARC144
A
憨憨题。
B
二分加检查。显然是容易的。
C
手玩发现，如果前面可以划分成一堆长度为 \(2n\) 的段那么一定划分，这样一定字典序最小。后面会有一段小于 \(4n\) 的数，考虑让其递增循环着来即可。然而 wa 了，观察题解区发现是答案 \((10,3)\) 应该是 4 5 6 1 8 9 10 2 3 7 而非 4 5 6 7 8 9 10 1 2 3。发现如果最后的长度大于 \(3n\) 的时候需要在中间进行一些循环位移，找规律就可以了，然后就没了。
D
猜想合法的形式应该是存在一个大小为 \(n\) 的数列 \(p\)，满足 \(a_S=p_0+\sum\limits_{i\in S}p_i\)。然而 \(p\) 有正有负，把其按照正负性分类，而题目中的限制就变成了负的那些（可以认为是最负的那个集合）不小于零，最大的那个也不应该大于 \(k\)。然而方案似乎并没有那么好计算。
考虑切换枚举对象。思考每个 \(p\) 对应的 \(p_0\) 的取值范围，发现其就等于 \(lim-\sum|p_i|\)，而每个 \(p_i\ne 0\) 都有两个取值。于是显然想到枚举非零的个数 \(n\)，可以得到下面的柿子：
\[\text{ans}=\sum\limits_{0\le n\le m}\binom{m}{n}2^n\sum\limits_{s=n}^{k}(k-s+1)\binom{s-1}{n-1} \]右边是个上指标求和的形式。具体地：
\[\begin{aligned} &\sum\limits_{s=n}^{k}(k+1)\binom{s-1}{n-1}-\sum\limits_{s=n}^k\binom{s-1}{n-1}s\\ =&(k+1)\binom{k}{n}-\sum\limits_{s=n}^kn\binom{s}{n}\\ =&(k+1)\dfrac{n+1}{k+1}\binom{k}{n}-n\binom{k+1}{n+1}\\ =&\binom{k+1}{n+1} \end{aligned} \]然后就没啦。组合数可以递推，所以总体复杂度是线性的。
E
哈哈哈。
首先从图中剔除那些从源点无法到达的点和无法到达汇点的点，然后拆点，忽略那些 \(-1\) 的点，最后图会形成一些连通块，一个 \(x\) 合法当且仅当对于所有连通块都是合法的。搞一个生成树出来，考虑每条非树边对答案的限制，等价于限制了答案是 \(|v-\text{dis}_{x,y}|\) 的因数，前缀和维护即可。还要注意一下什么如果存在从 \(1\) 直接到 \(n\) 的边那么需要让答案和路径的长度取一个 \(\gcd\)，其它的就没什么了。主要数组要开够。
ARC145
A
进行一些特判就好了。
B
如果先手比较小，那么只要足够取第一次就是胜利的。
如果先手比较大，那么看余数，如果余数比后手小那么他也赢了，否则由于后手面对的是一个必胜局面先手肯定会输。方案计算是简单的。
C
显然顺次匹配最优。考虑方案数，首先削减一些条件变成合法的匹配数，最后乘上 \(n!\times 2^n\) 即可。手画发现合法的匹配应该满足不存在一个匹配被另一个匹配包含，画出来发现和括号序列形成双射关系，大概就是首先应该是一个合法的括号序列，其次每个括号序列只有一种匹配方法能得到合法的匹配（也就是顺次匹配）。简单计数即可。
D
感觉还是很巧妙的。考虑如何满足题目中的条件，注意到可以用三进制来推，只要满足每个数只存在 \(0\) 或者 \(1\) 就是合法的，因为两个不同的数相加一定存在 \(1\)，而一个数的两倍却只有 \(0\) 和 \(2\)。简单构造就可以出来一个方案，至于和的限制是简单的。
E
被大撅特撅了，感觉一直以来自己都非常傻逼。
首先需要做一个转化，题目中的操作相当于做了一次差分，那么反过来就相当于是做了一次前缀和，于是需要对 b 数组进行一些前缀和操作使之和 a 相同。参考题目中的限制条件，发现大概是 \(n\log V\) 级别的，所以从后向前，每一位分别进行一次操作。猜想合法情况，发现此时 \(a_x\) 无法被消除，所以只需要 \(a_{1\dots x-1}\) 能凑出 \(a_x\oplus b_x\) 即可。想到搞一个线性基，令 \(t_x\) 表示每个数在线性基中出现的情况，那么我们需要让一些数在线性基中出现的次数取反，于是按线性基中每个数出现的位置从大到小处理。假设位置是 \(p\)，那么对 \(p+1\) 操作会使得该基底多出现一次，同时不会影响之前处理过的基底的情况。每次重新计算是否需要操作这个基底即可。
ARC146
A
你大可进行一个举的枚。
B
从高到低枚举每一位，枚举每个数补齐所需的最小代价即可。后者需要分类讨论。
C
被撅了。
你可以发现集合中的元素不会特别多，于是考虑以元素数量为中心进行计数。用 \(f_x\) 表示方案数，那么大小为 \(x\) 的集合中所有大小为奇数的集合异或值应该互不相同。这样的集合数量是 \(2^{x-1}\)，原因在于如果 \(x\) 是奇数，那么一定存在一些集合对一奇一偶，毕竟 \(\binom{x}{t}=\binom{x}{x-t}\)；如果 \(x\) 为偶数，那么分理出某个元素，考虑剩下部分的方案再合并上来，发现仍然有这个结论。
于是就有转移 \(f_{x+1}=f_x(2^n-2^{x-1})\)，然后还需要带上一个 \(\dfrac{1}{x+1}\) 的系数毕竟会重复计数。复杂度可以做到线性。
D
明天七夕，所以我应该给挚爱深爱的 SPFA 一点笔墨。
每个限制等价于说如果 \(a_x\ge p\) 那么可以导出一个 \(a_y\ge q\) 的结论，把这玩意以连边的形式存储下来，考虑增量法，跑一次类似于 SPFA 就可以得到最优的答案。复杂度显然是正确的。感觉比较憨批，也不知道是说这道题还是说我。
E
相对牛逼的一个题。
考虑按值域从小到大进行转移，显然应该以段数为基础设计状态。假设 \(f_x\) 表示当前状态下形成了 \(x\) 段的方案数，显然每一段的两端都应该是当前这个数。考虑下一个数放在哪些地方，发现一种方法是每个空隙放两个数，然后还剩下一些数单独成段即可。但也可能出现一个数把两个段合并的情况，这样一来就会空出来一个数单独成段，发现段数其实没有任何变化，也就是说状态数不会特别多。转移等价于每个空隙填不少于一个球即可，暴力转移即可，复杂度应该是线性的，或许需要带上一个对数。细节其实并不多。
ARC147
A
暴力做复杂度似乎是正确的。
B
北风掠过像你的容颜。可能只是忘了应该怎么做的了。
C
比较妙的贪心题。如果所有区间的交不为空，那么答案应该是零；否则一定存在一个右端点最左和左端点最优的区间，容易发现它们的点应该尽量向里靠，这样应该是优的。于是处理完贡献之后问题的规模就减小了 \(2\)，边界就是前面有交的情况，复杂度线性对数，瓶颈在排序。
D
很憨的题目。
差分一下，假设差分出来的序列是 \(\{c_x\}\)，还有一个东西就是初始序列 \(\{d_x\}\)。画一下发现对于一个确定的 \(c\)，\(d\) 某一位翻转会导致结果的柿子中某个 \(\text{cnt}_x\rightarrow n-\text{cnt}_x\)，而每个元素实际上都是可以进行如此这般的变化的，所以总的贡献应该是 \(n^m\)。只需要考虑差分序列即可，显然其方案数应该是 \(m^{n-1}\)。乘起来即可，话说这玩意是不是可以直接找规律啊。
E
思考什么样的情况是有解的，显然应该是分别排序之后序列合法。考虑换一种方式描述这个限制，发现等价于在 \(b_x\) 处加一，然后 \(a_x\) 处减一，希望数轴上任意前缀不为负。提取出所有本来就不合法的区间，考虑用最少的区间去覆盖它，有显然的贪心，对于每个左端点贪心找最大的右端点即可。
ARC148
A
你停止收讯号，我开始搜寻不到。
B
到底有谁知道，是几点钟方向，你才会收到暗号。
C
画一下发现如果只输入一个点，那么答案是这个点和所有孩子的数量之和。如果输入多个点，有些点的贡献应该就被抵消了，大概就是如果一个点既是选中的点又是选中的点的孩子，那么它反而不用被操作。暴力判断即可。
D
AT 特有的博弈论问题。
假设那对小情侣已经选了 \(n-1\) 个数了，那么根据那俩的尿性它们的和应该保持相同。最后会剩下来两个数 \(x,y\)，发现如果要合法当且仅当 \(x\equiv y\) 或者 \(x+\frac{n}{2}\equiv y\)，因为这样才能使得女方不论怎么选男方都能获得最终的胜利。想到配对，相同的数配对，配不了差半轮的数配。如果模数是奇数直接判断即可，如果是偶数考虑剩下来的配对数量，感觉和奇偶性非常有关系。如果是偶数，那么每次男方选择配对的数，那么最后会累积偶数个半轮，然后就能凑齐七颗龙珠召唤原神。如果奇数感觉没有什么特别好的策略，猜想先手胜利即可。具体用 set 维护即可。
E
这个故事告诉我们凡是涉及形如 \(x+y>t\) 的限制，果断 \(x\rightarrow|x-\frac{t}{2}|\)，然后从大到小排序，这样会具有非常多的性质。具体到这道题就是无论当前的数是大还是小，它们的决策实际上是一样的，都只能放在前面出现过的两个大数之间，分类讨论一下即可。用两个计数器维护当前大数的数量和小数的数量，假设分别是 \(a,b\)，那么总共有 \(a+b+1\) 个空，其中 \(2b\) 个被禁止了（不存在两个小数相邻），乘起来即可。代码奇短。
F
大概思路是说由于 \(998244353\) 和 \(1000000007\) 很接近，所以可以用前者拟合出一个大概正确的商的值，多做几次就可以得到正确的商。然后过程中要用到很多造计算机的技巧内容，我说实话没有完全理解，比较高妙。
ARC149
A
模拟题。
B
等价于二维偏序的形式，于是二维数点即可。
C
评价是随便构造。
D
相当 educational。
我们希望给一个区间中的数全部减去某个值，等价于区间不动而去移动原点的位置。但是这似乎并不能解决问题，因为如果区间跨原点的话每个元素的决策是不同的。但此时可以注意到一件事情说关于原点对称的两个点答案应该也是对称的，所以可以考虑用原点把区间切成两个部分，然后暴力遍历较小的那个部分的所有元素指向对应元素，然后调整左右端点即可。查询的时候做一次记忆化就可以了，代码写起来非常简单。
E
相对有趣的题目，是不是 D 太难了搞得 E 难度评分特别高啊。
毛估估一个特殊的时间点，比如说 \(t=m-n+1\) 之后，整个数列中最大的 \(n-1\) 个数被排列到了数组的最后，剩下的数以某种比较奇妙的方式排列在前面。之后的操作似乎变得无聊起来，由于当前的虫子已经是最大的那些了，所以它会吞下所有遇到的数并把它放到尾巴后面，于是乎数列整体的架构是不会发生变化的，所以问题就可以直接回溯到上面所述的那个时间点，思考有多少合法序列满足。
令此时希望得到的数列是 \(a\)，原来的数列是 \(b\)，那么画图发现如果 \(a_x<a_{x-1}\)，那么说明 \(b_{x+n-1}\) 应该恰好等于 \(a_x\)。否则条件等价于前缀未确定的数中存在一个 \(a_x\)，并且其它的数都大于 \(a_x\)。而 \(t=x-1\) 时也应该有一个所有数大于 \(x_0\) 的限制，两相对比就能得到一些情况下 \(a_x\) 的位置也是可以确定的。顺着做就可以了，目测代码应该不难写。至于没有到达关键时间点的询问只需要把前缀当成一整个序列即可。
ARC150
A
掠过。
B
枚举 \(x\)，发现 \(y\) 的值是一个整出分块的形式，枚举即可。
C
相当广义的子序列自动机。由于我们不希望终点有所匹配，所以用 \(f_x\) 表示从起点到当前点所有路径中存在的匹配位置最前的答案，显然可以用类似 dij 的方式来转移，复杂度线性对数。
D
感觉上相当阳间的题目。不排除可以找规律找出来。
把期望转化成每个点被选中的次数期望（无论是否造成变化），显然之和其深度发生关系。此时如果打表大概是可以找出答案的，发现答案是 \(\sum\limits_{i=1}^{\text{deep}}\dfrac{1}{i}\)，思考如何理解这个柿子。首先需要理解一个事情，即我们正在进行一次操作，其中的一些是不合法的，然后需要求某个操作出现的次数期望。需要理解的是我们大可把不合法的操作拿进来正常算期望，这样是正确的，因为可以认为选中不合法的就让次数掉进黑洞里，并不会影响所求的期望。具体到这道题，问题变成了 \(n\) 个点选全的期望次数，这是经典的。
E
感觉很强的题目，就是那种什么 AT 特有的推理游戏。
首先转化为折线图，默认最后点是高于原点的，否则可以通过翻转来满足条件并且答案不变。考虑第一次操作，图中有两根线是重要的，一根是 \(y=a_n\)，另一根是 \(x\) 轴。高于第一根的第一次一定翻转，夹在两根之间的 L 也会在第一次翻转。显然第一次翻转之后呢末端会变得出奇的高，高到不可能有 R 在后续过程中被翻转，于是考虑 L 的情况，会发现和原点交点之后的所有 L 都会被翻转恰好一次，进行一个计数就可以了。脑车麻了。
F
很有意思的题。首先你得会朴素 DP，用 \(f_{x}\) 表示可以解决大小为 \(x\) 的问题时需要用到的最小前缀大小，转移上，你得照顾到最后一位是任意数的情况啊，所以 \(f_x=\max\{\text{next}_{f_y,x-y}\}\)。然后似乎并没有什么优化的方式了，但是有些智慧的人类发现这玩意是可以分治处理的，考虑当前区间 \((l,r)\)，思考对于一个长度 \(k\)，有哪些 \(p\) 可以更新 \(p+k\)。由于 \(f\) 是递增的，所以能去更新的 DP 值应该是 \(\text{next}_{f_{mid},k}\)，于是问题变成了哪些 \(f_p\) 可以做到这个值，用 \(pre\) 就可以快速找到，然后问题就变成了一个区间更新单点查询的问题了。用 vector 和线段树分别维护。
ARC151
A
省略。
B
枚举第一个不同的位置，那么前面应该是一些位置值相同的限制条件，用并查集简单维护，结合后面的任意取值就能计算答案了。
C
ATC 特有的博弈论题目。考虑 sg 函数，直接做似乎并不是很好做，而一段的形式除了长度可以用以刻画的信息很少，所以打表，发现有很强的规律。然后就没了。
D
不知道为什么可以发现位和位之间的贡献是独立的，所以考虑一位一位得处理。用 \(f_{0/1,0/1}\) 表示目前初始为 \(0/1\) 对现在的 \(0/1\) 的贡献系数，转移是简单的。
E
比较无聊的题目，发现一般情况下等价于求两个串的最长公共子串，爱怎么做怎么做，反正 SAM 是简单的。如果两个串非常不幸一个相同字符都没有就考虑计算二者的距离，可以用 bfs 或者 dij 去做，需要注意一些细节。
ARC152
A
掠过。
B
记得是个选择结构题目。
C
啊。你需要知道每次操作之后序列的整体架构是不会发生变化的，也就是说可以认为最后的答案之和最大值最小值的差强相关，只需要把最小值最小化即可。最小化特别像裴蜀定理的形式，所以把所有的差值的两倍和极差拿进来求 \(\gcd\)，然后求较小的余数即可。
D
相当牛逼。\(n\) 为偶数显然无解，奇数时考虑以 \(t\) 为基准把点划分成一些环，环的数量和环的长度应该都是奇数。显然可以一些边将一个环变成一条链，考虑如何把链连起来，于是牺牲一半的环充当中间的连接部件，方案是简单的。然后就没了。
E
还是很厉害的一个题。
考虑如何更加好地描述题目中的运动，考虑用 \(p_x\) 表示前缀和，那么点 \(x\) 左边的值就是 \(p_{x-1}\)，右边是 \(p_x\)（因为总体异或和为零），那么可以把点抽象成 \(p\) 的序列，相撞就相当于删除考前的那个 \(p\)。然后可以推出整个序列稳定的条件，即任意的原始 \(p_x\oplus v\ge v\)，计数是简单的。
F
attention is all you need。不想写了。摆了。
ARC153
A
循环结构题目。
B
模拟题，稍微优化一下即可。
C
不想写。
D
随便枚举一下就可以了。
E
再不写这两个题它们就要开始发酵了！
考虑对于当前已经得到的一个串 \(s\) 以及等待加入的一个字符 \(c\)，考虑贪心地去放置以得到最小的结果。发现如果 \(c\le s_l\)，那么放左边更优，否则放右边更优。反过来考虑这个过程，也就是考虑 \(s_l,s_{l+1},s_r\) 的大小关系以还原上一步可能的决策。显然如果 \(s_l\le s_{l+1}\)，那么上一步可能通过添加开头字符转移过来；如果 \(s_l<s_r\)，那么上一步可能通过添加末尾字符转移。把状态画成一个网格图的形态，把转移用箭头画出来，发现图具有极强的性质。
具体而言，去除掉无法转移到目标位置的状态，发现左边是一个分成了一些段的阶梯，并且每个阶梯右边的端点都是相同的，转移也是具有很强的性质的，如果理解了状态的话这些都是很好理解的。转移上发现是一个走格子的形式，是个非常典型的卷积形式，用 NTT 优化即可，后面都不是重点了。当然还有一些细节需要注意但是我不想写，只能说一定一定要把题想清楚了把样例模拟清楚了再去写代码，不然大概率会出大问题的。望谨记。
F
感觉相较于 E 这道题没有那么厉害。思考什么时候不合法，先去除一些诸如颜色不够的平凡情况，然后可以对于可能出现的环的大小分类讨论，以下只讨论存在三种颜色的环，否则没有意义。如果环的大小大于 \(3\)，那么显然合法。如果环的大小恰好为 \(3\)，那么可以想到如果对外只有一条边，那么不合法当且仅当剩下的所有边都是一个颜色并且都只能和底边同色，这种情况的贡献是每个环一个 \(6\)。然后思考两条边的情况，发现无论如何都不合法，舍去。
再有就是一些相对一般的情况了，由于每个环只能有一种颜色，建圆方树之后等价于每个圆点的每个孩子都只能有一个颜色，并且三种颜色都应该出现过，这是容易计算的。
ARC154
A
让小的尽量小即可。
B
相当于一个后缀没有重排，直接找最长的是字串的后缀，贪心匹配即可。
C
AT 特有的细节巨大多的奇怪题目。
D
\(O(n\log n)\) 的操作想到直接归并排序，于是需要一个 cmp 函数。而构造这个函数需要 \(1\) 的位置，而这一点是可以 \(O(n)\) 求得的。然后就没了。
E
大型诈骗题。
首先拆柿子。\(f_p=\sum[p_i>p_j](j-i)=\sum[i_i>p_j]i-\sum[p_i>p_j]j\)。考虑每个 \(x\) 的系数，假设当前该位置的数是 \(a\)，那么左上的每个数会贡献 \(1\)，而右下的每个数会贡献一个 \(-1\)，所以系数就是左上减右下，就是左减去下，就是 \(i-a\)。所以 \(f_p=\sum i^2-ip_i\)。
考虑每个位置 \(p_x\) 的期望，此时需要一个结论是说如果该位置被操作过，那么这个位置的期望值应该就是 \(\frac{n+1}{2}\)，可以打表得到，也可以分析一下。大概是考虑一个位置可能得到哪些数，发现原位置是 \(y\) 和 \(n+1-y\) 的数转到 \(x\) 的方案数是相同的，以此类推就可以得到上面的结论。那么我们需要做的就是找到每个位置没被操作的概率即可，这显然是简单的。复杂度线性对数。
ARC155
A
at 特有的奇怪分讨大题。
B
拆柿子。发现 \(||x-a_i|-b_i|=|x-(a_i+b_i)|\text{or}|x-(a_i-b_i)|\)，并且前者要求 \(x\) 比 \(a_i\) 大，后者要求小，总体看来就是在后面两个数中取较小值。于是把 \(a_i-b_i,a_i+b_i\) 丢进集合之中，考虑用 \([l,r]\) 中的数尝试匹配。如果匹配上了很好，否则找两个端点对应的答案即可。用 set 维护。
C
又是分讨。好好玩哦。
观察最开始的状态。如果可以进行两奇一偶的操作，那么很好，你想干什么都可以，因为这两个奇数是可以游走的，如果遇到奇数团那么只需要把偶数塞进去就可以智能地解决问题，而且偶数也是可以如此的，两个奇数可以一步步蚕食这些偶数，把偶数归到一边。需要考虑到无法进行两奇一偶操作的情况和偶数的数量比较少的情况。
D
博弈论题目。
由于值域不算大，所以设计状态似乎只能以当前黑板上的数是什么为依据来设计。记 \(f_x\) 表示当前的数是 \(x\) 的胜负状态（当然也可以认为是这个状态下的 \(\text{sg}\) 值），那么思考转移。它应该可以转移到一些因数，假设因数是 \(y\)，如果存在必败的后继那么当前一定必胜；如果所有后继都是必胜，那么此时有拖时间的策略，即令 \(\text{cnt}_x\) 是计数器，重新设计状态 \(f_{x,0/1}\) 额外记录当前步数奇偶性的胜负状态，那么此时有额外的情况 \(f_{x,\text{cnt}\&1}\) 必胜。
至于如何找到合法的 \(x\rightarrow y\) 的原始转移，令使得转移合法的数列中元素数量是 \(g_{x,y}\)，那么发现可以简单去重得到 \(g_{x,y}=\text{num}_y-\sum\limits_{y|z,y\ne z}g_{x,z}\)，递推即可。复杂度说实话不明但确实可以过。
E
atc 特有的把线性基祖坟刨了的题目。
考虑如果数列中有元素零，思考如何把线性基中的某个元素消除，发现只需要把包含这个元素的值分到一个集合中并且把剩下的分到另一个之中就可以达到目的。可以发现一次最多可以消除一个线性基的基底，于是答案就是线性基的大小。如果不存在元素零，那么考虑硬造一个元素零，具体方法是考虑让所有数异或上某个数，然后按照之前的方法计算，取最小值即可。用 bitset 即可通过。
不明觉厉。
ARC156
A
我为什么要写 A 啊。
B
思考哪些数能通过一次 \(\text{mex}\) 被造出来就可以啦。
C
原神说得好，做 SPJ 的题要考虑别人 SPJ 怎么写，如果结论是 SPJ 比原程序跑得慢那么要么是出题人要么是你在玩原神。具体到这个题，感觉如果 \(k\) 大了不好做，所以结论是 \(k=1\)，证明嘛考虑构造方法。一条链和原来的最长公共子序列为 \(1\) 当且仅当他们是反着来的。所以考虑从叶子向上构造，每次选择两个叶子反着赋值，这样是正确的。复杂度线性，数据范围比较小大概是为了方便写 SPJ。
D
老牛逼了。原神玩家特有的消消乐大师。
简单说一下，大概就是考虑每个和什么情况下出现的次数是奇数，发现由于出现的次数是个一串组合数相乘的形式，然后分析一下发现等价于出现的情况是 \(n\) 的一个划分，而 \(a\) 比较小所以可以从高到低枚举每一位思考这一位分配给哪个数并计算代价之和即可。
E
你应该学会数数。
首先考虑什么样的数列是合法的。首先和是偶数。如果没有相邻点不能相连的限制的话有一个限制是说不能有一个点的度数找过一半（不然一定出现自环），考虑这个限制之后相当于不存在相邻点的度数之和严格超过一半。充分性和必要性很好证明，接下来考虑如何计数。
直接做不好做，考虑容斥，发现这道题里需要容斥的情况异常的少，只有一对相邻点度数超标、相邻两对点度数分别超标的情况，不存在更多的情况是因为如果两对不相交的相邻点都不合法，那么总度数不久超标了。于是思考如何对上面两种情况计数，只需要枚举超标的那一对点的度数和是什么并计算方案、枚举那三个点大概的度数是什么并计算方案即可，计算方案等价于希望让一些取值在 \([0,x]\) 中的数和为 \(t\) 并求方案数，这个问题是经典的，做好记忆化的话稍微分析一下就能发现复杂度大概是 \(O(nm+k)\)。
似乎没什么了，细节有点多，需要对当前要求的东西有清晰的认知不然很容易出问题，但都很好理解。也可以参照代码加深理解。
F
相当牛逼的题目，不是很懂出题人是怎么想到的，大概是我太菜了。
首先考虑问题的弱化版，即每个位置考虑选或者不选，在两个集合相同的前提下最大化集合的大小，那么只需要每个位置连两个可能的取值，每个可能的取值拆点限流，然后大概建成六层的三明治就可以求解出集合的大小了，但是这样找出来的答案有可能是不合法的，因为对于一个位置可能出现两个出度都没有被选择的情况，也就是说这个位置不知道选什么，就不符合题目中的要求了，所以我们希望构造一组解使得每个位置都有合法的决策。
然后你就需要对 Dinic 算法的本质有一定的了解了。如果我们不考虑最优解而仅仅考虑可行解的话，只需要每个点都取 \(a\) 就可以了，表现在网络流中就是集合 \(a\) 中出现过的数都满流，并且上述元素和第一次出现的位置出现的边之间的边也是满流。然后在这张残余图上跑最大流就可以跑出一组最大可行解，这是因为我们 Dinic 算法 check 的过程中是按广搜序来确定当前流的路径的，而分析如果存在一个使得解不合法的流就一定存在一个使得解依然合法的流比它短，于是算法的正确性就得到保证了。
ARC157
A
忽略掉相邻相同的情况并分类讨论即可。
B
如果可以的话我们当然希望尽量多地把 X 翻转成 Y，此时可能希望尽量多地合并一些连续段；如果无法做到的话说明我们需要把一些 Y 翻转回来，然后就是一个什么 AT 特有的分类讨论了。
C
非常套路的题目。
D
暴力去做即可。大概就是你横着分出来的每一块列都应该是总数的因数，而这样的分界方案是很少的；相似的，横着的也是一样，甚至是被更强地限制着。所以要做的就是枚举，划分，然后暴力检查，你会发现复杂度是正确的。
E
不明觉厉，一开始胡了个做法假麻了，然后看了题解发现题解是对的，至于如何快速找到正确的表示方法我不清楚。他就是用 \(f_{x,y,0/1}\) 表示子树 \(x\) 中 \(x\) 的颜色特定的前提下并且已经选择了 \(y\) 个点（按照题目中的限制，这些点理应构成独立集）时最多能选择多少个非叶子节点，然后分析发现这玩意是连续的。我的方法也是差不多的，但是状态定义不一样，然后导出来的方程就不连续然后就寄了，感觉有点玄学，需要靠时间手玩解决。
F
首先你需要注意到一个结论说最后的答案不会小于 \(\dfrac{2}{3}n\)，具体证明考虑任意连续三个数对一定至少有长度为 \(2\) 的匹配，当然了这是一个很松的上界但是已经够用了。考虑一般求最长公共子序列的方法，即 \(f_{x,y}\) 表示两个前缀的答案，由于本题中答案比较大故而许多状态是无用的，于是可以用 \(f_{x,y,s}\) 表示两个前缀并且前缀差值部分的翻转情况是集合 \(s\) 的最大长度和字典序最小的答案，\(s\) 这一维的大小只有 \(2^{17}\)，暴力转移即可，看似复杂度很高但是跑得飞快。
ARC158
A
挖掘操作的性质，发现一次操作不会改变奇偶性，也不会改变和对 \(3\) 取模的结果，那么一开始对这两个值进行判断即可。
B
找具有特殊性质的一些数暴力计算取最优解即可。
C
很简单的题目没有什么好说的。
D
AT 特有的随机化题目，它随机化的是解啊，这不是显得相当牛逼。
发现左边恰好比右边多 \(n\) 次，如果 \(L(x,y,z)\equiv R(x,y,z)\)，那么有 \(L(x/k,y/k,z/k)=kR(x/k,y/k,z/k)\)，于是考虑反过来进行这一过程，即先随出来一个什么 \(x/k,y/k,z/k\)，然后根据柿子可以计算出来 \(k\) 的值，所以就可以还原出一组可行解。当然有一些边角情况可能不合法，解决方法就是多随几次直到合法，可以证明复杂度是正确的。
E
本来是一个非常傻逼的题目但是场上不知道为什么方向走错了。考虑分治，显然可以 \(O(n)\) 暴力求出中心点到任意一个点的最短距离，设上面那个点到某个点的最短路是 \(f\)，下面的是 \(g\)，左右两边各是 \(f_l,g_l,f_r,g_r\)，需要注意的是右边的边权不包括中心上的点权。然后考虑两个点的最短路在哪里会合，发现他们在上面那个点会和当且仅当 \(f_l+f_r\le g_l+g_r\rightarrow f_l-g_l\le g_r-f_r\)，排序之后发现决策对应的一个前后缀，二分维护一下即可。总的复杂度是 \(O(n\log^2n)\)，应该会有更好的复杂度。
F
发现一个位被多次操作的话前面的操作是无效的，所以我们只关心到底操作了哪些位以及这些位有效操作的相对顺序。
ARC159
A
跳过。
B
你大可进行模拟，然后发现有性质，具体是什么性质我也忘了。
C
首先思考什么时候无解，发现和显然是有性质的，因为每次加数的和是固定的，所以分析其对 \(n\) 的余数就能得到显然不合法的情况，此时猜想其它情况都合法并尝试给出证明。找到最大数和最小数，然后用两次操作把它们的差值缩小 \(1\) 即可，具体来说就是在正序加倒序加的基础上调两个数的位置即可。
D
题解区说得好，垃圾题。那就鸽了算了。
E
发现题目描述的就是一个类似二分查找的过程，考虑建出查找二叉树，由于两个孩子的大小差距被限制了树的深度不会太深。考虑题目要求的内容，画图发现等价于求一个连续段虚树的大小，而虚树中只有两个端点处可能包含非区间内的节点，发现可以以深度为瓶颈暴力求出；然后我们需要的另一个信息（即首尾节点的距离）也可以如此暴力求出。然后就没了。
F
一段是好的当且仅当不存在绝对众数，这是容易猜并且容易证明的。思考如何解决这个问题，自然用 \(f_x\) 表示前 \(x\) 个数划分的方案数，但并不好转移。思考绝对众数的性质，然后一些相当天才的大脑就想到了用 cdq 分治来加速这一过程，因为跨区间的严格众数只会有 \(\log\) 个，具体证明考虑前后缀都是这个数量，毕竟每次更新都意味着数量的倍增（似乎非严格众数也有这个性质？），然后对于每个质数画出折线图维护前缀和转移即可，这一算法的复杂度显然是 \(O(n\log^2n)\)，可以做到线性但我不会。
ARC160
A
你甚至可以用 nth_element 暴力去做。
B
令 \(n=\sqrt m\)，那么一个数对中至多出现一个大于这个数的数。如果都小于那很好，方案数就是 \(n^3\)；如果有一个数比它大，令为 \(t\)，那么剩下两个数的取值范围都是 \(\frac{m}{t}\)，整除分块即可。
C
就是一个 DP。令 \(f_{x,y}\) 表示当前等于 \(x\) 的数的数量为 \(y\) 的方案数，由于每个数向后一次就会消减一半，所以这样做的复杂度是对的。
D
首先把合法的数列计数转化成合法的操作序列计数，这要求我们让数列和操作序列之间一一对应。具体到这道题，大概就是让每个数都西瓜投手不超过 \(k\) 次，这样是可以一一对应的。于是操作序列大概是这样构成的：对于每个点，令以其为左端点种的西瓜投手棵数为 \(b_x\)，再搭配上随便怎么分的豌豆射手的名额就可以构造出操作序列。由于西瓜最多 \(nk\) 个，枚举这个数目并容斥 \(b\) 不合法的方案数，大概答案是 \(\sum(-1)^x\binom{n}{x}\text{ch}(s-kx,n)\)，此时复杂度是 \(O(n^3)\) 的。
然而可以把豌豆射手丢进来当成是没有限制的西瓜，这样一来就可以在 \(O(n^2)\) 的时间内解决了。主要是计算组合数那里还要一个 \(n\)。
E
有个老题是说给一棵树，希望加一些边使得不存在割点之类的，那个题的结论是说只需要遍历一遍然后把叶子们按照 dfn 排序，最后交错着连就可以了。感性理解是正确的，理性证明也是可以的但我不是很懂。至于这道题，如果叶子个数是偶数个那么很好，按照上面的策略连边即可；否则一定会有一个叶子被连了两条边，此时就需要分类讨论了。如果叶子中有最小值那很好啊，忽略某个点然后让小叶子连他就可以了；如果不是叶子的话，那么答案应该是叶子的权值加上最小值，于是思考哪些叶子是合法的，这是容易分析的。还有一个特殊情况即三脚海星的情况要取次小值。
F
好好好。
\(n\) 很小，但又没有小到阶乘的程度，于是考虑 \(2^n\) 设计状态。从大到小填数，假设大于当前讨论的数的位置是 \(1\)，小于等于的是 \(0\)，当前位置合法当且仅当经过操作之后 \(1\) 恰好构成了一个后缀，具体 DP 用 \(f_x\) 表示原序列已经填了集合 \(x\) 的位置的并且符合前面条件的排列数目，转移上考虑下一个数填在哪里即可，暴力去做是 \(2^nn\) 的。但是可以优化，因为有许多操作实际上是没有起到效果的。分析一下，令一次操作有效当且仅当存在一个排列，经过前面的操作之后仍然有 \(a_p<a_q\)，记这样的操作数量是 \(c_{p,q}\)，可以证明有效的操作的数量不增，原因在于每个从无效变得有效的数对 \((p,x)\)，都存在着一个数对 \((q,x)\) 从有效变得无效，加上原来的影响，可以得到前面的那个结论。所以只需要维护 \(c\) 和 \(\text{link}_x\) 表示序列 \(x\) 经过当前操作最后的形态即可，复杂度 \(O(n^32^n)\)。
ARC161
感觉是比较披风的一场。
A
排序之后判断一下就可以了。
B
贪一下即可。
C
显然从叶子向上考虑。每个点当前有一些孩子，如果孩子的黑白颜色数目相同那么会向父亲那里传送一个请求，如果请求产生冲突显然不合法，如果没有冲突看根即可，如果没有请求贪心地改成父亲的颜色以减弱冲突。好像当时吃了 114514 发罚时。
D
猜个结论就可以冲了，不知道为什么数据范围那么小。考虑轮换着连边感觉很优，交上去就能过。不是很清楚为什么，也懒得研究。
E
感觉相当披风。考虑如何验证一个方案是否合法，发现可以用 2-sat 简单验证。然后似乎就没有什么关键性质了。题解说可以打表或者观察图的形状性质辅以直觉口胡一类的高妙东西得到随一个方案大概率合法的结论，题解区那动辄几千字的证明看都不想看。于是做法就是随一个，check 一下，不行换下一个，你可以认为复杂度是正确的。
F
形式上特别像那个什么 BJOI，并且由于不用二分直接建模跑一个最大权闭合子图就可以了。如果跑出来大于零的话那么一定不合法，然而有可能等于零，因为整张图就是一个边数恰好为点数 \(n\) 倍的所谓子图，所以就会寄掉。问题变成了寻找一个真子图使得其的比值恰好为 \(n\)，思考这样的一个图需要满足什么条件。发现等价于每个点都有向外的 \(n\) 个出度，并且出度都在子图内，也就是说是个强连通分量。判断一下就可以了。
ARC165
E
题外话：AT 里很是有几道这样的题，可以做做看。至于题号我记不得了，如果你像大佬 赵悦岑 一样板刷了 ARC 的话应该是能做到的。
套路地把期望拆到每个点上，记 \(E_x\) 表示点 \(x\) 产生贡献的概率，那么答案自然是所有的 \(E\) 累加起来的结果，思考这个东西应该怎么求。按照类似于 ARC150D 的思想，考虑按照一个排列选点，如果选的点不合法就忽略此次操作，会发现这样是不会影响期望的。于是 \(E_x\) 的含义变成了断掉所有排列中比点 \(x\) 更靠前的点的连边之后，剩下的联通块大小仍然大于 \(k\) 的概率，显然这个概率就是这个点产生贡献的概率。
于是就可以 DP 了。用 \(f_{x,p,q}\) 表示子树 \(x\) 中选择了 \(p\) 个点在 \(x\) 之前，并且子树内有 \(q\) 个点和根在同一连通块内的方案数，转移上就是一个树形背包，在根处用得到的方案数（当然要乘上两边点内部的排列）除以总的排列数即可。可以通过。
标签：那么,题目,一个,可以,合法,几道,ARC,即可,考虑 From： https://www.cnblogs.com/Feyn/p/17741387.html