常见 trick 总结

· · 个人记录

1. 前言

我随机选取了一些我做过的绿、蓝、紫、黑题，总结出了一些 trick。

2. 正文

2.1 剪枝

2.1.0 介绍

剪枝一般用于搜索当中，可能是因为其作用相当于“剪去”搜索树上的枝条而得名。

剪枝使用得当，可以大大加快搜索的速度，有时甚至能达到出乎意料的结果。

2.1.1 剪去不合法状态

如标题，当一个状态不合法的时候，直接放弃搜索这个状态以及它的所有后继状态。

当然，这个方法仅适用于这个不合法的状态的所有后继状态都不合法的情况，正确性显然。

这个技巧给我留下的印象十分深刻，因为我前几天做题时，有一个数据点在我剪枝后，时间从超时变成了 70 ms。

剪枝前：

剪枝后：

推荐题目： P1763 埃及分数

2.1.2 记忆化

记忆化，就是将已经得到过的状态的信息存储起来，防止每次重复搜索，浪费大量时间。

最简单的记忆化思想可以体现在递归写法的快速幂上：

typedef long long ll;
ll fastpow(ll base,ll k){
    if(k==1)return base;
    ll num=fastpow(base,k/2);
    return num*num*(k%2?base:1);
}

注意，我们这里使用了一个 num 变量将已经计算了的幂值存下来，然后自乘。

问题来了，为什么不使用下面的写法呢？

typedef long long ll;
ll fastpow(ll base,ll k){
    if(k==1)return base;
    return fastpow(base,k/2)*fastpow(base,k/2)*(k%2?base:1);
}

让我们仔细分析一下这个写法的复杂度：搜索树每增加一层，层结点数翻倍，而一共有 \log n 层，因此不难得到这样写法的时间复杂度为 \mathcal{O}(n)。

而若是记忆化了之后，每层节点数不变，因此总复杂度为 \mathcal{O}(\log n)。

有多少人初赛被坑了？

记忆化的具体体现：

以下举两个例子：数位 DP 和杜教筛。

数位 DP：

数位 DP 的状态设计一般都比较复杂，因此大部分人会使用记忆化搜索。

以 P2657 [SCOI2009] windy 数 为例，给出数位 DP 的记忆化搜索写法：

typedef long long ll;
ll a,b,dp[20][20][2],numb[20];
void init(){memset(dp,-1,sizeof(dp));}
ll dfs(ll k,ll num,bool mx,bool zero){
    ll r=0;
    if(!k)return 1;
    if(!mx and ~dp[k][num][zero])return dp[k][num][zero];
    ll maxn=mx?numb[k]:9;
    for(int i=0;i<=maxn;i++){
        if(abs(i-num)<2 and !zero)continue;
        r+=dfs(k-1,i,mx and i==maxn,zero and i==0);
    }
    if(!mx)dp[k][num][zero]=r;
    return r;
}

发现，如果待搜索的状态已经被搜索过了，就不再继续搜索，直接返回结果。而在搜索到了一个新状态之后，记录搜索的结果。

这样，便可以保证总搜索次数小于等于状态数（也就是你 DP 数组的大小）。

推荐题目：好多数位 DP 题呢。

杜教筛：

不会杜教筛也没事，直接看核心代码：

typedef long long ll;
ll get_epsilonsum(ll n){return 1ll;}
map<ll,ll> mumem;
ll get_musum(ll n){
    if(n<(ll)MAXN)return mu[n];
    if(mumem[n])return mumem[n];
    ll r=get_epsilonsum(n);
    for(ll x=2,y;x<=n;x=y+1){
        y=n/(n/x);
        r-=(y-x+1ll)*get_musum(n/x);
    }
    return mumem[n]=r;
}

发现，这里使用了一个 map 来记忆化，不惜使用 \mathcal{O}(\log n) 复杂度的容器，也要记忆化，这足以体现记忆化的好处，也说明了记忆化即使是在这种复杂算法上也有妙用。

推荐题目：杜教筛的例题还有推荐的必要吗（恼。

2.2 状态压缩

2.2.0 介绍

状态压缩，即用某种东西将不同状态压缩起来，达到更易存储或更易计算的效果。

状态压缩使用得当，可以使很复杂的代码简单化，提高代码可读性，且能让思路更为清晰。

2.2.1 例题

2.2.1.0 前言

状压方法各有千秋，但最多的是使用二进制位存储信息。

2.2.1.1 状压优化 DP——以互不侵犯为例

P1896 [SCOI2005] 互不侵犯

相信大多数人的状压 DP 都是从这道题开始的。

题目要求在棋盘上放上国王，使得两两不能将军。

最基础的状压思想是：用 1 表示一个位置放置了国王，0 表示一个位置没有放置国王，用二进制数存储棋盘信息。

这样，就可以很方便地找出每一行的合法放置方案。

那么如何判断行与行之间是否合法呢？

很容易想到，只有两个国王在各自行的位置相同或是相差一位时，才不合法。于是想到使用二进制数的左右移运算，以及按位与运算，便很容易判断两行是否合法。

多么便利。

2.2.1.2 状压配合暴力——以枚举子集为例

很多题目的暴力分中，都会留出枚举子集的分数。

不过使用递归显然不够方便，不妨使用状压。

二进制每一位存储是否选出该位对应的元素，1 为是，0 为否。这样每一个二进制数都对应了一种子集。

------------ #### 2.2.1.3 状压配合线段树——以公主の#19准备月考为例 [P4256 公主の#19准备月考](https://www.luogu.com.cn/problem/P4256) 很久以前做到的一道相当哇塞的题目，我愿称之为神题。 题目要求我们维护区间每一个数的质因数以及质因数个数，而且是带修的。 对题目观察后，发现值域是 $[1,100]$ 的。 于是开始动“歪脑筋”：因为这个数比较小，所以考虑使用状压存储每个数的质因数。 但是还要存储个数，而每个二进制位只能存储 0/1，怎么办？ 很简单，多用几个位就行了。 计算一下各质数需要用几个二进制位存储： $2$：$2^{6}\le 100\le 2^{7}$，因此 $2$ 需要用 $3$ 个二进制位存储。 $3$：$3^{4}\le 100\le 3^{5}$，因此 $3$ 需要用 $3$ 个二进制位存储。 $5$：$5^{2}\le 100\le 5^{3}$，因此 $5$ 需要用 $2$ 个二进制位存储。 $7$：$7^{2}\le 100\le 7^{3}$，因此 $7$ 需要用 $2$ 个二进制位存储。 $11$：$11^{1}\le 100\le 11^{2}$，因此 $11$ 需要 $1$ 个二进制位存储。 事实上，$11\sim 97$ 中的总共 21 个质数都只需要 $1$ 个二进制位。 计算一下总共需要多少二进制位： $3+3+2+2+21=31 神奇吧！ ------------ ### 2.2.2 尾言 有一些其他状压技巧并未详细指出，如状压轮廓线这种，请读者自行了解。 ------------ ## 2.3 二分答案 ### 2.3.0 介绍 二分答案通过不断地对当前答案可能存在的范围的中心点判断可行性，达到缩小答案所在范围、确定答案的目的。 其实二分答案只是将普通的枚举改为了更加快速的二分，正是由于这一项改变，才能将原本枚举的复杂度中的 $\mathcal{O}(n)$ 改为 $\mathcal{O}(\log n)$。 不过二分答案是有局限性的，那就是所求必须单调。 不过有时我们可以通过寻找隐藏在题目中的单调信息来二分——即使求出来的并不直接是答案。 ------------ ### 2.3.1 例题 #### 2.3.1.0 前言 普通二分答案板子这里不讲，请见谅。 ------------ #### 2.3.1.1 二分答案搭配字符串——以 DVAPUT 为例 [P6456 [COCI2006-2007#5] DVAPUT](https://www.luogu.com.cn/problem/P6456) 题目要求我们求出一个最长的子串，使得这个子串在总串中至少出现了两次。 容易发现，如果一个子串在总串中至少出现了两次，那么这个子串的子串也至少出现了两次。 因此，我们所求的长度是单调的，可以使用二分。 具体地，每次二分长度，然后判断这个长度是否合法，对于字符串的检测，用哈希即可。 二分加哈希——字符串题的终极秘诀。 ------------ #### 2.3.1.2 三分法——以宅男计划为例 [P4040 [AHOI2014/JSOI2014] 宅男计划 ](https://www.luogu.com.cn/problem/P4040) 有时候，有一些题目的答案并不是单调的，但却是单峰的。对于单峰的答案，可以使用与二分法相似的三分法。 宅男计划就是这样的题，出去购买的次数和能够宅的天数并不是单调的，而是单峰的，为了找到这个峰值，我们需要每次找到峰值可能存在范围的两个三等分点，答案会更偏向更高的三等分点。根据更高的三等分点更新峰值范围。 具体做法详见下面代码： ```cpp ll l=1,r=w;//初始峰值可能存在的范围 while(l<r){ ll lmid,rmid;//两个三等分点 lmid=l+(r-l+1)/3; rmid=r-(r-l+1)/3; if(check(lmid)>check(rmid))r=rmid-1;//如果左边比右边优,则降低右边界 else l=lmid+1;//如果右边比左边优,则升高左边界 } ans=max(check(l),check(r));//二者取最大 ``` 单谷同理。 ------------ #### 2.3.1.3 实数二分 这个世界上有一种东西叫作实数二分。 不过既然是实数，就会存在精度问题，那么如何在进行实数二分时避免精度问题呢？ ~~答案是用分数。~~ 答案确实是用分数，但不是一般的分数。 今天中午（笔者写这段话的这天）某 HN Ag 牌突袭机房，给我介绍了一个分数二分的方法。 对于两分数 $\displaystyle\frac{a}{b}$ 和 $\displaystyle\frac{c}{d}$，满足不等式： $\displaystyle\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}

因此，在二分的时候，可以直接取 \displaystyle\frac{a+c}{b+d} 为中心点，有效避免了乘除运算，非常快速。

而且这种写法还有一个好处在于：你可以将下界设为 \displaystyle\frac{0}{1} 作为 0，上界设为 \displaystyle\frac{1}{0} 作为 \infty，这是实数二分和整数二分都做不到的。

2.3.2 尾言

其实不管是单调还是单峰，都可以使用一个很哇塞的算法来做——模拟退火。

事实上，就算不是单峰，而是多峰，都可以。

不过本博客不准备讲模拟退火，因为这是 LZMkingNB 的绝活，建议让他讲。

2.4 随机化

2.4.0 介绍

随机化并不是一种算法，而是很多种算法。

不过同前文所讲，不准备讲模拟退火，当然遗传算法也不会讲（主要是不会）。

言归正传。

随机化算法都有一个共同的特点——不保证能完全正确，但是有一定的正确率。不过只要有正确率就够了，因为我们完全可以多跑几遍来提高正确率。

当你想不出正解时，随机化算法往往能发挥奇效。

2.4.1 例题

2.4.1.0 前言

字符串哈希不讲。

2.4.1.1 和哈希——以星战为例

进行接下来的讲解前，需要作出一些约定：

P8819 [CSP-S 2022] 星战

相当熟悉的题目了，就是去年考过的原题。

题目简化后发现，就是给出一些删边加边的操作，让我们判断当前图是否满足下面的条件：

  1. 所有点的出度为 1。

  2. 从任意一个点出发，都可以走到一个环里面去。

仔细分析之后发现这种情况很难出现，因此直接输出 NO。

仔细分析之后发现，只要满足了条件 1，条件 2 就自动满足了。这是个好消息，意味着我们只需要判断所有点的出度是否为 1。

不难发现，对于一个图 G=(V,E)，当所有点的出度为 1 时，满足：

\displaystyle\sum_{v\in V}d^{+}(v)=|G|

那么能否通过这一点判断图是否满足要求呢？

发现：\forall v\in V,d^{+}(v)=1 是 \displaystyle\sum_{v\in V}d^{+}(v)=|G| 的充分条件。因此，后者为前者的必要条件，且并不充分，无法作为判断图是否满足要求的依据。

既然没有充分性，不妨就让它尽量有充分性。

考虑为每个点赋一个随机权值 val_{i}，在计算时，每有一条出边，就加上这个点的权值，这样可以得出 \forall v\in V,d^{+}(v)=1 的另一个必要条件：

\displaystyle\sum_{v\in V}d^{+}(v)\cdot val_{v}=\sum_{v\in V}val_{v}

观察发现，第一个必要条件即为所有 val_{i} 都为 1 时的第二个必要条件的特殊情况。

既然第一个必要条件不充分，那么第二个充分吗？

发现这个式子的解与 val_{i} 的值强相关，而 val_{i} 的值是我们随机赋的，因此这个式子有很大概率充分。

既然有很大概率充分，那不妨就将其当成充分条件使用。

这个式子不管是左边还是右边都非常好维护，甚至不需要建图。

2.4.1.2 摩尔投票——以 Destiny 为例

摩尔投票指的是这一类问题：

有一群政客，它们在竞选某种职位，只有某个政客的选票数大于所有政客的选票数的一半时，那个政客才能当选。

给出每个选民支持的政客，要求找出是否有政客能够当选，如果有，输出是哪个政客。

摩尔投票问题有专门的摩尔投票法解决，不过既然这一节讲的是随机化，那么自然要用随机化解决。

考虑以下的过程：

如果有某个数字出现的次数大于一半，那么随机从这堆数字中抽出一个数字，抽到目标数字的概率大于 1/2。

于是考虑先统计出所有数字出现的次数，然后随机抽取一个数字检验其是否为答案——若是，直接输出；反之继续。重复上述过程 100 次。

由于一次检测到答案的概率大于 1/2，因此重复 100 次还检测不到答案的概率很小很小，大概是 0.00...1 中间跟着 30 个 0 吧。

这个时候有人要说了：你都把数字出现的次数统计出来了，为什么不直接输出答案呢？

这个别管，你就说是不是 \mathcal{O}(n) 的吧。

CF840D Destiny

来看这道题，是摩尔投票的变式，只不过是加了一个区间查询而已。

和上面描述过的做法一致，随机抽取区间内的数字，然后判断是否是答案，跑 100 遍，取最小，出错概率小于 0.00...1 中间夹 10 个 0。

至于如何统计区间内数字出现个数：可以将询问离线下来排个序，然后慢慢加。

这样，一道主席树紫题就被轻松解决了。

2.4.1.3 随机染色——以 Tourism 和假期计划为例

CF1310D Tourism

先考虑一下不要求没有奇环的做法：是不是 DP 就行了？设 f_{i,j} 为走了 i 条边，停在 j 节点的最短距离即可。

那要是有奇环怎么办呢？

很不容易想到一个性质：二分图上没有奇环。

基于这个性质，我们可以强制将图变成二分图——具体地，考虑给每一个节点随机染上黑/白两色，然后把两端点颜色相同的边删掉，这样剩下的图就是一个二分图了，在这个图上跑 DP 就不需要考虑奇环的问题了。

既然是随机染色，所以不妨多跑几遍。发现 K\le 10，所以随机到 K 个节点黑白交替的概率为 2/1024，也就是说随机 350 次出不了正确答案的概率大概为 1/2，随机 3500 次出错的概率为 1/1000。如果实在觉得出错概率太大，不妨再多跑几遍。

P8817 [CSP-S 2022] 假期计划

这道题的正解是枚举中间两个节点，不过我们依然可以随机染色。

具体地，先给图上能够在 k 步内到达的点互相连边，构成一张新图。

然后给新图上的节点随机染上四种颜色 A,B,C,D（1 号点不染），从 1 号点开始，强制要求按照以下路线走：1\to A\to B\to C\to D\to 1。

每次有 2/4^{4} 的概率出正确答案，随机 88 次出错的概率为 1/2，随机 888 次出错的概率小于 1/1000。

2.4.2 尾言

像上面介绍的需要跑多次的随机化算法，可以配合卡时食用，效果更佳。

2.5 枚举

2.5.0 介绍

这里的枚举并不是指暴力枚举，而是在一道题目中变量很多的时候，考虑枚举其中某些变量，把那些变量当作常量求解，往往可以使问题更加简单。

2.5.1 枚举——以假期计划为例

又是假期计划。

P8817 [CSP-S 2022] 假期计划

刚刚介绍了这个题目的随机化做法，那么这一节介绍其正解。

发现一条路线中涉及四个节点，实在是太多了，不妨考虑枚举中间的两个节点，然后求解。

发现枚举中间的两个节点后，问题转变为了求出另外两个节点，既可以到 1 节点，又可以到中间的节点。那么问题一下就变得非常简单了，直接计算出能够到达中间两个节点并且能够到达 1 节点的所有节点中权值最大的几个，然后更新答案即可。

具体有一些实现细节这里不提。

2.5.2 尾言

对于一个题目，只要确定了枚举哪个变量，接下来的步骤就会非常简单了，非常好用。

比赛中这个方法的瓶颈往往在于你想不到，而不是你写不出。

2.6 根号

2.6.0 介绍

莫笑分块没头脑，要说好处真不少。

又好写啊又好调，代码简单常数小。

对数方法真难找，考虑根号没烦恼。

管他淀粉线段树，直接分块就没了。

根号算法——优雅的暴力

2.6.1 例题

2.6.1.0 前言

不讲分块和莫队，一是没怎么写过，不太熟练；二是这是 mori_ 的绝活，要讲让他讲吧。

2.6.1.1 块状链表——以书架为例

块状链表的具体介绍可以见我写的 这篇博客。

P2596 [ZJOI2006] 书架

一道平衡树的题目，我为这个题目写了一篇题解，所以就不在这里赘述方法了。

题解通道

顺带一提，这道题目我用块状链表的提交记录如下：

一个同学用平衡树的提交记录如下：

这就是小常数的魅力。

2.6.1.2 数据分治

一个题目，你想不出正解，但是你有两种暴力做法：一种的复杂度为 \mathcal{O}(n\cdot k)，另一种的复杂度为 \displaystyle\mathcal{O}(\frac{n^{2}}{k})，这个时候你怎么办？

我在一万年前的一次考试中遇到了这种情况，当时我比较蠢，没有想出正解，只想出了复杂度如上述的两个暴力。

但是我当时又比较聪明，我想到——如果在 k\le\sqrt{n} 的时候，跑复杂度为 \mathcal{O}(n\cdot k) 的算法；而在 k\ge \sqrt{n} 的时候，跑复杂度为 \displaystyle\mathcal{O}(\frac{n^{2}}{k}) 的算法，那么我的程序的复杂度不就是 \mathcal{O}(n\cdot\sqrt{n}) 了吗？

于是我靠着两个暴力过了那道题。。。

这就是数据分治。

2.6.2 尾言

其实根号算法主打的是一个均摊思想，只要熟练运用了，所有根号算法都不难理解。

2.7 打表

2.7.0 介绍

如果说上一节是教你暴力出奇迹，那么这一节教你打表拿省一。

好吧不一定能拿省一，但一定能教你怎么打表。

2.7.1 例题

2.7.1.0 前言

普通打表……真的还用教吗？直接写个爆搜然后挂后台挂四个小时即可。

不过 €€£ 有代码长度小于 100 k 的限制，因此如果表太长了照样会超时。

这个时候，允许我介绍——分块打表。

2.7.1.1 分块打表——以数 7 为例

P1662 数7

看上去是一个朴实无华的模拟，但是一看数据范围——X\le 10^{9}。

这下没办法模拟了，对吧，毕竟这样的数据范围一看就是故意卡模拟。

不过我们一身反骨，出题人不想让我们写模拟，我们就偏要写模拟。

想想，模拟就好比跑步，一次性跑到目的地肯定累死，而我要是在路线中放上很多传送点，每次跑步先传送到距离目的地最近的传送点，再开始跑，不就轻松多了吗？

模拟也是一样，我们不把所有位置的表都打出来，而是只打“传送点”的表，然后每次模拟从距离目标位置最近的“传送点”开始模拟。

只需要每隔 \sqrt{n} 的位置打一次表，就可以做到 \mathcal{O}(\sqrt{n}) 的复杂度，相当地哇塞。

如果空间是在比较紧张，也可以适当调整一下块长，不一定要 \sqrt{n}。

这种方法也可以看作一种以空间换时间。

3. 尾言

到这里，我总结的所有 trick 都已经讲完了，可能还有一些遗漏，不过我记不起来了。

在考场上，如果能够用到这些 trick，一定可以给你带来莫大的好处。

祝各位神犇 AK NOIP。