Trick 2.0

NKOJ P11061 签到题

对于多边形的三角形划分，可以每次对于相邻的三个三角形划分，将中间的点删掉，继续下一次的选点。

[20250701] 求和

对于换转移的状态，如果知道环上总权值，那么就可以用主元法，设一个参数然后解出。

[模拟赛20230824] 龙了个龙

要求出现次数为 \(k\) 的，普通不好做可以用hash。

[PA 2019] Desant

对于总和为 \(n\) 的若干正整数，它们的乘积最大是 \(3^{\frac{n}{3}}\)。

[ABC221G] Jumping sequence

对于所有的数选进两个集合，分别可以选择正负号，使得他们的和分别是 \(A\),\(B\)。

我们将第一个集合的和设为 \(s1\) ，第二个集合的和设为 \(s2\)，要求使得 \(s1+s2=A+B\) ，\(s1-s2=A-B\)。我们可以用背包，分别跑出和为 \(A+B\) 时的方案和和为 \(A-B\) 时的方案，其中两组相同的放入第一个集合，两组不同的放入第二个集合，发现这就是合法的一组选择。

[20250723] 树

树的重点和直径的中点做根都有一定性质。有时候可以将路径问题划分成经过根的和不经过根的。

[20250723] 最后一道

对于将一个点删除，再将与它相连的所有点互相连边的操作。可以将每条边变成一个点，得到一颗圆方树，讲一个点删除就是将它四周的边点合并成一个边点。

Nezzar and Hidden Permutations

一些图论问题正向不好做可以变成补图来思考，例如一个菊花图的补图是一个团和一个孤立点。

Dynamic Shortest Path

对于边权为负的最短路，或是想将边权变小，可以借助势能满足一些条件。

Chests and Keys

hall 定理可以将一些条件转化为匹配问题。

K.4

四点团计数，同样按照度数大小连边，枚举最小点，然后用bitset维护出点之间的连接关系，有出点个数 \(O(\sqrt {2m})\)，总时间复杂度 \(\sum \frac{du_i^3}{\omega}=O(\frac{n^2}{\omega})\) 。

Mędrcy

度数分讨，发现度数 \(\le 2\) 的点可以在最后一步统计，那么每次的决策是将一个点变为决策点，或是将与它相邻的所有点变成决策点。有 \(T(n)=T(n+1)+T(n+3)\)，注意到\(n\le 30\)，时间复杂度是正确的。

[Ynoi Easy Round 2014] 等这场战争结束之后

操作树。对于每次操作有添加和回退到某一个状态的题目。可以对于每次操作建一个节点。其中不是回退操作的话 \(i\) 的父亲为 \(i-1\) ，否则为回退到的那个点。对于每个点，它在树上的祖先就是它存在的操作。那么顺
次遍历整颗树就可以将回退操作变为单步撤销。

团队选拔

对于选取区间类的dp中要求强制某个点的方案可以转化为全部方案-一定不选它的方案，一定不选它的方案是一段前缀和一段后缀。

[20250906] sdkfz

注意到预处理的复杂度为 \(O(n^3)\) ，单次修改的量确只有 \(O(n)\) ,那么最大的减量也不会超过 \(O(nq)\) ，所以预处理量达到阈值时，就可以直接退出了。

[20250910] 小球进洞

在树形dp中，若是允许在同一个点上选多次，也就是第二维很大，有时候只用考虑用到的点，将第二维转化为关于 \(size_u\) 级别的，最后在通过组合数计算。

[20250909] 快速kmp

对于维护一个子集需要两两做贡献时，可以采用分块的形式，分别预处理每个块内部所有子集情况，和不同块所有子集对应的贡献。

[20251007]复生

对于区间 \([l,r]\)，端点为最小或最大值时，例如 \(a_l\) 最小，\(a_r\) 最大时，满足在小根笛卡尔树 \(l\) 是 \(r\) 的祖先，大根笛卡尔树上 \(r\) 是 \(l\) 的祖先。于是一颗转区间限制，另一颗用可持久化线段树就能维护。且按权值大小枚举时，是小根笛卡尔树上的拓扑序。

[20251007]造茧

对于单点贡献为两值之和或之差时，可以考虑在不同的时间点加入，比如转移当前点加第一个值的影响，记录第二个值可以转移的点数，每次考虑当前第二个值加进去的贡献。

[20251011]城镇地图

计数类问题中，\(w^2\) 可以视作 \(w\) 中两两连边的边数。

若记 \(f_u\) 表示满足某条件当前状态的数量，想求平方值可以可以记录状态 \(f_{u,v}\) 表示满足条件的两个状态的个数，这样每两个同一条件的数就会被计数一次。

[Ynoi Easy Round 2022] 虚空处刑 TEST_105

对于线段树每个店维护点集，可以采用 \(vector\) 记录，但若涉及合并或是删除操作就会十分麻烦甚至无法在低复杂度内解决，但如果我们换成链表，就可以很好的解决这个问题。

CF1058D

对于分段贡献最值问题，考虑代价函数，若出现有除法或平均等形式，使得有效区间个数有限，可以预处理所有有效区间，或是在转移时直接枚举代价。

同时，当答案的取值远小于状态时，有时候可以进行转置。

[20251015] 开会

类似中国剩余定理的条件具有可合并性和分组性。

[省选联考 2025] 追忆

老生长谈的技巧了，对一堆类似求 \(max\) 的操作时间复杂度不是 \(\sum\) 而是 \(max\) ，利用这个性质可以进行一些分组以减少时间复杂度。

[20251018]复读机

对于求 \(a_i+a_j\) 的 \(max,min\) 之类的，可以将答案的一半作为关键字。

[Ynoi Easy Round 2015] 此时此刻的光辉

数论除了根号分治还有三次根号分治，感觉不是很常用的说。

[20251021] 最短路

统计方案将每一种状态转化为另一种映射。

将全局条件转化为全局条件。

[ARC101F] Robots and Exits

数轴上点左右移动，若是碰到关键点消失的问题，可以用二维平面表示，横纵坐标分别表示向右的最大值与向左的最大值。