AT做题记录（旧，176-138，顺序）
dsy081101
·
2024-10-01 16:45:40
·
个人记录
ARC刷题总结：
ARC176:
A：
考虑每次染一条斜线，可以让横着和竖着的每个位置都+1，再考虑要求的染色个数是点数M，于是让每个点所在的斜线被染色即可。
技巧：网格图上构造方案时的染色法，同样的还有异或染色、同余染色，此题属于同余染色。
B：
很奇怪的题。这谁想得出啊？考虑当 M<N 时，有 2^N mod (2^M-2^K)=(2^N-2^{N-M}\times(2^M-2^K))mod(2^M-2^K) = (2^{N-(M-K)}) mod (2^M-2^K) ，于是可以降幂处理。然后就是特判几个特殊情况即可。
技巧：对于原数和模数都包含相同部分时，考虑让原数 减去 模数乘以什么东西 ，抵消掉原数一部分，接着考虑递归处理。一定要注意过程中产生的边界情况
C:
乍一看，似乎完全不可做，考虑发掘更深的性质， max(a,b)=c 代表了 a=c 或 b=c，且 a,b\le c ，考虑从宽松到严格地处理约束，发现按照c从大到小处理即可，方便思考可以让a到b连接权值为c的边，每次判断 a 和 b 那个可以填 c ，如果都行，代表此时ab已经在图上被孤立，可以直接让答案乘以2，注意判断无解。
技巧：对于max/min 的限制，可以按照值域排序之后按值域扫描处理，当然也可以直接做2-sat和前缀和优化建图。
对于很多限制条件，可以考虑限制条件的宽松程度，按照宽松/严格程度顺序处理可能会简单许多。
ARC175：
A：
考虑在环上每个人都能拿到勺子当且仅当每个人拿的方向是一样的，否则绝对会有人左右都被拿了。枚举一号拿的方向，扫描检查即可。。考虑处理每个人拿哪个方向不容易，建议直接分讨2*2种情况，否则很容易出问题。
技巧：环上问题，考虑断节点，就会变成若干链，链的性质通常更强
B：
考虑已经匹配好的括号不用再去管，于是贪心做一次括号匹配。匹配完成后变成 ")))))((((((" 状物，可以用两个变量表示。接着考虑贪心，交换一次两边各消耗1个，单点修改每次修改在一边消耗2个，优先用1把两边消成只剩一遍。
技巧：括号串做完匹配是 )))(((((( 。如果对于每个位置代价一样的话，已经完成的位置便不需要继续花费代价了。
C:
先考虑求一组最小解，然后再要求字典序最小。首先想假如 i-1 位置已经确定了，在确定 i 位置时，一定是在 i 的区间限制内尽可能接近 i-1，由于差的绝对值之和等于极值点之差，这样一定是最优的。注意对于一开始的一段要特殊处理，因为0位置没有确定。接着考虑构造字典序最小的方案，由于之前的构造方法，上坡段肯定已经确定好了，只需要管下坡段即可，倒序枚举每个位置，如果是下坡段，就向下一位标齐，绝对不会破坏一开始的最小限制。
技巧：的绝对值之和等于极值点之差，最小化它只需要相邻位置接近即可。有多个构造条件，考虑从宽松调整到严格。继续考虑，此题也是增量构造的思想。
D：
树上构造出恰好k个，尝试填满，也就是每个节点都比父亲小，那就会有所有点的深度之和的贡献，如果不及，则一定无解。
然后考虑微调，减少lis之和。让一个节点和下面交换不好做，因为贡献不好算，于是考虑换成更一般的方式。
让一个节点不再出现在任何子树的lis中，也就是填一个相当大的数，大于所有子孙，一次会让结果少siz_u。
对于每个节点都能这样操作，从深度浅到深，填的值从大到小。每次贡献互相独立。
然后尝试选点，可以考虑dp，但是复杂度过高无法接受。
那就考虑一个朴素的贪心，从大到小试填，感觉很错。
但是仔细思考，发现类似 神秘数 一题，一个所有在总体积内的元素都能被选择到的充要条件是：\forall i ，a_i\le \sum_{j=i+1}^{n} a_j +1 充要性可以考虑增量归纳。 此题显然满足此条件，于是可以贪心选取。
ARC174:
A：
最小字段和模板，当C>=1时，求最大字段和，C<1 (C<=0)时，求最小字段和。
要点：注意数据范围是 |C| 不是 C ，所以一定要分类讨论。
B：
少见的评分问题，首先绝对不能被迷惑了，就算我现在选2、3可以提升评分，但是之后想要超过3分还是要投4、5，那我就不如不选2、3，于是直接考虑4、5即可。
技巧：拉均分问题，低于目标分的都不如不要。当有很多操作，但是有些操作最终须要别的操作才能达成目的时，要警觉这些操作是否有用
C：
神奇概率题，待补，大致思路就是发现轮数相当多，于是不用轮数做状态，用取了了数字个数作为状态，无穷的转移可以写成方程，解出来即可递推转移。然而这个题最难受的是先后手的考虑，一定要考虑状态的对象，什么时候加贡献。
技巧：无穷轮数的游戏，可以考虑换成有限的东西，比如取的物品为对象，解方程转移。
D：
打表找规律题，关键是不要眼瞎，不要看漏数位
ARC173：
A：
直观的想法是试填法+数位DP，十分套路。但是考虑有更简单的解法：考虑用九进制数写出来，然后每位减一，注意保留前导零，然后输出的时候每位代表这一位上要填第几大的数，记录上一位结果即可。
技巧：求K大的某数，可以直接数位DP+试填法。
要点：在用n进制考虑k大时，一定要关注前导零的问题，前导零很多时候会影响答案。
B：
贪心，有点启发性，考虑什么时候直接33配对很假，那就是很多店共线时，计算最多点的线上点数，让它们与直线外的点贪心匹配，匹配得完就一定可以让每个点都被匹配，匹配不玩就只有剩下的线上节点不被匹配。
启发：可以考虑一种理想情况，然后借此考虑不理想情况，发现不同位置作为突破口。
技巧：匹配问题，可以先确定一个极大的内部绝对没有匹配的集合，然后让它和集合外元素贪心匹配。
C：
想一下一个数什么时候不是中位数，就是+1-1地修改后不存在区间和为0，于是一定是+1-1交替的，否则就可以构造是中位数的区间。于是对于每个数往两侧扫描，扫到相对大小关系相同的点，就记录答案。这样复杂度是对的，考虑每次扫过一个点代表这个点左右正负性相同，也就是都是山峰或都是山谷，之后这个点答案就是3。特判几种情况即可
技巧：中位数的+1-1技巧，不是中位数就代表山峰山谷交替出现。
启发：考虑左右扫描性质时，保证复杂度的方法1、双指针，2、考虑性质是否重复，借此考虑均摊。
ARC173D（超级好题）：
很很很很很很 有意思的题，一生必做！！！！
套路地，把 （ 和 ） 看成 1 和 -1 ，那题意即可转化。
然后，发现对于任意一条和=0的回路，我可以调整起点位置，让它的任意前缀和非负 （考虑画出来折线，那我选择最低点为起点的话就一直非负）
问题就转化为了是否存在走过所有边的回路，它的和为0
不难想到，随便遍历一遍所有边，求出和的正负性，假如走出来负数，那就再乱走一条和为正数的任意起点回路，中和一下即可；和为正数同理。
再仔细思考一下，发现这还是太复杂了，能再简化：
无论如何，我都要走两条正负性相反的回路，那我可以都考虑，找一个正环再找一个负环，那就是充要的了。
特别的，不存在正环和负环的，只有0环，那也是有解的。
技巧：回路调整起点以满足条件。
技巧：一个正数和和一个负数重复多次一定能评出来0
ARC172：
A：
直觉题，感觉就是可以贪心从大到小，从左上到右下试填，其实很对，因为边长是倍数，能放得下的话绝对可以调整成此方法。
启发：证明困难，相信直觉（？
B：
性质题，不难想，但是很有趣。对于每个位置能填 ch 的充要条件是最近的 ch 距离不小于 n-k ，不然一定可以构造两个相同的子序列。
C：
将第一个人的决策钦点为A，然后将A看作+1，B看做-1，尝试每次调整第一个人的投票点从i到i+1，画出平面上的折线，分讨一下，即可知道什么时候会影响答案，且可以证明影响之后的答案两两不同，于是可以直接计数。
技巧：交换、微调法处理单人决策问题。
技巧：双值看作+1和-1，类似括号匹配的技巧，然后可以转折线，方便思考
D：
很聪明的构造，首先不难想到，每个点可以对应一维，也就是对应维上设成inf，这样每条边长度相等的。
接着考虑如何让长度变短，产生差距。
想让i和j的距离减小，其实只需要让i在j维上加上一个k，那i和别的点距离只会减小O（1），但是和j的距离减小量相当大，因为 x^2 的增长速度的变化相当大，所以可以看成只改变了i和j的距离。
让每对限制分别减去，要求越短的减去越多即可。
关键点：构造题，要注意题目条件中的等量关系，比如操作次数、点数、位数、维数等之间的关系，很可能会成为突破口。
ARC171：
A：
简单题，但是我不会。看到网格图上的车和卒，发现车的限制更简单，因为只需要每个占领一行一列即可，于是考虑卒的摆放，考虑还有车，于是尽量压缩行列，结论就是空一排放一整排，然后简单讨论摆放方式即可。
B：
看到奇怪的操作，考虑操作的本质，排列上做操作，于是想到置换环，但是由于只能单向置换（有小于的限制），实际上是若干链，连头是最大值，操作结果是每个链上元素都会变成链头（也就是最大元素），考虑怎么计数，在值域从小到大扫描，对最终状态为初始状态的节点，寻找一个小于它的入度空闲节点，连向它，或者连向自己，乘法原理计数即可。
技巧：排列想到置换环，根据变化方向，转化为链，于是计数方法就显然了。
C：
首先，这个是树上的数状物，仔细观察性质，发现只要我选的边集不同，结果一定不同，对于一个点，其周围选中的边删除顺序不同，结果也一定不同，并且不难发现这样是充要的。做一个树上背包样的东西即可。
技巧：用必要条件来凑出充分必要条件。
D：
首先，坑点是题面给的字符串哈希式子和常规的不一样（指数反了）。
根据题意，列出区间字符串哈希关于后缀哈希值的式子，就是 B^{r-n}\times (s_l-s_{r+1}) \mod p 。
根据数学知识，第一部分绝对不为0，于是要整个乘积是0，只有后半部分是0，也就是 s_l = s_{r+1} 。
每个位置的值我们可控，所以每个位置上的后缀哈希我们也可以任意选，只要不超过 p-1 即可。
于是问题变为了建图之后的图是否能 p 染色。是一个npc，n不大，于是考虑状压dp求解，解出一个最小染色数。
关键点：不要想当然，仔细研究题目给的公式，是否会和我们常见的写法一样。
技巧：处理一个npc，考虑状压，一般复杂度不会很劣
技巧：对于模数给定，底数给定，值域不给的情况，我们可以实现构造任意哈希值。
ARC170：
A：
注意到原本就相同的先可以不用管，然后把A-B 和 B-A 看成括号，做一次括号匹配，然后剩下）））（（（（的形状，接着用A-A和B-B再尝试贪心消除前后的无法匹配段。
技巧：双字符变换，尝试分两类，一类不变一类变，不变的看作括号匹配。
B：
注意到值域不大，且问题在r固定时，有l的单调性，于是考虑对每个r，枚举a_k 和 a_j 的值，用类似子序列自动机的东西求最后一个出现位置，对所有的合法a_k 和 a_j 对应的 i ，求max位置，从此位置开始的左端点合法，于是答案可求。
技巧：左端点单调，不止可以考虑双指针，在值域不大时，可以考虑建立子序列自动机或者别的东西，对每个r算出l。
C：
观察：n个数的mex不会超过n+1，于是实际上只需要处理m<n的情况
发现我们并不在意mex具体是多少，只在意还有多少个数可以变成mex，也就是还有多少数没被填过，于是设计fij表示前i个位置，还有j个数字没有用上的方案数，转移是简单的。
技巧：限定一个值相等或限定不相等时，考虑我们是否在意这个值具体是多少，是否可以压缩为剩余个数
D：
非退化三角形，可以直接想到一个关于三边的绝对值不等式，|a-b|<c<a+b ，b是bob决定的，我们可以尝试枚举a，然后判断是否能存在一个b满足找不到c。
对绝对值分讨一下，两种情况是不对称的，分别处理即可。
启发：不是所有问题转化之后两（多）部分是会互相对称的，有些时候出题人不会那么聪明，会写一个不对称的东西。
ARC169：
A：
诈骗题，考虑我递归无穷次之后，我深度约深的点的贡献巨大无比，可以忽略掉深度浅的点的贡献，于是考虑求第一个满足和不是0的层数，在这个层的正负性就是答案的正负性。
技巧：对于贡献只与深度有关的问题，考虑对深度分类，列式计算。
B：
首先，对于一个序列的权值，很好求，可以考虑贪心地取，于是对每个i，求出其最远的可选段右端点 r_i （双指针处理），接着，考虑枚举l求答案，每个l的答案分成两部分，一个是右端点r不超过 r_l 的部分，另一部分是超过的部分。不超过的部分贡献是1，直接加上即可。超过的部分，答案是 r_i 到 r 的区间贡献+1，于是考虑用 r_i 处的答案处理这部分贡献。倒序递递推即可。
技巧：所有区间的子区间划分答案之和，可以考虑倒序递推扫描。
C：
首先一眼就有 O(n^3) 的暴力dp，设 f_{i,j,k} 表示前 i 个位置，结尾是数字 j 且已经连续 k 段的方案数，转移简单。考虑对其状态进行优化，优化掉 k 维，考虑转移枚举结尾段长度，且结尾段前的一个数不能和结尾段数字一样，变成 2d1d，继续考虑优化，发现我求的是 i 的一段前缀之和，于是前缀和优化dp，可以做到 O(n^2) 。
技巧：颜色段dp，可以考虑把代表结尾长度的一维放到转移中而不是状态中，可以方便优化。
D：
首先做一个转化，把循环，转化为取模 n 。
然后就能考虑去掉循环之后，也就是不取模的结果，这样更容易描述操作次数，即为 \max(a'_i-a_i)
待补，大致是将合法的b的充要条件列出，然后对求最值得条件松弛。
ARC168：
A：
签到题，直接考虑尝试顺序填数，再将钦点>的部分拉出来处理，具体而言，对每段>区间，增加 n*(n-1)/2的贡献。
注意：构造序列，没给值域范围一般能乱搞
B：
k-nim游戏，先考虑怎么求游戏的SG。每堆石子独立，可以每堆石子分别求出来异或。对于一堆石子的一个局面，只能走到其前面k个局面，于是可知其sg值是一个长度为 k+1 的周期，仔细思考之后就是 x\mod(k+1) 。至此，此题基本完结。
技巧：对于博弈论，一定要手摸n=1、2、3情况，然后尝试数学归纳。
C：
很好的题。首先要发现答案与序列无关，只与ABC的个数有关，可以意会一下，我对其排序之后可以做同样的变化，原本结果不同的排序之后再变换结果也不同。
于是考虑枚举 AB BC AC ABC 之间的变化次数，做多重组合数，注意CAB和BCA是两种对应ABC的交换方法，一定分开处理。
技巧：求任意交换之后的不同情况数，注意是否和顺序有关，无关就考虑值域上枚举交换方法。
D：
区间，值域500，一眼区间dp。
考虑如何设计状态转移。发现我们对于一个区间，可以枚举断点，断点上要求能用此区间内的一个线段覆盖到，然后加上断点前后的值，整个不难转移。
转移的实质，是前后分别求出答案，然后最后用中间的断点去选一条线段，发挥最大作用。
技巧：要求区间中存在至少一个点满足什么条件，直接考虑枚举第一个出现位置，这样可以简单转移。
ARC167：
A：
签到，首先用代价0的物品补全到2m个物品，然后根据初中数学，可知让小配大是最优的。
B：
C：
先想怎么算一个情况的答案，贪心地从小到大枚举值域，那贪心地连边一定不劣。接着考虑计数，MST权值和，拆贡献，每条边在MST的出现次数，可以考虑分讨其左右的最近段的存在情况，计数即可。
技巧：MST权值和考虑拆贡献。MST考虑贪心取边。值域扫描序列考虑连续段。
### ARC166：
A：
注意到 AB-> BA ，实质是让A后移，不要当成括号匹配类的东西了。
B：
坑点是在于很少有人会想到能对常数个条件做状压，想到就解了。
启发：看见常数个限制，直接转成k个限制，k很小，大概可以帮助解题。
C：
很怪的条件，但是根据这个可以想到把每个方格左上右下分隔开处理，于是划斜线，每条斜的是独立的。预处理斜线地填法，就可以方便地回答询问。
技巧：每个格子上有多种操作，且每种操作的条件独立，考虑拆点。
此题注意到左上右下的操作条件是互相独立的，于是拆格子。
D：
并非二分，因为二分之后还是不好做。
所以直接考虑一个贪心或者dp。
dp看起来就不太适合做这个的样子，所以还是考虑直接贪心。
根据套路，这里贪心看着交换论证不出什么东西，那就考虑增量贪心。
常规的一些套路看起来不管用，所以摸一下性质。不难发现，每一项的上一项小于它，那直接延申过来是很对的，然后还要加入些许新的线段，一定是起始于上一个关键点后面的。
这启发我们，直接增量，每个位置如果比前一个大，就继承，比前一个小，就舍弃一些。舍弃哪些？当然是起点最早的那些。用单调队列维护即可。
假设已经有了前面 i-1 的最优解，考虑 i 的最优解。
### ARC165：
A：
对于有关lcm的构造，想到lcm(a,1)=a(还有 lcm(a,a)=a,gcd(a,1)=1,gcd(a,a)=a 等)
于是想到构造两数和一堆1
要点：对于lcm的构成，要注意是 $p_i^{k_i}$ 之积，不要漏掉 $k_i$ 。
B：
首先，做这样的操作不会让序列字典序变大，于是可知原本就有长k的单调递增段，就不用管了，直接输出即可。
接着，容易想到从低位排序不会很劣。
想到从最后做排序，不过随便举一下就能发现反例。
此时关键点是不要立马否定想法，而是对想法做微调。
观察hack数据，发现，就是可能往前面选一点，可以避开末尾的很小元素。
接着简单分讨一下，即可从后往前扫描，得到最优位置。
C：
首先，这个题目是瓶颈问题，想到二分。
二分一个答案之后，由于题目的描述容易让人联想到二分图判定，假如直接相邻的两个点距离小于mid的话，这两个点绝对不能同色。
不过这样还不够，因为可能有两个点不相邻，但是距离很近，颜色还相同，就寄了。
同样，考虑对解法做微调。关注简单的情况，就是只隔了两条边的点之间的情况，发现假如我答案大于了这两条边的边权之和，那绝对无解，且这是充要的，为什么呢，因为隔着3条边的满足情况绝对被2条边的情况包含了。
所以我们只需要修改二分上界即可。
技巧：对于任意两点之间距离的限制，考虑下放到只隔着两条边的点对上，考虑证明充要或者得到启发。
### ARC164：
A：
很像三进制，先进制转化，然后就很显然了，首先总数不够肯定不行，接着考虑把一个拆开，拆掉1个i位，要3个i-1位，奇偶性绝对不变，且这是充要的。
技巧：-1+3想到奇偶性不变
B：
简单环不劣，显然，因为我可以拆开，第一次回到起点就结束即可。
我们不会往回走，所以考虑直接连边，异色直接连，最终回到起点，要同色。并查集维护即可。
技巧：找是否存在环，可以考虑拆成简单环判定，因为这样可以不管往回走的条件。
C：
首先，转化一下题面，bob无论如如何都至少会拿到小的面，于是每张牌都减去小面，小面直接先记录答案。
问题变成两面正数和0，bob当然会想让拿走正数，且对于一个局面会拿走做大的正数，Alice对此，会将最大正数翻面。
重复次操作，直到所有初始正的牌全部被取走或者反面，此时Alice只好翻出正数，Bob则直接取走Alice翻的。
技巧：双数贡献，假如无论如何都会得到至少小的贡献，那就先提前计算小的贡献。
技巧：双人最值博弈，从后手的决策开始考虑，考虑数学归纳法。
### ACRC163：
A：
显然对于任意划分方案可以调整成两段，直接枚举断点判断即可。
技巧：多段划分求段之间关系，考虑是否可以将段合并起来减少段数。
B：
画数轴上，就是让每个数都在a1a2的区间内，发现让a1a2改动是不劣的。
排序之后类似双指针扫描求解。
注意：改变之后求相对位置，考虑目标区间是否能被改动
C：
待补，很怪的裂项
### ARC162：
A：
类似区间覆盖，每个人从前半段到结尾位置连线段，被覆盖的人就不可能是后半段的rk1了。
同时，此题有特殊性质，因为是排列，且前半段是顺序的，因此可以直接用最终成绩求后缀max，成为了后缀max的位置就可能成为rk1。这和线段覆盖是等价的。
B：
每次可以让相邻两个数为一组进行交换。
可以操作2n次，所以对于每个数最多2次操作内归位。
于是想到按顺序归位，每次把要归位的i和i后面一位一起移动，假如i是最后一个数，就尝试先往前面换一次，再交换。
最后可能会有两个数，但是没归位的情况，样例也提示了，此时，就无解。
技巧：相邻两项一起交换的情况，可以当一项处理。
C：
同样考察后手的Bob会怎么操作。
为了破坏mex，Bob会直接填上k。
所以假如一个节点有多个空位，则一定不能填出mex=k。
技巧：非传统博弈都先考虑后手会如何操作。
### ARC 161：
A:
每个位置要么是山峰要么是山谷，那我一定可以排序之后，钦定偶数位置上大于奇数位置，那构造就是简单的了。
启发：M 形状的填数，考虑拆分成偶数和奇数位，分别考虑。
B：
首先，足够小的可以暴力求，然后对于一个大的数，一定可以只保留最高 3 位上的 1 。但是假如我没有至少 3 个 1 ，那显然可以减 O(1) 个数，直到减到有 3 个 1 为止。
### ARC160：
A：
k 小，考虑 kth element 算法。接着只需要想办法让我们能快速比较两个交换方法即可。
接着考虑怎么写 cmp 。除了当 l=r 时，我们出现的结果是两两不同的，可以直接特判掉。 然后对于两个不同的交换方案，我要么第一个变化位置不一样，要么第一个变化位置的值不一样，所以可以直接 O(1) 地比较两个方案。
技巧： k大，考虑 1） 二分答案；2）kth element ；3）超级钢琴
B：
不难想到，我可以钦点 a、b、c 之间的大小关系，然后枚举中间数，那我只有 $O(n^{0.5}) $ 种合法中间数，每种情况可以快速统计方案数。
### ARC159：
A：
B：
首先，我直接模拟是不行的，考虑为什么不行，因为我可能要减相当多个 1 ，并且我不能得知每次下一个在什么地方会变化。
所以我根据上面的两个点，分别攻破。
第一： 我两数不互质，一定可以除以公约数，轮数不会变化。
第二：我要考虑求下一个不互质的位置，也就是使得 $ gcd(a-x,b-x)>1 $ 成立的最小的 x 。仔细分析之后，使得目标达成的 gcd ，一定是 $a-b$ 的约数 ，于是枚举约数，即可保证复杂度。
### ARC158：
A：
三个数，每次操作，三个数分别 +3 +5 +7 ，可以看成都 +5 ，那就是 -2 +0 +2 ，然后就类似均分纸牌了。
技巧：每次操作会改变每个数，可以考虑整体 +delta ，那就可能变简单。
B：
一坨和、一坨比值，自然想到一定和绝对值最小、最大的数字相关，于是取这24个数字，暴力枚举，就不用想很多事情了。
技巧：比值与和大概和绝对值的最值有关，一般取最大最小跑暴力就可以避免分讨。
### ARC157：
A：
看见限制条件，直接想到对于 X 和 Y 的连续段做分讨。
技巧： XX、XY，直接反应连续段。
B：
首先看不足以让 X 全部变成 Y，那就每连接上一个连续段，加 2 的贡献，否则 +1 ，那就贪心优先填上短的 X 连续段。
接着看要额外变 Y 为 X 的，考虑原序列中 Y 的连续段，删一个连续段 -2 ，否则 -1 ，因此从长到短填上。
C：
贡献的平方之和，首先考虑 1 次方之和，也就是所有贡献之和，直接 dp ，转移，尝试填上这一位是否能和上一位连城 YY 连续段。
接着考虑完全平方公式， $(x+1)^2=x^2+2\times x+1$ ，于是我贡献的二次方之和，也可以尝试基于这个来递推，
$\Sigma(x_i+1)^2 = \Sigma x_i^2 + 2\times\Sigma x_i + \Sigma 1$ ，最后的 1 的和，会计算 路径条数 次，也就相当于贡献的 0 次方之和。
技巧： k 次贡献之和，考虑二项式定理拆开，分项降次计算。
### ARC156：
A：
显然，奇数无解，然后假如有大于 2 个 1 ，或者 2 个 1 不相邻，那就一定可以隔一个匹配。
B：
mex 要么是 全集 的，要么不是，不是的话对整体没有影响，就是内部任意选择，所以可以枚举 K 次操作完成之后的 mex 增加了多少，接着就是 <mex 的数每个插入了多少从，可以直接插板法计数。
D：
### ARC155：
A：
回文问题，经典地画出线段，首位相同，这样对于 K 相当大的时候，可以略去许多无用部分，只需要考虑最中间。
接着， K 很小的时候，就可以考虑暴力判断。
技巧：回文问题画线段辅助思考。
B：
两重绝对值，考虑拆掉内层。于是，询问就变成了求区间内的所有 $a+b $ 和 $ a-b$ 最接近询问给的 i 的元素，可以 set 维护。
技巧：无论多少重绝对值，都先考虑从最内层开始拆，这样问题会最大地简化。
C：
三数和为偶数，一定只有 0 个 或者 2 个奇数，也就是连续偶数之间可以任意交换。假设奇数也能任意交换，则一定可以转化到前奇后偶的标况。
考虑什么时候奇数也能任意交换，只当最长奇数段长度至少为 2 时，满足。
否则，奇数一定会变成不动点，把序列的偶数划分为若干独立的段，段内又要讨论是否能被交换。
技巧：钦定了和的奇偶性，则一定考虑加数的奇偶分配。
技巧：对于序列交换问题，假如存在复杂的限制条件，则一定要去考虑是否存在不动点，可以把序列划分为若干不相关子问题。
### ARC154：
A：
和不变，乘积最小，那就大配小就可以。
技巧：交换两个数对应数位上的数，考虑和是否不变。
B：
C：
每个数值赋为下一个位置，考虑颜色的连续段变化，我可以循环位移，所以就是目标串的颜色段序列为原串的一种循环同构的子序列。
技巧：相邻互相赋值，考虑颜色连续段。
### ARC153：
A：
有些数位之间有相同限制，所以可以合并数位，每个数位只需要考虑第一次出现，然后还原出原数即可。
B：
首先，看到横纵是独立的两个问题，对每个点的横纵坐标拆开讨论，那就是每次做前缀区间翻转和后缀区间翻转，首先可以平衡树直接做，但是由于只有前后缀，所以可以进一步简化。
对于每个 x ，关于 a 做了翻转， 那前缀的 x ，会变成 a-x ，后缀的 x ，会变成 a-x+m 。所以其实是在 mod m 意义下做了 -x 操作。于是可以直接线性复杂度维护。
技巧：两维操作，尝试观察两维是否相关，是否可以拆开。
技巧：前缀、后缀操作，通常可以换更为简单的结构。
C：
D：
DP的时候，如果是一整行的状态一起转移，但是不能状压，考虑它们的相对顺序是否有用，以及要标记的点是否有什么性质，然后就能对其每层重新按照它们性质的大小标号排序，那标记的点就变成前缀后缀了。
技巧：dp如果不关心相对顺序，可以每层重新打乱，重新安排一个顺序之后说不定状态可以转化为前缀。
### AEC 152：
A：
最坏情况，就是所有团队都正好隔了 1 个位置做，之后再有 2 人团队的时候就没地方了。模拟即可。
要点：对于显然无解的情况，一定要特殊注意，因为可能题面不会说，但是代码会有区别。
B：
最多会相遇 2 次，发现 2 次相遇 一定没有 1 次相遇 优秀。
所以让两个人背对背，枚举出发点。
技巧：至多进行常数次增加多余代价操作，可以尝试操作尽量少的时候是否一定是最优的。
C：
把操作放数轴上，就是关于某点翻转所有点的位置，要求最小化最大值，由于区间长度不变，所以就是最小化最小值。
考虑对于点 i 做翻转操作，对最小值的贡献，也就是 新的最小值 $2\times S_i-S_n$ 与原最小值 $S_1$ 之差 ，也就是 $S_1 - 2\times S_i-S_n = len-2\times S_i$ 我的贡献可能是正也可能是负，怎么办呢，我如果当前的正负和我想要的不一样，那就让序列绕别的点随便转一下，然后再转回来，那一定不会变劣。
所以就是要对所有 i ，求出的贡献 $len-2\times S_i$ ，张开线性基，得到的最小正整数，根据这个正整数一定是出事的 $S_1$ ，减去若干倍的 所有代价的最大公约数，之后的数值，也即余数。
技巧：2*x-y，反应到数轴翻转。
技巧：若干操作，求最小值，可以让操作对最小值的贡献计算，考虑贡献，不只是用于计数问题。
技巧：贡献和操作奇偶性有关，那一定要考虑是否可以增加无用操作互相抵消。
### ARC151：
A：
计算有多少位置一开始就一样，这种直接填 0 。
接着计算 1-0 和 0-1 分别多少，先全部 0 ，然后再从低到高依次修改成 1 ，使得 汉明距离相等。
B：
字典序大小，于是枚举相同前缀，发现我和置换之后相同，就会形成若干连通块，连通块内所有数值相同，然后钦点下一位置上的数字的大小关系即可直接计数。
同时，这个题还有一种解法，就是字典序大与字典序小是对称的，所以排除掉 A=P 的情况即可。
技巧：只要和大小相关，都可以想想一个二维平面，拉一条 y=x 的直线，直线两侧的大小关系相反。
技巧：排列与置换环。
C：
数学归纳法。
首先我每个断点，把原问题分割成若干独立子问题。
每个子问题，有 4 种情况：
1、U-U 2、U-(x/y) 3、(x/y)-(x/y) 4、 (x/y)-(y/x)
分别数学归纳即可。
要点：数学归纳法一定要检查边界的情况是否模拟错误，否则得不出结论。
### ARC150：
B：
考虑枚举 A+X ，那么最小的 Y 就是 $\lceil \frac {B}{A+X} \rceil \times (A+X) -A$ 可以直接对 $\lceil \frac {B}{A+X} \rceil$ 整除分块，且容易知道块中最左边的一定是最小值。
技巧：处理两数和的最值，可以列一个数关于另一个的式子。
技巧：向上取整也能整除分块。
C：
图上的子序列匹配，其实类似最短路，只不过换成了最短子序列匹配。
要点：子序列自动机的建立对象千万不要想反了，反了就大概率无法接近正解。
启发：子序列匹配其实本质上是一个求解最短路的过程。
技巧：“所有都包含” 转化为 “最小的也包含”。
### ARC149：
B：
考虑最优的构造，由于 LIS 的性质，交换两个相邻的位置，如果保证这样不会更优，则一定已经获得最优的构造。
所以首先尝试让每个位置按照第一关键字排序，这样之后，每次交换相邻每个位置，一定会减小第一个序列的 LIS ，然后第二个序列还至多只会增加 1 的贡献，所以交换时不优的。
因此，最大的 LIS 之和，就是按照第一个序列为关键字排序之后的情况。
技巧：构造最值，可以考虑转化为构造一个情况，使之无法通过操作变得更优。
技巧：双序列同步求最大和，可以尝试让第一个序列最大，再微调第二个序列。
### ARC148：
A：
一定可以 mod 2，使得产生至多 2 种不同数字。
然后考虑何时是 1 ，那就直接求所有差的 gcd ，如果 gcd >1 ，那么，可以 ，mod gcd ，获得所有的都是 0。
B：
最小化字典序，所以让第一个 p 变成 d。所以旋转左端点就确定了，接着枚举右端点即可。
C：
考虑只管一次怎么做：从根开始尝试。
仔细观察，发现每个节点翻转情况会和其父亲节点一样。
所以每个颜色和父亲节点不一样的节点都要翻转一次。
技巧：多次询问，先处理单次，再寻找性质。
技巧： $fa_{root} =0$ ,可以处理根节点和父亲的关系 ，就不用分讨了
### ARC147：
A：
模拟即可，用 set 维护，是 logV*logn 的。
B：
操作二，等价于在奇偶位分别做冒泡排序。但是我们要求先最小化 操作一 的次数，每个 操作一 可以把一个奇位和偶位交换，所以先用 二 把 所有要交换位置奇偶性的数放到一起，一起交换，然后再分别做冒泡排序。
C：
考虑两端极值，不难想到一定最边上两个数要尽量接近，也就是最小最大，最大最小。接着考虑最小最大是多少，其实就是所有右端点中的最小值，因为比它小可以调整到它，比它大，则一定不是最小。最大值同理，是最小的左端点。
接着进一步考虑正确性，首先，我选的一定不会使得两个数值来自相同的一个区间，原因就是假如来自相同的区间了，则一定存在一个 l<r ，也就是两端一定已经相交过了，这之后的区间一定都包含了同一个点，所以这个时候答案不会再变了。
于是可以拆开左右端点，分别排序之后贪心地考虑。
技巧：区间可以拆成两个端点，这样有些时候可以证明最值只和两边分别相关，就不用处理区间选择问题了。
技巧：构造两两之间关系之和的最值，可以拆贡献，然后转化为子问题。
### ARC146：
A：
简单贪心，从大数填到小的。
B：
考虑按照二进制位贪心，贪心地从高到低，让每一位上变成 1 的代价最小的几个数字的对应数位变成 1 ，证明显然。
C：
超级好题。
题意转化：S 不存在子集 T ，使得 |T| 是偶数，且 T 中元素异或和为 0。
考虑增量，记 $f_i$ 表示又 i 个元素的集合数。可以发现 $i\le n+1$ ，接着考虑怎么从 i 转移到 i+1 。
考虑一个集合，内部所有偶数子集异或和都非 0 。那么一定不存在两个不同的奇数子集的异或和相同，否则可以取这两个子集的不相交部分。
考虑在一个大小为 i 的合法集合中加入一个新的元素 x ，使得加入之后仍然是一个合法集合。那么显然 x 不能是之前集合内的任何一个奇数子集的异或和，且可以是此外的任何数值。于是我可选的 x 的数目之和 i 有关，也就是 $ 总元素数量 - 奇数子集树 = 2^n-2^{i-1}$ 。
注意我每种选法都一定会被计算 i+1 次，因为我可是增加了任意一个数字得到的转移，所以最终的转移方程就是 $f_{i+i}=f_i\times\frac{2^n-2^{i-1}}{i+1}
技巧：和子集有关的限制计数问题，考虑增量计数，增量之后一定要分阶段去重。
技巧：子集有关的限制（特别是和子集大小、位运算等有关的），一定要考虑是否之和子集大小相关。
ARC145：
A：
考虑头尾，
一样就不用管，直接考虑下一位，不难发现下一位无论是什么，都能继续变换首尾，使得头尾相同，接着同理，一定可以变成回文串。
不一样的话，如果是 AB ，那一定不能解了，否则是 BA ，那可以对结尾做一次变换，那就是变成 AA ，对于下一层要么相同，要么是 BA 。（感觉此题虚低了）
技巧：回文串，可以考虑开头位和结束位，想办法让它们一样，之后考虑数学归纳。
B：
直接考虑 B 怎么做，B 一定会贪心地选满，让 A 无从下手，所以游戏只会进行一个回合，那 A 为了把 B 逼死，一定会尽可能多地选择。策略出来了，此题便迎刃而解。
C：
ARC144:
A：
显然，根据之前一个题的结论，不难知道 f(2x) 的最大值取在 x+x 不会进位时，等于 2*f(x) ，接着就是考虑如何构造 f(x)=N 了，贪心地思考，一定填上 4 是优的，填不完的往前放即可。
技巧：设 f(x) 表示 x 各个数位之和，则有 f(a+b)=f(a)+f(b)+[a+b 时的进位次数]\times 9 在处理 f(a+b) 或者进位次数的时候都相当有用。
B：
最小值的最大，考虑二分答案，直接贪心 check 即可。
C：
首先有一个绝对对的构造 k+1 k+2 k+3 ... n 1 2 3 ... ，但是这个不是字典序最小的构造，因为可能可以把 1 给往前移，但是也不能直接移到 k+1 位置，因为这样可能导致之后的 2*k 没有地方填。
考虑字典序，贪心，每个位置考虑没有填上的最小数字能不能填上，也就是此时位置 i 上原本放的数字能不能延迟一点出现。
对于能否延迟出现的判定，也是单调的，所以可以直接维护。
启发：最小构造，先构造一个解，再考虑调整成最小
启发：线性的限制，观察是否具有单调性，是否能直接线性维护。
ARC143：
A：
其实就是只用两个位置减的操作使得最小代价使得每个位置相等，存在相当多解法。
B：
首先发现这样的位置就算有，也只会有一个，原因可以画图。
然后就枚举填什么数，组合计数一下即可。
技巧：假如一个位置会对整行、整列产生影响，考虑画两个这样的关键点，观察是否会矛盾。进一步的，假设关键点对外有超过 O(1) 个限制，都考虑多个关键点之间的关系，是否能共存。
C：
先考虑一种策略：每次模仿对方的取法。
那么直到最后，相当于让每堆石子个数对 X+Y 取模了。
令，b_i = a_i mod(X+Y) 。
当 \forall i,b_i < X 时，先手必败。
否则，继续分讨：
当 X\le Y 时，先手可以把所有 b_i > X 的位置取走一个 X ，这样之后，后手便面临了第一种情况，后手必败。
否则，进一步分讨（似乎很容易漏掉）：
假如我存在一堆石子， Y\le b_i <X ，那么先手一旦取了这一堆，对于后手，就变成了上一种情况了，先手必败。
否则，先手必胜。
技巧：两人操作不同的博弈，考虑是否能让两人操作对应相同，也就是对相同位置连续操作（考虑 nim 的证明方法）
ARC142：
A：
f(x) 一定是把 x 首尾去除之后的最小正序或者逆序。
首先如果翻转之后更小，则无解。否则用原串和反转之后的串分别尝试在末尾增加 0 。
B：
有若干种构造，考虑最简单的一种：奇数行和偶数行分别填小的数和大的数。
技巧：偶数个数，小于的不等于大于的，那可以尝试让一边恰好过半，也就是尝试隔位置填。
C：
ARC141：
A：
枚举循环节长度，循环节内容一定是第一段的数或者第一段的数 -1 。
B：
考虑一个事实：最高位单调不减，且异或的最高位单调不减，那么说明最高位位置一定严格递增，证明显然。
于是就可以直接 DP 计数了。
技巧：前缀异或单调，尝试要对最高位讨论。
技巧：位运算相关，尝试拆位。
C：
很好的题，
首先对原序列画出折线图思考。考虑处理字典序最小的部分，对于每一个无序组，一定是因为走到 0 了，且此时顺序之下还要往下走，那就不合法了，所以换过来的一定是它之后的最小的一个左括号，被换过去的一定是一个右括号，并且这样可以用 P确定出来 序列所有在 0 下方的位置的信息。同理，把原串反转再翻转过来，那求 P 就相当于求了 Q ，所以再用 Q 做一次即可确定所有 0 之上的部分，这是充要的。
技巧：括号序列拍折线。
技巧：原问题难以考虑，可以考虑怎么反过来求，然后还原过程。
技巧：字典序与贪心试填。
ARC140：
A：
考虑已知 S ，怎么求 f(S) ，那就是循环节长度。
最小化循环节长度，可以枚举循环节长度，然后尝试贪心地修改，每个对应位置上保留众数。
B：
第二种操作没前途，考虑第一种操作，肯定是要选两侧地 A、C 个数最多的做操作 1 ，个数最少的做操作二，用一个堆就可以。
C：
首先，最理想的情况，就是从中间开始，一加一减，波浪式推进，构造出来的 LIS 长度为 n-1。
尝试推广一下，我起点是中点一定很优，所以尝试第一步跳到中点，然后波浪进行，这样答案下界就是 n-2 的了。
尝试证明最优性：假设我存在一个 n-1 的答案构造，那么一定是每个都记录了，那我如果有两个邻项增减相同的话，易得一定存在至少一个点不在 LIS 上。
注意特判一下一开始就在中间的情况即可。
技巧：构造若干限制的最值，可以先尝试考虑去掉一些限制之后的最值，然后再加上限制，尝试证明调整方法的最优性。
技巧：序列最优，可以先假想一个理想情况，然后使用开头几项，使得后面变成理想情况，那就只有一开始的一点点是不优的。