下面是近期我见识到的一些新套路/oh
-
P1640 [SCOI2010] 连续攻击游戏 考虑值域是很小的，并且编号向权值连边不好做，那么直接正难则反！权值向编号连边，从权值 \(1\) 开始最大匹配，直到有一个权值无法到达。如果直接最大流 \(O(nE) = 1e4 \times 1e6\) 可能复杂度有点假，不过网络流一般是跑不满的，能过！注意清零的时候不能用 memset ，常数略大。
-
CF940F Machine Learning 这种求区间数出现的次数的问题有一个巧妙的性质：\(\sum_{i = 1}^{k}i = \frac{k(k+1)}{2} = n\) ,可得知这个答案 \(k\) 是一个 \(\sqrt n\) 级别的，对于莫队这种根号数据结构来说，暴力的复杂度是可以接受的。
-
CF375D Tree and Queries 第一次看我还以为跟上面这个题一样暴力算就行了，可是会出现一个子树内全是一个颜色的情况，我就成神笔了。上面这种 \(\sqrt n\) 级别的意思是不同的区间数出现的次数是 \(\sqrt n\) 级别的，而这个题让你求的是出现次数 \(\ge k\) 的数，不是让你统计不同的次数。这个题 \(O(1)\) 求贡献的办法也比较巧妙：设 \(Cnt_i\) 表示有多少颜色的出现次数 \(\ge i\)。于是代码就好写了。
再者，对于链问题，往往用欧拉序解决问题，因为要消去不在链上的点的贡献；对于子树问题，往往用 dfs 序解决问题，记录下入栈和出栈的时间点，那么这两者之间的都算入贡献。
il void Add(int x)
{
x = a[x];
cnt[x]++;
Cnt[cnt[x]]++;
}
il void Del(int x)
{
x = a[x];
Cnt[cnt[x]]--;
cnt[x]--;
}
-
AcWing208.开关问题 一个异或高斯消元的题，但是做的时候由于对高斯消元理解不清，导致卡了很久。我采用的是高斯-约旦消元，就要凑成对角矩阵。而消 \(0\) 的过程中要加一句
if(a[k][i])后再消，要不然0^1 = 1，白消了。而它左边的都是0 ^ 0 = 0没有影响。 -
P4550 收集邮票 其实做多了就是套路，倒推。不过我想写的是因为这位博主的题解非常细心和通俗易懂，让我豁然开朗。