做题记录(Tricks)

· · 个人记录

1.middle

题目链接

本题的Trick就是数的大小关系上的处理以及中位数的处理。在考虑到大于某个数的数的个数与序列规模有关，需要动态增加或减少序列元素时，或者单纯不太好用数据结构维护时，可以考虑本Trick，就是将大于某个数的所有数全部设成某个值(通常为1)，然后把小于那个数的数设成另外一个数(视情况而定，经常为0或-1)，就可以将求个数的问题变为求和。

对于中位数，采用上述Trick，将小于某个数的数设为-1，最后求和即可，和应该为0或者1。

2.小Q的棋盘

题目链接

本题的Trick为树上遍历的最小步数。首先访问一条链的均摊耗费为1。在除了这条链上的其余地方访问一个点要再退回来，均摊次数为2步。因此尽量使这条链最长，即为直径，剩余的点的访问均需要2步，最后答案为直径长度+剩余的点\times 2。

3.树上染色

题目链接

本题的Trick为树上边算贡献思想。对于求点集内距离和一类问题，发现不好直接求时，可采用对每条边分析贡献的方法。对于每条边，其被算的次数为两端点数之积，因此直接预处理大小，枚举边算贡献即可。

4.Sonya and Problem Wihtout a Legend

题目链接

本题Trick为将严格上升子序列转换为非严格上升子序列。采用对于每个数a_i，将其变成a_i-i，这样每个位置多出来的1会被消掉，等效成非严格上升子序列。

5.Land Acquisition G

题目链接

本题Trick为对双序列数值大小问题的处理。假设现在一个元素有两个参数，现在要对元素数值大小关系进行维护以及询问。在不影响答案的情况下，按某个维度对序列排序，然后将一定不优的值去掉，最后的序列会变成一个维度单增，一个维度单减的。因此可以结合二分等单调结构进行处理。

6.Counting reorders&&Counting Sequences

题目链接1

题目链接2

这两道题的Trick主要为利用容斥原理从反面进行计数。当发现题目不好或无法直接计数时，可以考虑从反面进行统计，即用总方案数减去不合法的方案数，或者理解为利用容斥，钦定某个范围较广的条件，通过多次粗略的计算得到答案。具体到第二题，先钦定每个数都可以出现，方案数为k^n，接着减去钦定一个数不可以出现的方案数，为C_k^1 (k-1)^n在加上钦定两个数不可以选的方案数，为C_n^2 (k-2)^n……第一题较为复杂，容斥内需要再套一个DP，通过DP计算钦定条件的方案数

7.School Excursion

题目链接

本题的Trick为使用bitset对可状态压缩问题的优化。对于许多题目，到最后的状态遍历不太好或者无法优化。如果此时涉及到的状态可用一串0,1串表示，那么可以使用bitset代替暴力，大幅优化常数。比如本题，最后化简为可行性的背包，发现不太好质的优化，于是使用bitset优化常数

8.Programmers and Artists&&Eden 的新背包问题

题目链接1

题目链接2

这两道题的Trick为使用前后缀和拼凑答案。在遇到一些答案不好计算，由前后两段答案构成，且分界点在移动，前后两端答案可以预处理的情况可以考虑使用一段前缀和一段后缀拼凑成答案。比如第一题，可以预处理出前缀x最大a人的和与后缀y最大b人的和，最后前缀和后缀拼接即可

9.GCD XOR

题目链接

本题的Trick为使用暴力程序找规律。在遇到一些看上去有特殊性质，但不太好找的题目里面，可以考虑先打出暴力然后找规律，最后再使用暴力验证性质正确性。该方法也具有保险性，即使没有找到特殊性质，依然有可以拿分的暴力。该方法在多数构造，博弈论，组合与数论题目中极为有效

10.Coin Arrangement

题目链接

本题的Trick为序列分配问题的贪心策略。在许多序列题目上，贪心应用的非常广泛。一般情况下，序列分配问题都要往贪心方面想一想。其贪心策略多为优先满足当前点，不够的向后面贷款。比如本题，优先满足当前节点，不够的贷款，然后有多余的相互支援一下即可

11.骑士共存问题

题目链接

本题Trick为棋盘问题的处理。对于棋盘问题，格子与格子之间有关系的，如果卡住了，都应该考虑一下染色处理。染色一般是进行黑白间隔染色，但是不应该局限于这种染色方法。事实上，斜着染色或者多色彩染色也比较常用（至少在数竞中），需要视情况而定。染完色便可以考虑转换为图论或者DP来做。染色的详情可以参考小蓝本初中卷的组合问题

12.Beetle&&Hammer 2

题目链接1

题目链接2

第一题的一个的Trick为费用提前计算。在大部分DP题目中，都可以在到达一个状态的时候再计算其答案。但是在有些题目中，然后到达一个状态再计算会使得复杂度变劣或者直接不可做，在这类题目中，如果发现当前状态对后面状态的影响比较好计算，那么就把这个影响提前计算了，在后面转移的时候只用考虑上该转移本身的贡献即为答案

这两道题目还都有一个Trick为处理区间运动问题的方法，这里讨论的区间运动指运动过程中所有事件被经历一定不劣。区间运动问题有一个结论，即为在任意时刻人经历的事件构成一个区间，该区间中所有时间被经历，所有点走过。这时可以就考虑区间DP，区间DP的同时记录当前在l或r的那一端即可

13.Stones&&Deque

题目链接1

题目链接2

这两道题的Trick为使用DP来刻画博弈论问题，或者用DP来刻画博弈中先后手的更替转换与选择。具体来说，在博弈论问题中，当发现状态不好确定最优转移时，可以考虑使用DP来记录下来所有最优状态，然后对于每个状态都模拟一下下一步走什么。由于博弈可以看作是先后手的转换，所以转移上一步的最优是对于当前的后手而言，当前这次转移应该是和上一次的最优矛盾的，故可以用于模拟博弈。用这两道题来说，第一题是用DP来表示先手必胜状态，然后转移到下一次时状态取反，表示当前的先手必胜变为了先手必败。第二题是使用区间DP来描述一段区间内先手的最优状态，在到下一回合，当前的先手变成了后手，因此当前状态的贡献是下一状态后手的贡献，因此贡献算到后手上

14.Permutation&&Deforestation

题目链接1

题目链接2

这两道题的Trick为大范围排列型计数的处理技巧。在遇到涉及到排列问题计数的时候，如果对于范围较小的情况可以考虑状压DP或者状压容斥，若数据范围较大的时候可以考虑普通容斥，但是当容斥不太好做的时候并且答案与上升下降的突变位置有较大关系时可以考虑使用插入DP。很多时候，插入DP的第一维为遍历序列，第二位为位置i在前i位中的排名j，转移的时候i-1中排名为rnk\in [j,i-1]的要+1。比如第一题，设f_{i,j}表示前i个位置全满，第i位的排名为j的方案数，然后转移方程比较好写，就是注意前i-1位中排名j以后的在i加入以后排名+1。第二题和第一题比较像，但是首先要注意到如果a[i]>a[i-1]，那么i一定要在i-1之前选，然后就变成了第一题

处理排列计数使用插入DP时，思考方向有三种：把最小值提出来，把最大值提出来，把中间某个值提出来。前两种方向通常是在状态的定义或者转移里面表现，最后一种通常需要作为一个状态表示的维度

其实插入DP的核心思想就是每次新加入一个元素，看一下这个元素对于之前的元素的影响是什么

15.Toll

题目链接

本题的Trick为分层图(或DAG)的处理以及倍增收集答案的技巧。在分层图上，不经常考虑使用Dijkestra，要考虑使用DP，因为DP能干的事情比Dij多，且DP在分层图上比Dij快。在倍增统计答案的时候，如果遇到当前有多个选择，而时间有允许的情况下，就把所有状态记录下来，最后取最优即可

16.滑雪

题目链接

本题的Trick为单流向图的最小树形图的计算。如果遇到有向图求最小生成树，即最小生成树，如果是普通图，那么可以直接走人，如果是单流向图，可以考虑以下贪心。先按照边的终点的Topo序由大到小排序，然后再对于终点相同的点按照边权排序。这样做一定是对的。现在考虑一个比较显然但是错误的贪心，即直接按照Prim算法来扩展。这样一些当前最优的边选择了后会使得其他一些真正优秀的边选不到。这种情况的发生是由于每个点并没有考虑到生成树上所有可能成为其父亲的点和边就选择了一个仅在当前最优的边，因此这个贪心成立当且仅当每个点被扩展到的时候其所有可能的父亲都已经被扩展到了，这样选出来的局部最优才是全局最优，而最开始的贪心就刚好满足了这个条件。因此在单流向图上可以使用以上算法求最小生成树

17.Tower

题目链接

本题的Trick为贪心(或者性质)排序后DP。在部分题目中，如果发现可以使用DP，但是DP的结果和DP的顺序有关时，就考虑先贪心排序后再DP。例如本题，首先抛开顺序不谈就是一个背包DP，但是发现DP的顺序会影响答案，现在要使顺序最优。然后就推式子，\sum\limits_{j=1}^{i-1}w_j\le s_i，两边同时加上w_i，得到\sum\limits_{j=1}^i w_j\le s_i+w_i，发现前面一块单增，因此s_i+w_i单增，所以顺序即为s_i+w_i从小到大

18.Intervals&&Apples

题目链接1

题目链接2

这两题的Trick为单点或区间操作的处理。对于很多题目，区间操作实际是不好处理的，比如DP中，这时候，就需要考虑将区间操作转换为单点操作。同样，有些题目单点操作覆盖面太小，也不好做，要考虑换点为区间。在第一题中，由于DP维护的是单点的信息，区间操作显然无法维护，因此得考虑把区间操作转换一下。这时可以选择对于所有区间都仅在其右端点统计贡献，这样可以保证正确性。区间操作的转换还可以使用差分思想。第二题中，注意到并不知道窗口起始点的坐标，如果暴力遍历一定超时。单点查询单点修改范围太小，要考虑转化成区间查询。这时，注意到如果考虑每个点有贡献的区间，那么这将会变成区间修改，而查询也可以变成区间查询。因此，当发现单点操作覆盖面太小时，可以将每个单点操作变成其影响范围内的区间操作

19.Count Path

题目链接

本题的Trick为树上路径统计的处理。对于树上路径统计的题目，可以考虑在其LCA处统计，这样就变成了每个子树间的计算。这时候如果涉及到合并时，可以使用启发式合并

20.双亲数

题目链接

本题的Trick为容斥原理在数论中的应用。本题有两种做法，思想全部为容斥，而第二种还兼以DP的思想。容斥的应用场景通常为问题不好从正面刚，但是算出一个大概范围较为容易，而使用一些大概范围可以算出正确答案，但是在比赛和练题中，意识到容斥其实不太容易，主要是因为思维太过僵化，思考问题老是走一个方向去想，想不通还是有一种赌徒心理认为自己可以想出来，像这种时候其实应该冷静一点，把所有可能的做题思路写在纸上，一个一个仔细想，不要太着急，不要只是大概一想觉得不对就跳过了，必要时上一个厕所。平时训练时也应该锻炼自己的思维使其不僵化，能够从多角度考虑，使用以上方法。回归本题，首先发现如果要硬求以d为gcd的数的对数其实不容易，需要知道某个数在小于一个数内与其互素的数的个数（这个用容斥能求），就比较麻烦。但是注意到都是d的倍数的二元组个数好求，这就是一个大概范围，这启发我们使用容斥。首先我们需要先清楚需要排除的东西，第一步我们保证了所有数都是d的倍数，那么一类多出来的数就是所有数都是2d的倍数的方案数，还有所有数都是3d的倍数的方案数，这些的大致范围都好求，但是注意到这样排除以后还多排除了6d的情况，应该加上。写成函数的形式就是\sum\limits_{S\subset P} -1^{|S|}\frac{AB}{M_S^2}，P为素数集，M_S为S的元素的乘积，这样就可以使用线性筛预处理了。但是如果上面的思路换一种想法来考虑，就会变成第二种做法。现在我们想要知道d情况的精确范围，但是现在仅知道其大概范围，则我们需要做的就是用大概范围减去其多出来的部分，具体到本题就是所有kd(k\in N^*)的精确范围。然后令人激动的是所有kd都是大于d的，也就是说d的精确范围仅与比其大的数有关，这就可以递推了

21.Cowlendar S

题目链接

本题的Trick为抽屉原理在值域问题上的应用。当发现在某一维上有限制，该限制的大小小于该维度大小时，那么就会有重复的元素，这些重复的元素往往是题目的突破口。抽屉原理出场的场景通常是值域问题，数论(取模)

22.数学实验

题目链接

本题的Trick为可行性DP与最优解DP的转换。在许多DP题目中，直接想到可行的DP状态较为困难，但是想到一个复杂度较高的可行性DP较为简单。这时，如果固定一些维后发现状态满足单调性，举个例子比如本题的可行性DP可以为f_{l,r,k}表示[l,r]内能否拼出k这个数，此时发现单调性，即[l,r]一定，k越大越好，或者[l,k]一定，r越小越好，那么就可以消掉一维状态，比如本题最后选择消去r

23.Xor on Grid Path

题目链接

本题的Trick为通过状态空间的分解优化状态数。或者说，双向搜索。这个方法的应用场景通常是发现状态数很大，状态数增长也很大，而把状态空间分成两份后分别去算答案的复杂度就会低很多。双向搜索的核心思想是将状态空间分成两份后去除冗余答案，将空间树限定在一个合适的大小内，从而求解。一般情况下，双向搜索会以最中间的状态为界，在前面和后面分别进行求解，最后枚举中间状态，对于每个中间状态再求出经过该状态的答案

24.Bigger is Better

题目链接

本题的Trick为双状态拼凑。在有些题目里面，直接获取答案比较困难，这时候可以考虑用两个DP状态来凑出答案。一个DP求出最优解或者最优解的某个信息，最优解的位置，另一个DP沿着第一个DP的路径去走，然后给出答案。或者两个DP分别求出最优解的某个信息，然后拼凑起来。比如本题，直接维护答案显然不好做，空间时间双炸，所以就要放弃一些信息，把这些信息再用另一个数组记录，最后拼凑答案。在本题中，模数以及剩余多少火柴显然无法放弃，那么现在就只剩下位数和答案，显然维护答案是几乎无法进行的，因此就在第一个DP数组用模数和剩余的火柴做维度，最大的位数为答案，第二个DP数组还是用模数和剩余的火柴作维度，达到这个状态的最高位为答案，由第一个数组开路，用第二个数组拼凑答案即可

25.团

题目链接

本题的Trick为虚点优化。在很多题目里面，边数会非常大，或者边是拼凑起来的，又或者图不是连通的不好处理，比如本题，这种情况下，可以考虑建立虚点来进行优化，即对于图额外引入一些点，将图中原本的边或者关系使用虚点与其的边或者关系来代替，这样就可以将边数减少，或者使得图连通。比如本题，发现边是拼凑起来的，边数特别的大，把所有边都建出来显然不现实。考虑到每个点在S中的w值都是不变的，这意味着考虑可以重复利用这个w值，仅建一条边。于是结合虚点优化的Trick，可以想到\forall S_i，建立一个虚点，\forall j\in S_i,j->V_i，这样可以把边数优化到线性的

26.Swap Round Sorting

题目链接

本题的Trick为置换建图。在很多排列变换题目中，排列的变换关系比较恶心，不容易想清楚，这时候可以考虑建图来处理，置换建完图一定是一堆环，这就较好处理了。常见的可以用置换建图解决的题目有的特征就是涉及到排列的变换，比如每个数换到一个新位置去，或者一个序列重排或者排序之类的。比如本题，原序列有序等价于每个数i到位置i去，即i->a[i]建图，建完后发现是一堆环，然后每次交换就是让一个点从环中孤立，特别的，如果现在有一个二元环，那么交换一次会使得所有点孤立，现在求出使每个点孤立的最小次数。这个问题就比较好处理了

27.Farm Update G

题目链接

本题的Trick为删边操作的处理。在图论题目里面，删边操作大都非常恶心。处理删边操作的方法大致有2种，使用以LCT为首的大数据结构，或者逆序维护，后者似乎更加常用。逆序处理的优点在于，它可以把删边化为加边，使得问题具有单调性，当原问题只有删边，或者加边操作具有某些单调性时，就考虑使用逆序处理。比如本题，首先每个点都只会从有关的变成无关的，这具有单调性，其次，有删边操作，删边操作没有特殊性质，加边操作只会在活跃的点间进行，于是考虑逆序维护，然后发现这样做具有单调性，用并查集加启发式来做即可

28.Jump Distance Sum

题目链接

本题的Trick为切比雪夫距离转曼哈顿距离。在有些题目中，会要求求解以下式子\sum\limits_{i,j\in [1,n]}\max(|x_i-x_j|,|y_i-y_j|)，显然这个式子如果直接去做的话很难维护。现在考虑转化问题，这个式子的意义是什么，从(x_i,y_i)走到(x_j,y_j)，斜着走的最小步数。斜着走不太好处理，如果是垂直的那么处理起来相对容易一些，于是考虑对于斜着走建立坐标系，于是(x_i,y_i)就变成了(\frac{x_i+y_i}{2},\frac{x_i-y_i}{2})，然后走一步就变成了在该坐标系上平行于x,y轴走一步，这就转化为了曼哈顿距离，于是排序计算即可。对于这里的处理还有一个Trick，就是将互不相关的维度分开考虑。发现x和y互不相关，于是就可以拆开来处理，其实这个Trick能够应用在很多题目里面以简化问题

29.Help Tomisu

题目链接

本题的Trick为一个数论性质，即若a\perp n，则a\space mod \space n\perp n，反之亦然。或者说，a\perp n，则a+kn \perp n,k\in Z，这个性质的证明比较简单，但是其应用较为广泛，可以用于缩小求解问题的范围。从这个性质可以推到以下结论: n以内与m互素的数的个数为\lfloor{n/m}\rfloor\times \phi(m)+cnt，其中cnt表示n \space mod \space m以内与m互素的数的个数，这样就成功的限制了求解的范围。在遇到n范围较大时可以使用以上Trick先缩小问题的范围。同时，要积累一个等价刻画，即n没有小于等于m的素因子等价于n\perp m!

30.Max to the Right of Min

题目链接

本题的Trick为启发式分裂。启发式分裂本质上就是启发式合并的逆过程，考虑这样一个情况，现在有一个序列，无规则的将这个序列分治下去，即每次分治不是严格对半，每次分下去都要统计分开的两半之间的答案。一个比较直接的方法是在左端点放一个指针，依次枚举，右端点对应的统计答案即可，但是显然这样会被卡成O(n^2)的，于是现在考虑优化。注意到刚刚被卡掉的情况是右端点很多的情况，这启发交换一下左右端点，改为左端点枚举，这样能节省大量时间，于是现在就出现的一个算法，每次分下去，选择长度较小的区间枚举，统计答案，最后会发现这个算法跑得飞快，远超O(n^2)的复杂度。事实上这样做最劣复杂度为O(n\log n)的，可以这样考虑，由于每次选择较小的区间，因此枚举的区间长度一定是小于等于当前区间的长度的一半，如果考虑倒着思考，每次枚举区间长度翻倍，于是复杂度为O(n\log n)。这个方法在很多无规则分治题目里面极为有效

31.Frequency Mismatch&&Fixed Prefix Permutations

题目链接1

本题的Trick为使用Hash维护值域信息。假设现在你在做一个维护序列的数据结构题，当题目对于值域求解的要求不是那么细的话，即不需要区间上某一个值或者某一段值域上数的个数时，通常是是求解某段值域的构成是否相同时，可以考虑对于值域使用Hash，使用数据结构维护，因为Hash满足可加性，可以使用数据结构维护。比如本题，链可以使用树链剖分摊到序列上，题目要做的求解一些区间和另外一些区间的颜色构成是否相同，于是就是用上述Trick，使用主席树维护即可，即可判断是否相同，但是题目还要求出一个不同的颜色，注意到颜色值小于最小不同颜色的Hash值相同，于是使用倍增求解

题目链接2

本题的Trick为使用Hash维护状态。其实Hash可以看作是不可逆的状压，即无法解压的状压，仅能用来比较两个状态是否相等，然而这样做的代价是非常低的，仅是O(n)预处理O(1)询问。这个O(1)询问的优点使得其可以搭配二分倍增或者一些数据结构来维护一些复杂的状态，这些算法或数据结构可以弥补Hash无法维护过程的缺点, 以后遇到难解决的状态判定或者求解之类的都可以往Hash方面想一想

32.Intervals

题目链接

本题的Trick为不等式关系的转换。在一些序列上的题目中，可以使用差分约束转换其为最短路问题求解。但是转换的前提是发现了不等式关系。这里列出不等式关系转换的Trick(遇到了就更新):

  1. 使用前缀和，比如本题。

不只是不等式关系，等式关系也可以使用图论的做法，比如本题，一次询问可以得到两个两个前缀和之间的等式关系，想要得到完整的区间和，就必须让前缀和无缝衔接的差分，于是每次询问都必须有一端与上一次询问重合，于是想到图论，以前缀和建图跑最短路便是最优解

33.Invertible Bracket Sequences

题目链接

本题的Trick为对括号序列的处理。一般情况下，对于括号序列的处理通常是使用栈进行处理。但是在许多题目中，都需要对于序列进行操作，此时每次都去跑一个栈出来不太现实，于是需要其他维护技巧。第一种是将(设为1，)设为-1，然后求和，最后必定满足任意前缀的和大于等于0且总和=0，这个Trick可以配合数据结构来使用。第二种是对于栈序列Hash，再进行处理

34.冰火战士

题目链接

本题的Trick为树状数组上倍增。当发现题目要求复杂度是单\log，现在的复杂度是双\log带二分，而又必须使用树状数组进行统计的时候，可以考虑使用树状数组上倍增来优化掉二分的\log。考虑树状数组的本质，其本质就是使用lowbit将原来的询问区间拆成一些2^i长度的区间，然后求和，这个其实就是倍增思想，预处理出倍增到某个点时其管辖的区间。于是可以考虑在树状数组上倍增，这样可以省略掉每次单独的查询。具体的，以本题为例，从大到小枚举二进制位，当pre_i<suf_i的时候，就倍增跳出去，否则不动，这样由于树状数组已经预处理出来来每个点管辖区间的和，每次倍增都是跳的这些管辖区间，于是可以O(1)求和

35.KUR-Courier

题目链接1

题目链接2

本题的Trick为一半的性质。当发现题目出现出现次数或者和大于一半，或者说所有数出现次数或和都小于一半的条件的时候，可以考虑使用一半的性质(遇到了就更新):

1.如果有数的出现次数或和大于一半，那么该数在该区间内至多仅有一个

2.大于一半的数的出现次数或和大于其他所有数出现次数之和或者总和

36.Sequence

题目链接

本题的Trick为数论中代数技巧的应用。当模数为素数时，可以使用代数中的一些技巧，比如同时扩倍任意有理数，此时直接乘上该有理数的逆元即可，但是需要注意0。以本题作为例子，考虑部分分d=1的时候，显然就是阶乘，直接逆元就可以做。当d\ne 1的时候，如果把问题转换为d=1的情况，问题就能够得到简化。如果将每一项乘上\frac{1}{d}就可以将问题转换为d=1的情况，需要注意d=0的情况

37.Dropping water Balloons

题目链接

本题的Trick为化归和简化思想的应用。当发现两个不同的问题满足相同的条件时，比如排列型DP中把n-1换成n之类的，可以把两个问题变成一个问题来求通解，将所有满足这个条件集的问题化成同一个问题求解，比如排列型DP中把n-1去掉换成n，排列数不变，因为排列关注的是位置间的相对关系，而不是值的大小。应用化归和简化思想的前提是要学会抓住问题的本质，同时要大胆的舍弃掉冗杂条件，这两点能力要通过大量练题来训练。回到本题，首先如果去掉k的限制，那么本题就是一个二分查找，但是有了k的限制，很有可能在查找中途就已经没有气球了，这种情况下需要使用询问次数来弥补气球的不足。那么现在的做法要么就是找到一个最优策略，要么就是要预处理出i次询问j个气球的最大高度。在尝试第一条道路发现失败后，走第二条道路。把问题系统的描述一下，设f_{i,j}表示i次询问j个气球可以把楼层在[1,k]的球的情况全部问清楚的最大k，于是现在考虑转移。现在假设i次测的是t层，现在分情况讨论，假设气球没破，那么应用化归思想，把t+1层看成1层重新再来测一遍，那么答案就是t+f_{i-1,j}，如果破掉了，那么如果要保证那个前面的全部测完了，就只能让t=f_{i-1,j-1}+1，由于两种情况全部要兼顾到，那么两者的t必然是同一个，于是f_{i,j}=f_{i-1,j-1}+f_{i-1,j}+1

38.Turtle Mission: Robot and the Earthquake

题目连接

本题的Trick为转换参考系。当发现在变化的东西很多，然而变化的方式和幅度一样或者相近的的时候，不妨换一种角度来思考，如果把某个元素视为不动的，其他的元素变化的幅度就会变小，或者仅有很少部分元素在大幅度移动，就有可能可以维护了。比如本题，把移动的石头视为不动的，把人和起点视为动的，这样需要考虑的就仅仅只有两个动的元素了，于是就可以直接广搜了

39.Magical GCD

题目链接

本题的Trick为gcd的性质。当一堆数求gcd时，此时如果加进来一个数，那么gcd一定单调不增，同时还有一个更强的性质，加入gcd减小，gcd大小至少减半，这两条性质的应用非常多，非常灵活，需要非常熟悉

40.currency

题目链接

本题的Trick为网络流切糕模型。以本题为例，注意到一定不会往右走，于是转换一下问题，变成构造一个01 seq，0的算上面的贡献，1的算下面的贡献，每一次01转换算中间的贡献。此时可以使用最小割的切糕模型，即在网格图的结构中将同一列或同一行的边在网络流模型上练成一列，即(i,j)->(i,j+1)，再在这个网络流上考虑限制。特别的，对于竖向边，也把其考虑为限制。在这个网络图上，割掉那条边表示选择那条边。比如本题，先用上述做法建出网络图，对于限制(i,j,c)，连边j->i，边权为c，表示如果i处的上面边割掉，j处的下面边割掉就还需要割掉中间的边。特别的，对于最左侧的竖向边，应该连边1->t，边权为该竖向边边权，表示如果选择下面就应该把竖向边也选了

41.Last Man Standing

题目链接

本题的Trick为基于调和数的分块。这个Trick在很多涉及到上下取整的题目中用的较多，并且可以一定程度上代替数论分块。整个Trick的核心思想就是枚举\forall i\in [1,n]，然后将[i\times (j-1)+1,i\times j]分成一块讨论，枚举块，复杂度为O(n\log n) 。这样做有一个好处，就是当有上下取整的时候，同一个块内的元素的上/下取整值是相同的，于是就相当于定下了一个变量。比如本题，要求h\times \lceil{\frac{a}{x}}\rceil 。当 \lceil{\frac{a}{x}}\rceil定下来时，就仅仅考虑h的最大和次大即可

42.Decomposition

题目链接

本题的Trick为对于极小范围数据的处理。当发现有数据范围极小的时候，可以考虑直接暴力遍历所有状态。或者可以直接存入DP状态中，状压或者直接作为维度，复杂度仍然在一个可以接受的范围内。比如本题，当分析出来仅有三个序列的时候，注意到情况仅与序列的末尾相同，并且数值也非常小，因此可以考虑直接将三个序列的末尾存入DP数组进行转移，这样做复杂度依然可以接受

43.Fun Game

题目链接

本题的Trick为对于环化成链的处理。当发现，一个环如果断开后的影响仅与断开后链的首尾有关，就不用将环复制一倍，可以直接钦定断点，然后当成链上的问题求解，最后再计算首尾造成的贡献。在这种情况下，这样做是拆两倍链的上位替代。具体到本题，钦定从第一个串前面断开，钦定第一个正着摆放，然后就可以按照链的方法DP了，最后需要减去末尾和第一个串的公共部分

44.Intersection and Union

题目链接

本题的Trick为有固定初值的递推式的处理。对于一个递推式或者一些别的有依赖关系或者牵连关系的式子，正常情况下是需要使用矩阵乘法来维护的，不过对于一些有固定初值的式子，由于每次的起点是唯一的，因此可以求出一个仅仅适用于这个初值的关系，通常来说这个关系会相对于矩阵简单很多，可能仅仅是乘法之类的，这样就能够简化问题。比如本题，当推出来每次转移的式子后，发现每次区间内的初值是赋值\frac{2}{3}，然后外面的操作是一个有牵连关系的式子，但是初值固定为\frac{2}{3}或者1，然后将这两个初值带入式子发现表现都是变为原来的\frac{2}{3}，再往下带也是这样的，于是外面的操作变成概率乘上\frac{2}{3}，线段树维护即可

45.Censoring S&&消消乐

题目链接1

题目链接2

本题的Trick为类括号序问题。类括号序就是形如括号序匹配的问题，这类问题的形式通常是要消去一些东西，消完一个后合并两端，然后接着消去下一个，消除在一定范围内是连续的，并且消去的顺序为从内向外消去，只有将内侧的东西消完了，才能够给外侧创造消去的条件。比如这两题，只有内侧消完了，才能够消去两边的的。这类问题就可以考虑使用括号序匹配的相同的算法，使用栈进行维护。同时，栈序列也是非常重要的元素，比如第二题就是对于栈序列进行操作。特别的，如果题目是从外向内消去的，那么也可以考虑把问题转化为由内向外消去的

46.Chip Move

题目链接

本题的Trick为对于余数进行前缀和。在一些题目中，需要求出p\equiv k(mod t)且p\le k的f_{...,p}的和，这时候就可以按照余数进行前缀和。首先遍历k，然后再遍历的规程中，更新sum_{k \mod t}。本Trick可以应用在优化很多维度有余数的DP计数问题中

47.Digits

题目链接

本题的Trick为对于仅包含极大乘积的处理。在一些题目中，会涉及到仅包含极大数的相乘，显然高精度是不可能的，时间和代码复杂度双炸，但是此时可以采用对于极大数取\log的方法，将乘法转化为加法，同时缩小数据范围，使得并不会有数量级上的精度损失。这类做法对于精度要求较高，使用时需要注意精度问题

48.Color length&&Coding company

题目链接1

题目链接2

这两题的Trick为贡献拆分。在一些DP题目中，贡献常常和组当中的各种极差相关，非常难处理，放进状态当作维度也不现实，这时候可以考虑费用拆分，将这个极差或者别的什么贡献拆分开，拆成与起始和末尾的求和相关或者与中间过程相关的计算，这样可以避免将统计贡献有关的信息放进状态里面当成维度。比如第一题，不难想出状态f_{i,j}表示a到了i，同时b到了j的最优解，难点在于转移上面。发现每一种字母的贡献与其出现的首尾相关，但是现在不可能把每个字母出现的位置放进状态，这时候就考虑贡献的拆分。注意到对于单种字母，如果其开始了还没有结束，那么对于最终答案的贡献就会+1，而现在知道了i,j，就知道现在有多少个字母还在扩展中，从而可以转移。对于第二题，状态的定义方法可以学习沿用到其他涉及分子集的题目里面。先将a_i从大到小排序，设f_{i,j,k}表示对于前i个位置还有j个组是可以加人的，并且已经分完的组的贡献是k的方案数，分3种情况分讨，注意这里从大到小排序可以避免对于k为负数处理，学习一下。将一组的贡献拆分成为两部分，开组的时候为+，组闭合的时候为-。事实上很多极差的题目，都可以将极差拆分成两部分，首尾两部分分开计算贡献。像第一题，可以看作末位置减去初位置，但是这样做中间最优并不意味着全局最优，于是需要费用提前计算，就变成了直接统计中间过程的贡献

49.Great City Saint Peterburg

题目链接

本题的Trick为\max与\min的互化，以及使用线段树维护单调类信息。对于第一个Trick，有如下式子\max(a,b)+\min(a,b)=a+b，这个式子可以将取\min或\max操作化为加减法，可以在最大值或者最小值确定或者较好求解的情况使用，非常有用。当发现题目中线段树维护的信息是一个单调的序列，但是如果直接维护序列空间会爆，但是序列又可以轻松知道首尾时，可以使用第二个Trick。就拿线段树维护单调队列为例，线段树里面只需要记录，单调栈的首尾。在pushup的时候合并单调栈时，首先ls的单调栈可以直接并上去，rs的一个后缀栈序列也可以直接并上去，其余的序列全部删去。所以现在只需要找到rs中第一个>en_{ls}的位置即可，这个就可以递归询问求解

50.Circlic Array

题目链接

本题的Trick为倍增的应用场景。这个Trick非常重要，在很多题目中都作为重要的优化技巧，所以务必将倍增变成肌肉记忆，在思考过程中增加倍增这一环。在很多题目中，常常每个点或者状态的转移去向固定的，而又需要去依次遍历转移对象，导致超时，这时候，就需要使用倍增来优化遍历速度。每个点转移时固定的，在经历k个点以后到达的点时固定的，于是考虑记下来所有点跳2^i后到达的位置以及得到的答案，最后要用的时候拼凑即可。最后再强调一遍，如果涉及到"跳"的操作，一定要往倍增方面去想

51.XOR Tree

题目链接

本题的Trick为对于多个集合中满足可逆性二元关系存在性查询的处理。在一些题目中，会涉及到在一些集合中，查询任意两个集合中是否存在元素满足a\space opt \space b=k，这些常常会出现在树相关的问题中，比如本题。在复杂度允许的情况下，可以使用启发式合并，对于每个集合开一个set，全局再开一个set，然后遍历这些set，每次查看全局的set中是否存在元素a\space antiopt \space k，然后在启发式合并，将当前set合并到全局set上

值得一提的是，本题还有一个思维方式，就是对于一些相互影响干涉的条件或者操作，给他们定一个统计区间，在计算完在这些区间内的贡献后，再计算相互间的影响就会容易很多

52.Maximum Composition

题目链接

本题的Trick为邻项交换法。在许多DP题目中，常常需要先推出一个贪心结论进行排序，再在这个基础上进行DP，这样做能够将枚举集合变成遍历序列，节省大量时间。在这类题目中，发现贪心结论比较高效的方法之一就是邻项交换法。邻项交换法的核心思想就是考虑相邻元素如何排列会更优，计算两种排布下这对相邻元素的贡献，这样能够考虑到所有情况，因为任何局面可以通过交换相邻元素相互到达。值得一提的是，很多贪心题目也都可以使用这个方法。要注意交换的是相邻元素而不是任意元素

53.Replace the Numbers

题目链接

本题的Trick为集合赋值合并操作的实现。对于一些启发式合并的题目，涉及到两个集合的合并，但是要求强制将集合a合并到集合b上面的情况，就会涉及到赋值操作，而赋值操作的复杂度是O(n)的，无法解释。此时可以使用容器的交换操作代替赋值操作，因为交换操作是O(1)的，于是可以先正常进行启发式合并，接着如果合并到的集合并不是想要的集合的话，就交换两个集合。这算是一个码力方面的Trick

54.String Painter

题目链接

本题引出了自己对于区间DP的一些理解。区间DP适合处理的问题不只是一些区间性质的问题，其实区间DP适合求解几乎所有序列上的问题，只不过很多时候其他形式的DP复杂度更优。区间DP感觉是基于任何一个序列都可以按照一定规则分成若干小连续段这个性质的，这个性质或者思想在很多题里面都能用到，比如CSES-2421，非常重要。区间DP本质上适用于求解序列上无固定顺序的取数或者别的合并之类的操作，枚举断点合并两侧干的就是这个。此时，当可以使用贪心结论知道具体按照什么顺序合并或者合并顺序不重要，即段与段之间并没有任何关系时，区间的合并顺序可以固定下来，变成线性DP。当发现求解的问题天然构成一个整区间的时候，就可以不用枚举断点了，复杂度优化为O(n^2)。因此当发现题目中选数或者合并或者其他操作无顺序时，或者纯纯线性DP不好做时，可以考虑使用区间DP

55.Coin Rows

题目链接

本题的Trick为对于n\times 2的方阵中路径问题的处理。首先比较常见的方法为DP，设f_{i...,0/1}表示i列0/1行的解，这个做法适用于很多问题，然而某些时候复杂度较劣。第二个做法为贪心，按照顺序考虑使得前i列最优，大部分情况下复杂度是优秀的，但是扩展性较弱，最好是在细致分析性质及一些单调性后考虑，或者是在发现DP的复杂度较劣时考虑。第三个是对于只能往下和往右的路径的做法，注意到仅有2行，于是往下的操作只有一个，考虑枚举这个操作的位置，然后统计答案。这个做法可以对于一些列或者行较小的方阵使用

56.Chips on a Board

题目链接

本题的Trick为对于加操作和异或和的维护。首先可以使用0-1 Trie来维护全局+1全局异或和，具体做法为将所有数按照二进制位从低到高将其插入Trie树，接着对于一次+1操作，将其0,1的儿子交换，然后往当前为0的儿子的边递归，-1操作同理，只不过是往1儿子的边递归，这种做法搭配莫队等暴力数据结构的适用范围会比较大。第二种做法算是一个结论，需要对于每道题具体分析，就是(a+2^i)\oplus (b+2^i)\oplus (c+2^i)在a,b,c\le 2^i时等于(a\oplus b\oplus c)+2^i，于是在有些题目中，可以考虑将加法操作按照从小到大的顺序进行。比如本题，可以利用题目本身的性质和刚刚的结论使用倍增维护

57.Chaotic Merge

题目链接

本题的Trick为对于相同转移的DP方程的处理。在一些题目里面，经常会遇到转移方程相同DP状态，此时如果发现转移仅仅涉及加法或者异或运算时或者两个状态可以同步时，可以考虑尝试将两个状态合并，统一进行转移。比如本题，当确定起点时是好做的，然鹅如果每次去枚举起点复杂度接受不了，又发现所有状态的转移时一样的，并且转移里面仅有加法操作，于是考虑合并状态，对于i,j位置开始的，给f_{i-1,j-1}加上1表示有新状态开始。最后减去空串的影响即可。同时对于一些比较绕的初始化，不好想第0步是什么情况的，可以考虑初始化第一步

58.集合

题目链接

本题的Trick为对于集合相等的判定方法，这个Trick本质上和前面维护状态的Trick是一样的。对于判定集合是否相等的问题，一个常用方法是Hash，将序列摊成数然后搞个set之类的查询。对于有序集合，可以使用多项式形式的Hash，给每一项赋一个x^i的系数。对于无序集合，可以考虑等权求和相关的，比如说把Hash函数设成f(S)=\sum\limits_{i\in S} i^k之类的，又或者是f(S)=\sum\limits_{i\in S} k^i，实际使用可以视情况而定

59.Not Argmax

题目链接

本题的Trick为排列中区间最值相关计数的处理。在一些排列计数题目中，条件可能会与区间最值有关，此时可以考虑本Trick。注意到最值有这样一个性质，对于一整个区间，其最值有且仅有一个，并且该最值将区间划分成了\le2个子区间，对于每个子区间，又可以重复以上过程。此为区间最值的分治结构，整个结构构成一棵树，在设计计数算法的时候可以考虑从整个分治结构上面设计区间DP或者线性DP，又或者是对于笛卡尔树设计树形DP，具体视题目而定。同时，感觉区间DP和树形DP可以和分治结构进行融合，在发现题目有分治结构时优先考虑这两种DP

60.Algebra Flash

题目链接

本题的Trick为meet-in-the-middle算法的使用场景及思考方式。首先，使用meet-in-the-middle需要满足过程可逆，此算法如果作为正解存在，则题目数据范围一般满足O(f(n))无法过而O(f(n/2))可过，比如n=40。通常情况下，思考该算法的时候可以先去考虑找到把哪个维度折半，然后对于两部分的所有状态分开计算答案，最后再拼凑。值得一提的是拼凑的技巧，首先考虑遍历一个半边的状态，对于状态i，假设另外一边可行的状态构成集合S，找到对于集合S的答案即可，于是可以将问题转化为在可以接受的时间内找到一个状态集合的答案，这一步需要结合题目思考，通常集合满足一些包含关系，可以根据这个点设计递推结构

61.旅行者&& 10/1 T4

题目链接1

题目链接2

这两题的Trick为对于网格结构上DP或最短路的处理。对于网格结构上的全局DP计数，前面提到过使用合并状态的方法。对于需要询问网格上对于任意两个点进行DP的答案或者求出这两个点的最短路这样的问题，可以考虑采用分治算法。首先题目需要保证n\times m的范围不会过大，对于分治算法的过程，首先把当前网格由较长边的中点切开分成两部分，对于当前询问集合，枚举切开的中线上的点，求出这些询问求出钦定他们必须走这些点时的答案，接着对于在一侧的询问，递归求解

同时第二题还有偏向一个思维方式的东西，就是对于二维状态的DP可以将其视为网格结构或者网格图进行思考处理

62.种树

题目链接

本题的Trick为对于有时间限制的扩展问题的处理。在某些题目中，可能会涉及到在规定时间限制内扩展到某个点，询问是否存在或者给出构造的方案。此时可以考虑一个DP+贪心，假设f_i表示第i个点必须被扩展到的时间，找到求解f的方法，通常来说为\min\limits_{j\in arrive} t_j-dis_{i,j}，接着由f从小到大排序，即求出最优顺序。这个做法核心思想在于将所有会被i的扩展时间影响到的点都计入了贡献，这样局部最优就变成了全局最优。这个做法的思想还可以扩展到其他题目里面，将能被i影响到的点的贡献全部计入i的贡献，再在这个基础上贪心。需要注意的是f并不需要计算的特别精确，f只需要支持找到一个最优策略即可

63.Uplifting Excursion

题目链接

本题的Trick为使用贪心缩小DP/暴力范围。本Trick的适用范围为对于值域较小该问题，可以使用暴力或者DP求解的问题，同时原问题的值域非常大，对于这类问题，可以尝试本Trick。这个Trick的核心思想在于先找到最优解一个大体的结构，接着在这个结构上进行微调，第一步的手段通常可以为贪心，或者推一些结论，第二步通过DP或直接暴力进行较为精确的求解。以本题为例，先通过贪心找到一个次优解，使得当前的重量在[l-m,l+m]之间，接着在此基础上进行微调，由于最优情况下只会增删不超过m次，于是整个过程中值域最大为[l-m-m^2,l+m^2+m]，DP即可。对于这种值域较大但是又逃不开对于值域朴素DP的题目，要去想办法将值域缩减为poly(V)，可以通过本Trick或者通过删去一些到不了的状态来优化。还有一个对于值域极大然而单个物品体积较小的背包问题的贪心方法，就是在这种情况下可以直接按照V/val排序，因为此时V对于整体选择的影响较小，这样贪心有较大几率正确，或者可以这样选择后再用DP进行微调

本Trick还折射出对于题目的一种思考方式，就是先思考题目的弱化版，通过将一些条件强化或者限制弱化的方式，比如将恰好换成不超过，将小于换成包含，先解决这些问题，在思考当前子问题如何转化为原问题

64.贪吃蛇/蚯蚓/合并果子(加强版)

题目链接1

题目链接2

题目链接3

这三道题目的Trick为使用队列维护有序结构。在一些题目中，会涉及到取出最值，进行一些操作后再插回去的操作，此时可以直接使用set或者priority_queue进行处理，这样做是O(n\log n)的，然鹅题目如果卡\log n，这样的做法就会较劣。此时，如果发现取出的数进行操作后具有单调性，即每次取出的最值进行操作后得到的值单增或者单减，且保证初始序列有序的情况下，就可以采用两个队列的做法，第一个队列维护初始的序列，第二个序列维护操作后的序列，由于单调性，这两个序列都是有序的，于是每次取出的队首为最值，插入在队尾即可。这个Trick还携带一种做题的思想，就是通过找到题目中的单调性来优化复杂度，对于一些常规优化手段不好用的情况，找到题目自身的单调性是一种不错的选择，至于发现单调性的做法，可以推式子，但是对于较为复杂的题目可以考虑打表

65.金字塔/10.17 T4

题目链接1

题目链接2

题目链接3

这两题的Trick为方案数DP的去重。如果DP计数题中涉及到求本质不同的方案数或者是状态间会有重复的情况，可以考虑使用钦定条件的方法来防止重复。以较为常见的区间DP去重为例，第一题设f_{l,r}表示[l,r]内建树的方案数，然鹅如果直接转移会重复，因为两段区间的子树对应的子树个数不一定，如果两段区间都有多棵子树就会重复，于是考虑钦定第一段区间是完整的一棵树，然后转移就不会重复了。第二题同理，直接钦定第一段是一整段括号序列即可。至于第三题，是状压DP的去重方法，每次枚举子集的时候要求子集必须有当前集合内最大点即可。总的来说，DP的去重方法主要还是靠钦定当前选出的集合或者段是包含(左/右)(最值/端点)的第一段

66.基因工程

题目链接

本题的Trick为使用bitset计算两个值域较小的序列的差异数。在一些题目中，会涉及到快速计算两个序列的差异数，此时若直接暴力计算，时间消耗较大，这时候可以考虑本Trick。可以考虑对于每个值维护一个bitset，若值a[j]=i，则将bs[i][j]设为1，最后枚举值计算差异数最后除以2即可

67.基因工程&&Kazaee

题目链接1

题目链接2

这两题的Trick为判定是否集合内所有元素都满足性质I。在一些题目中，会涉及到在较低复杂度内判定是否集合内所有元素都满足性质I，若并没有什么太好的处理方法，同时性质I满足一个必要性的前缀性质，可以考虑本Trick。本Trick的核心思想在于使用一个正确率较低的做法多进行几次，变成一个正确率极高的算法。首先先随机打乱几次集合，打乱后维护广义前缀和，对于一次询问，随即找若干位置查看前缀和是否满足性质I，多进行几次，正确率会很高，如果怕正确率不够高还可以随机赋权

对于第二题，还有一个Trick为对于全局值出现个数满足性质I的处理。当发现值的出现个数很难处理时，可以考虑将所有值随机映射到一个数上，然后维护区间和处理，这样可以得到\sum\limits b_i cnt_i，然后查看sum是否满足性质I即可，这样多做几次

68.管道取珠

题目链接

本题的Trick为利用问题答案贡献的实际意义简化问题。在一些题目中，常常会涉及到求解方案数，然鹅最后答案并不是方案数的简单求和，而可能是每种方案包含的方案数的平方或者是立方求和，此时如果采用常规方法维护的话会较为复杂，此时可以考虑先利用答案贡献的意义转化问题。比如本题，每种方案数的平方和可以转化为"在所有的操作序列中选择两个使得最后序列相同的方案数"，于是可以简单的在此问题的基础上设计DP即可。积累一些转化的方向:

69.2024 11/15 T2

题目链接

本题的Trick为对于背包问题重量单调性的维护。对于一些背包问题，如果考虑维护单调性可能可以使得问题的复杂度下降。背包中维护单调性的方法主要有3种，第一种就是单开一维直接维护，这样做比较直接，但是时空复杂度会较高。第二种是费用提前计算，考虑将重量序列转成重量序列的差分序列，每次记录当前重量变化对于全局的影响，缺点是无法得知当前的重量。第三种是通过限制以后的操作都必须合法，这样做复杂度是基于调和级数的，因此需要保证重量较小的物品不会有很多

70.白雪皑皑

题目链接

本题的Trick为静态的区间推平/取max操作的处理。对于一些题目中的区间推平/取\max，要求每次操作均摊是O(1)的，此时如果使用常规的线段树打tag进行维护就太慢了，此时可以考虑使用并查集来进行维护。首先静态取\max操作可以通过排序转换为区间推平操作，所以以下只考虑区间推平操作。考虑将问题倒着来做，转化为每次在一个区间内将所有没有染色的位置染色，这样只要能够快速的找到没有染色的位置就是均摊O(1)的。接着考虑对于i，如果i未被染色了，就连一条边向自己，否则向下一个位置连边，对于一次操作，从l开始一直跳到当前的段尾，改变段尾的状态，然后再往后跳

71.2024 11/21 T3

题目链接

本题的Trick为树上路径的批量容斥。对于要钦定系列路径都不能选/都可以选的问题，比如钦定两个子树内组成的路径不能选，如果仅仅使用常规树上处理技巧会特别难做，此时可以考虑本Trick。以子树为例，先处理出每个点的dfn序，对于一条路径(u,v)，在二维平面上设点(dfn_u,dfn_v)，对于钦定i,j子树组成的路径不选，就是点(u,v),u\in [dfn_i,dfn_i+siz_i-1],v\in [dfn_j+siz_j-1]不选，不难发现不能选的区域构成一个矩形，所以最后不能选的部分构成矩形的面积并，跑扫描线即可。事实上对于所有可以摊成连续段的路径容斥，都可以尝试本Trick