我有独特的骗分技巧

（注意：以下见解为个人观点，如有不足，请多指教。如果对卡常的几个名词$inline,register$等的原理感到疑问，请看其他dalao的博客，本篇博客不赘述。） ## -1 写在前言之前 可能这篇文章初看标题会有一些dalao认为我写的东西很低级（虽然的确挺低级） 但是，我认为也值得浪费您一点时间看一看 相信多多少少也会有一些收获 （如果没有，我深表歉意。） # 0 前言 ### 骗分法宝：打表与暴力。 暴力是NOI系列比赛中极为重要的一环。而打表就更不用说了，是上述两者的补充，虽然耍赖，却能拿分，何乐而不为？本蒟蒻今日把上述两种技巧总结一下，方便各位~~轻松AK~~。 （卡常我就不说了，我就在暴力的时候顺便用一下，优化暴力的时间复杂度就算了） （鉴于本人经验不足，~~太懒了~~没有打过经典的骗分算法——模拟退火，就不讲了，推荐一篇给大家，更多的题目还需要自行百度：[这里](http://ruanx.pw/post/%E8%BF%91%E4%BC%BC%E7%AE%97%E6%B3%95.html)） ~~说到底还不是因为我太弱才会来讲这些~~ 声明：并非所有的知识都为我原创，我会尽量注明出处，如果哪位dalao认为我触犯了您的知识产权，我深表歉意，请在评论或是私信联系我，我会把出处加上。 那咱们就暂时离开恶心人的各种算法，来到骗分的天地吧。 # 1 打表 打表，顾名思义，就是__『获得一个有序表或常量表，来执行程序某一部分，优化时间复杂度』__（摘自度娘），说白了就是先暴力（题目数据较大，题目简单）或手算（题目数据较小，难度较大）出答案，然后放进代码里，直接输出。 __在我看来，打表不只有输出答案，还可以佐以我们的思考，成就一顿~~美味的~~程序。__ 有些人会问：“打表还有什么技巧？不就是什么数据什么输出吗？”不急，来看道题： $\color{Black}{-------------------------------------------}$ [洛谷P1463 POI2002,HAOI2007 反素数](https://www.luogu.org/problemnew/show/P1463) 这道题可谓是经典的打表题（个人觉得搜索简单些），但是也不能无脑直接『打出答案』，比如我一开始的打表思路就是如下的伪代码： ```cpp int a[2e9],b[2e9],maxn=0,l; bool sign; for i = 1...n 计算i约数个数，存放到a数组; if(a[i]>=maxn)maxn=a[i],l=i; print maxn; ``` 这样可以得到一整个答案表。 但暂且不谈空间大小问题，单算算输出时间复杂度就够了。 输出$2e9$个数，再假设计算机运算速度为$1e9/s$，输出速度为$2000B/s$（很难做到），那最少也要输出$1000000s$，约为11天，赛场上怎么可能呢？ 所以还是要优化一些。不难看出，速度瓶颈主要在输出上，于是可以上筛表，同时反素数个数实际上很少，不用全部输出对应答案，只要输出所有反素数即可。经~~非~~精确枚举，$2e9$下的反素数共有69个。 时间太长时可能打不完，但是一般来讲这就可以了，因为暴力的时间平均也就比正解多几个$O(n)$（呸），一般来讲可以承受。 $\color{Black}{-------------------------------------------}$ ### 但是，这就是打表的唯一用途了吗？再来！ ## 1、获得正解 很多时候数据的种数很多，不可能全部打完，单纯的打表就不能满足我们的要求了。这个时候，__打表可以帮助我们获得正解。__ 如《训练指南》P137，[LA5059（UVA1482）](https://www.luogu.org/problemnew/show/UVA1482)，这道题是个典型SG函数应用，汝佳大神就是先写了个递推程序，观察了SG函数的特点，得到$n$为偶数时$SG(n)=n/2$，$n$为奇数时$SG(n)=SG(n/2)$，最后结合SG定理得出了正确的结果。 __所以说明，打表不仅仅是直接输出答案，也可以找到数据与答案的联系，甚至推导正解。__ $\color{Black}{-------------------------------------------}$ ## 2、分段打表 如CSDN中的某位大神（似乎不止一位）所言： >遇到不会的题一定要想想能不能打表，运气好都能满分。 虽然本非酋表示不信但是就是觉得好霸气好有道理$QAQ$。 遇到我们上面说反素数的问题，如果打不完怎么办？当然不能坐以待毙，肯定要奋起反击！ 对于比较容易递推（可递推且依赖状态较少）的情况，我们可以请出打表的升级版：__分段打表__。 比如说，假设范围是2e9，答案种数又不如反素数那么少，那就只能让计算机算了，这时就可以以5e6为一块，打出BLOCK_SIZE（没错就是它）$\times k(k\in N)$时所对应的答案，然后零碎的部分靠暴力递推。 （可以看看[这里](https://blog.csdn.net/jiangyuze831/article/details/41551981)，相信会对分段打表有一个更清晰的认识） 有人可能会说，这不是分块的思想么？事实上我觉得，分块和分段打表都是同源的，把大的任务打散成块，只是分块稍微“优雅”一些而已。 块大小的问题吗……在__可打出来的时间内尽可能把块变小__，降低分段暴力的时间复杂度，这样最后拿高分的概率更大。 分段打表还可以用来算许多计数问题（包括组合数等）的答案。 $\color{Black}{-------------------------------------------}$ ## 3、借助网站/自己手算 许多计数问题可以把小数据的答案打出来，得到一个基础数列，然后可以放进[这个神奇的网站](http://oeis.org) 你没看错这清奇的画风，就是它：  它可以干嘛呢？ 你可以试着点一下$Search$，比如说对于我们界面上的这个：（很遗憾它不是主页的页面只支持英文，所以要么靠翻译要么靠自己）  $\color{Gold}\colorbox{White}{黄色的框框}$是显示有多少个结果（可以搜"1,2,3,6,10,15"试试） 所有$\color{Blue}\colorbox{White}{蓝色的框框}$会显示它是如何构造出来的（即组合意义），这里说的是“$F_n$指$n$个无区别节点构造出的树的个数”。 或者，如果您知道数列的序号，也可以输入数列序号。（比如$A000001$） 下面的几行会显示原数列，加粗的是搜索的内容。 再往下拉会有几行不是很显眼的小字：  意思是说: $Formula$（公式）：$G.f.$（$Generating$ $Function$，生成函数）：$A(x)=1+T(x)-\frac{T^2(x)}{2}+\frac{T(x^2)}{2}$，$T(x)$是$A000081$（$n$个节点构成有根树的个数）的生成函数。 $Example$（例子）：（用独特的方式把树的样子画了出来） 上面那个正是我们需要的（可以打正解），下面那个则可以帮助我们理解。 ### 多讲一句：有没有觉得$A000001$非常熟悉？做过$CF$愚人节题目的$2k$多人应该都知道，愚人节题目$CF409F$的标题就是$000001$，指的就是$OEIS$里的$A000001$，题目是要求输出该数列的第$n$项。（可见对于这些网站掌握程度的重要性） 其它是链接啦，出处啦之类的，大家有兴趣可以自己看看，我不多讲了。 有什么用？当然是可以打表了！要不然就是转化为一个较简单的组合模型，要不然就是直接或间接得到递推式或是多项式，再要不然……直接复制打表，如果不会我也帮不了您。除开这些，这也是平时了解组合数学和验证自己答案的好去处。 $\color{Grey}{-------------------------------------------}$ 或者说，想要锻炼或是比赛场上，得靠自己手算，人脑找规律，就可以有如下几种方法： 1、神犇型：直接观察 2、大佬型：凭经验 3、我型：借助纸笔好好算算 然后看看，能否线性递推，或是有直接多项式（每项相互独立）可以表示，再比如有没有与组合数相关的规律，再用对应的算法验证。或者也可以看看是否是积性函数。 什么？您问我积性函数是什么？ 数论中，就是__对于正整数$n$的一个算术函数$f(n)$，在$f(1)=1,gcd(a,b)=1$时满足$f(ab)=f(a)f(b)$的函数__，其中对于$a,b$不互质情况也成立的叫做__完全积性函数__。比如常见的欧拉函数，莫比乌斯函数等都是积性函数，单位函数$f(n)=n$等是完全积性函数。 想了解更多？看[这里](https://www.cnblogs.com/wfj2048/p/6537861.html) 积性函数有一个有趣而有用的性质： ### 若$n=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k} (a_i\in N+,p_i$为质数$)$，且$f(x)$为积性函数（不必是完全积性的），则满足： $f(n)=f(p_1^{a_1})f(p_2^{a_2})f(p_3^{a_3})...f(p_k^{a_k})$ 如果是积性函数怎么用？这就容易得多了，可以直接快速递推，~~麻麻再也不用担心我会超时啦~~。这样，可以只关注$f(p_i^{a_i})$的值，而一般这个值有很显而易见的规律，或者可以手推，可能就可以打出正解了！ $\color{Grey}{-------------------------------------------}$ ## 于是有几条打表的总结技巧： 1、不要一开始就全部输出，首先先输出一些比较小的，以便找到规律，或是大致推断答案的种数，是否能直接放到数组里输出。 2、就算是打表程序，为了在规定时间内打完，也要制定策略，优化复杂度（如反素数），否则打到比赛结束没打完，就得不偿失了。 3、打表程序要力求简单而正确，其次是高效，才能发挥打表的作用。 4、数据种类较多时，主要以发现规律为主，无脑输出为辅。 5、打表有很多变种，并不是只能输出答案。 __6、不要太信任打表，有时间最好想想正解。大多数题目不能用打表做，平时要多练，直接打表输出是赛场上的方法。__ $\color{Grey}{-------------------------------------------}$ ```cpp ``` # 2 暴力 暴力可谓是一个很深的学问。大多数时候，比如NOIPTG，普通选手（看到这里的各位dalao除外）能想出一两道题的正解，剩下的都得靠暴力拿部分分。 不要小瞧了这部分分，据yanQval大神所言，如果NOIP2016TG中，只用裸暴力，而且代码本身没有问题，对于下面六道题：  可以拿$100+60+88+100+65+85=498$（此处感谢@凯瑟琳98 dalao指出我的算术错误）分！~~我就别想了qwq~~ 详细信息： $\color{Grey}{-------------------------------------------}$ $\color{Red}T1$、$\color{Blue}20/20$的数据点 模拟 $\color{Red}T2$、$\color{Blue}12/20$的数据点 $\color{Green}1-5$：$O(n^2)$暴力求出第几秒第几个人在第几点过去了 $\color{Green}6-8$：（退化成链）第X结点第Y秒钟观察，则起点只有在x-y~y之内，判断是否存在$O(n)$。 $\color{Green}9-12$：（起点在1号）所有人时间固定，某个时间是否有人过来，或终点就在子树内，递推$/BFS$ $\color{Red}T3$、$\color{Blue}22/25$的数据点 见下面讲解 $\color{Red}T4$、$\color{Blue}20/20$的数据点 二维前缀和（正解） $\color{Red}T5$、$\color{Blue}13/20$的数据点（普通堆模拟） $\color{Red}T6$、$\color{Blue}17/20$的数据点 状压DP（洛谷上搜索+剪枝可过） $\color{Grey}{-------------------------------------------}$ （当然D1T1、D2T1正解相对比较容易，所以打的是正解） 当然这是最乐观估计，实际上400分应该是差不多的，但是单暴力能拿400分也很不错了啊！ $\color{Black}{---------------------------------------------}$ 讲得有点多了，现在回到正题上来。 __所谓暴力，就是不用高级算法，用模拟，搜索，裸DP等等，复杂度感人，但是可以保证正确，还比较好打。__ 暴力涉及的算法很多： - 普通状压DP/无优化DP - 枚举（子集，染色等等） - DFS/BFS - 迭代加深搜索IDA* - 折半搜索 - 双向宽搜 - 一些看似不是暴力但本质是暴力的（比如下面那个Floyd） - …… 还可以用一些碰运气的做法：比如人工定个下界，对于DP就是只枚举$i-k\le j\le i$的$f[i]=min$ { $f[j]+cost(i,j)$ }，这样有点碰运气（有些时候的确可以证明是对的），但是可以优化暴力的时间复杂度。 出于可暴力的题目太多，我就不讲完了，重点挑一道题来看一看如何针对题目数据点分析暴力方法吧。 $\color{Black}{------------------------------------------}$ 请见[P1850 换教室](https://www.luogu.org/problemnew/show/P1850)，NOIP2016TG中暴力（理论上）拿分最高的题。（以下为yanQval大神所言，本人代码还没有调对……） 然后下面是25个数据点的范围：  注意到结点个数$v\le300$，首先可以Floyd预处理任意两点间距离，然后该怎么办呢？ 观察可换教室的申请数$m$，有19个数据点的$m\le2$，如此神奇的共同点肯定是有用的！ 当然有用了。考虑枚举换的$m$个教室，枚举复杂度为$O(n^m)$，分类讨论是否通过是$O(2^m)$，总时间复杂度为$O(n^m\times 2^m)$。但是对于$m$在$2$以下的数据，复杂度仅为$O(n^2\times 2^2)$，可以承受。因此，我们就这样拿到了19个数据点！ 哪怕常数大，应该也可以拿60多分吧！ $\color{Black}{-------------------------------------------}$ 我们还可以做得更好。$m>2$时，有三个数据点#$11$，#$15$，#$19$具有特殊性质$2$。特殊性质2是什么呢？  （洛谷图床万岁） $k_i$就是申请通过的概率。也就是说一定能通过，然后就可以愉快地DP，当然这不属于我要讲的内容了。 $\color{Black}{-------------------------------------------}$ __这道题只是一个例子，总的来讲，只要①想出暴力算法，先解决基本数据点，②然后再找到剩下数据点的共性，从特殊性质入手，解决特殊问题，就可以尽可能多地拿分。暴力，是非常重要的方法。__ $\color{Black}{------------------------------------------}$ ### 关于如何分类处理不同的数据点嘛……这可以用结构体，或者，如果您用C++，可以写在命名空间（$namespace$）里，这样不同命名空间里面的变量、函数可以重名，写起来不容易错，比较方便。例如： ```cpp namespace task1{ int a,b...; char c...; void solve(){ ... } } namespace task2{ int a,b...; char c...; void solve(){ ... } } ... int main(){ scanf("%d",&n); if(n is situation1)task1::solve(); if(n is situation2)task2::solve(); ... }//调用和平时相同，注意是:: ``` $\color{Black}{------------------------------------------}$ ~~真觉得试炼场应该加一个：~~  ## 秋豆麻袋！还没完！ 当然，这只是暴力的一角，如果想要拿到更高的分，在许多范围比较紧的时候，偏偏（像我这种人）常数又很大，就拿不到应该拿的分了。 $\color{Black}{------------------------------------------}$ 也许就这样说还不能领悟到暴力骗分的精髓，那让我们实践一下吧！ 实验名称：暴力 实验对象：[P2119 魔法阵](https://www.luogu.org/problemnew/show/P2119) NOIP2016PJT4 使用账号：我的小号@K423（U46777） 应用算法：$O(m^3)->O(n^3)$暴力（有略优化，但上界为$O(n^3)$） 一开始：  代码主程序如下： ```cpp //0 int main(){ scanf("%d%d",&n,&m);//1 for(int i=1;i<=m;i++){ scanf("%d",&b[i].a); b[i].id=i; k[b[i].a]++;//2 maxn=max(maxn,b[i].a); } sort(b+1,b+m+1,item_cmp);//3 for(int i=1;i<=m;i++){ if(b[i].a==b[i-1].a)st[i]=st[i-1]; else st[i]=i; } for(int i=1;i<=m;i++){//4 for(int j=st[i]+k[b[i].a];j<=m;j++){//5 if(((b[j].a-b[i].a)&1)==1)continue; int tmp=(b[j].a-b[i].a)/2; if(tmp+b[j].a>=maxn)break;//6 for(int g=st[j]+k[b[j].a];g<=m;g++){//7 if(tmp+b[g].a>maxn)break; e=st[g]+k[b[g].a];//8 while(b[e].a-b[g].a<tmp && e<=m){ e+=k[b[e].a]; }//9 if(b[e].a-b[g].a!=tmp)continue; if(b[g].a-b[j].a<=6*tmp)continue; s[b[i].id][0]+=k[b[e].a]; s[b[j].id][1]+=k[b[e].a]; s[b[g].id][2]+=k[b[e].a]; for(int l=st[e];l<st[e]+k[b[e].a];l++)s[b[l].id][3]++;//10 } } } for(int i=1;i<=m;i++){ for(int j=0;j<4;j++)printf("%d ",s[i][j]);//11 printf("\n"); } } ``` 注意上面标出的12（0~11）处可以优化的地方。 0、赖皮$O_2$ 1、可以加上快读（我的玄学程序加快读更慢了） 2.4.5.7.8、可以改一下方式，不用这种储存（见下面代码），可以更快 3、根本不用sort，因为权值较小，可以用桶排序 6、还有更紧的上界 5.9、可以用二分查找 10、因为有相同值，可以存值而不是物品。 11、快速输出和以值为基本输出 $\color{Black}{-------------------------------------------}$ 中间提交：  其中的最优解：（洛谷评测机升级之后快了很多……但还没低于4000msqwq）  代码： ```cpp // luogu-judger-enable-o2 void print(int x){ if(x>=10)print(x/10); putchar(x%10+'0'); }//快速输出 int main(){ scanf("%d%d",&n,&m); for(register int i=1;i<=m;++i){ scanf("%d",&v[i]); maxn=maxn>v[i]?maxn:v[i]; w[v[i]]++;//桶排序 } for(register int i=1;i<=maxn;i++){ if(w[i]){ k[++tot]=i; sum[i]=w[i];//权值存储至k数组 } } for(register int i=1;i<=tot;++i){//register for(register int j=i+1;j<=tot;++j){//register if(((k[j]-k[i])&1)==1)continue;//等价于(k[j]-k[i])%2==1 int tmp=(k[j]-k[i])>>1;//>>1等价于/2 if(7*tmp+k[j]>=maxn)break;//7*tmp为更紧的上界，因为k[e]至少要比k[j]大(6+1)*tmp。 for(register int g=j+1;g<=tot;++g){//register if(k[g]-k[j]<=6*tmp)continue; if(tmp+k[g]>maxn)break; e=lower_bound(k+g+1,k+tot+1,k[g]+tmp)-k;//二分 if(k[e]-k[g]!=tmp)continue; t=sum[k[i]]*sum[k[j]]*sum[k[g]]*sum[k[e]]; s[k[i]][0]+=t/sum[k[i]]; s[k[j]][1]+=t/sum[k[j]]; s[k[g]][2]+=t/sum[k[g]]; s[k[e]][3]+=t/sum[k[e]]; } } } for(register int i=1;i<=m;++i){ for(register int j=0;j<4;++j)print(s[v[i]][j]),putchar(' ');//快速输出&s数组存对应值的次数 printf("\n"); } } ``` 竟然一下快了8000ms！理论复杂度不变（虽然有二分，但是上界仍保持$O(n^3)$）！ 原来是65分，几个优化就到了85分（不开O2就80分）！如果“中间”数据的点数更多，我们可以拿更多分！ 这20分，可是有$EDJ->YDJ$，$Ag->Au$的魔力的！ 再总结一下优化的地方： 1、快速输出 2、快速排序转桶排序 3、更换存储方式 4、二分 ~~好像就剩算法没有改成正解了~~ （具体本题暴力的更快做法嘛……我最近看见一个3000ms以下的暴力，可惜后三个点太大，实在是过不了，大家可以看看评测记录里耗时比1000ms要长的代码，大多都是暴力，会觉得非常神奇的。） （出于那些代码不是我本人写的，我就不拿来用了） $\color{Black}{-------------------------------------------}$ 综上可知，暴力不是直接无脑上代码的，对暴力进行一些剪枝，就可以拿到更多的分。当然，这个是靠多练题，多总结，就可以掌握暴力的方法~~，轻松AKIOI~~。 ## 2-EX 随机化算法 骗分，怎能少了随机化和模拟退火！（输出随机数骗分这种就算了）（模拟退火因为我没经验，就不讲了，参见上面声明下方。） 随机化，即指『对于有些具有瑕疵的算法，配上随机数减小误差』，这可以得到意想不到的结果。 我知道有些dalao有强迫症，不准许有随机数出现在自己的程序里。这我可以理解，因为蒟蒻我平时连暴力都不敢打，更别说把自己的命运交给随机数了。但实际上，有些时候随机数异常有效，不仅代码比正解短，还跑的更快，虽然有些错误的概率，但是这也是可以接受的！ （比如您的Treap里就有随机数，复杂度很大程度上是由随机数决定的，期望是$O(logn)$而已，极小可能下还是会退化成链，但没有它，Treap就不能发挥作用了） ## 举个例子： 大家应该都知道，往地上丢火柴可以算出粗略π值，到程序实现时，可以用“投点法”代替，一个圆内接于正方形，随机若干次，可以算出π/4的粗略值。（这只是随机化的一个例子，平时还是用$acos(-1.0)$吧） ```cpp #include<cstdlib> #include<cstdio> #include<ctime> using namespace std; const int MAXN=100000;//投掷次数 const int RAND_M=32767;//上界 int tot=0;//出现次数 int main(){ srand(time(NULL)); for(int i=1;i<=MAXN;i++){ double a=(rand()%RAND_M)*1.000/RAND_M; double b=(rand()%RAND_M)*1.000/RAND_M;//生成随机实数 if((a-1.00/2)*(a-1.00/2)+(b-1.00/2)*(b-1.00/2)<=1.00/4)tot++;//圆方程(x-a)^2+(y-b)^2=r^2 } printf("%lf",tot*1.000/MAXN*4); } ``` 会输出3.139960等，与π=3.1415差的不是很远。如果增大次数，还能更接近。 再比如百度百科中的，枚举一个字符串的四个字符的组合种数，判断是否满足AAAA,AABB,ABBA,ABAB中的一种，就可以用随机化代替枚举，也可以在较高的概率下得到答案。 $\color{Black}{-------------------------------------------}$ 正如这两个例子，__在枚举情况过多甚至没有上界时，可以把程序交给随机化，反倒可以收获意想不到的效果。__ 还有一些，是因为__正解比较麻烦或是本来算法就要随机数__，所以才加入随机数的。 ## 1、最大团问题 最大团问题（$Maximum$ $Clique$ $Problem$，$MCP$）意即求出所含结点数最多的完全子图（结点之间两两有连边的子图）。 这是一个经典的$NPC$问题，常用算法都是搜索，贪婪启发式算法，模拟退火等等，其实本问题用随机数做也不错。参考[这里](https://blog.csdn.net/BlackJack_/article/details/73555052) __题目__：参考BZOJ 4080 __题意__：给出平面上$N(N\le100)$个点的坐标，选出一个点集$S$，使得$S$中的点两两之间欧几里得距离不超过$D$，问$|S|$的最大值，并输出$S$中的点编号。如有多解，任意输出一个。 这是一个最大团的模板，就用这道题来讲一下随机化贪心求最大团吧。 基本思路就是每次随机生成一个排列（就是随机交换$n$次），然后直接$O(n)$扫一遍，再$O(n)$把距离大于$D$的排掉（一般来讲这样就足够了，最大团一般$n$都不会超过100，我也不清楚是否有更低复杂度的。）遇到更大的答案更新即可。 主过程代码如下： ```cpp T=2000;//随机次数 for(int i=1;i<=T;i++){ random_shuffle(p+1,p+n+1),a[0]=0;//algorithm自带随机打乱函数 for(int j=1;j<=n;j++){//枚举所有点 for(int k=1;k<=a[0];k++) if(dist(p[j],a[k])>d*d) break;//如果当前集中的某个点距离大于D则退出 if(k>a[0])a[++a[0]]=a[j];//如果没问题，大小++，加入这个元素。 } if(a[0]>tot){ tot=a[0]; for(int j=1;j<=ans;j++)ans[j]=a[j]; }//更新 } ``` 这样写比较简单，同时也很难有考虑不到的情况（因为随机打乱过），所以推荐采用这种写法。（其实也可以用bitset但是本题规模似乎不需要） 这样随机化，代码简短，比起回溯效率更高，比起最大独立集更易于编写，不失为一种拼人品的好算法。 ## 2、字符串哈希 蛤希嘛，历来就是个靠人品的东西，往往都会用一些__大质数__作为模数。 但是用什么比较好，至今未下定论。有些时候反而合数比质数好，而且还有些毒瘤出题人专门卡常用的大质数（比如$10^9+7,998244353$，还有~~某位长者的生日~~等等） 于是呢，随机模数蛤希就登场啦，随便随机一个初始的$MOD$，只要限定一个范围，足够大就行。同理，也可以在$\sqrt n$附近选取一个值作为分块的块大小，免得有人卡。 当然，不排除有些极度毒瘤的出题人，出一大堆数据，包您~~满意~~被卡的舒舒服服。 （所以呢，如果有时间有能力（其实不差多少），还是打打双哈希比较好） $\color{Black}{-------------------------------------------}$ 还有舍伍德、拉斯维加斯算法等，各有用处，百度上都非常的详细了。我也没有什么特别好的例子（如果Treap不算的话），就建议大家多看别人的博客，自己搜索，收获更大。 随机化算法比较难以驾驭（毕竟太随机了），但是多做一些题，还是可以掌握技巧的。 # 3 总结 许多时候，考场上因为种种原因，不一定能想出正解，今天的骗分就非常重要了。 但是，打表和暴力并不是大家所想的那样，就是普通地上代码，优化可以帮助我们拿更多的分。__这些看似朴素的算法，实际上也需要多思考多优化，难度和重要性并不比别的算法低。__ 希望这份总结能帮到大家，如有不足，请多指正！谢谢！ # 4 鸣谢 ### @ComeIntoPower 打表与暴力的许多点子，文章上的建议 @白井黑子 卡常方面咨询 各位浴谷网校负责人 关于NOIP暴力讲解 @dyx666 @楚阳 等等同机房的dalao们（过多，不一一列出） 给予~~肉体和~~精神上的支持 https://sm.ms 提供一部分图床 http://oeis.org 提供技术支持 www.baidu.com 提供搜索引擎 我在改博客期间用过的三台电脑 给我提供基础 以及各位写了我引用的博客和知乎的dalao们，在此衷心感谢！ ~~如果认为有用，请点个赞，谢谢！~~