CreeperK
2018-08-15 22:53:36
（注意：以下见解为个人观点，如有不足，请多指教。如果对卡常的几个名词
可能这篇文章初看标题会有一些dalao认为我写的东西很低级（虽然的确挺低级）
但是，我认为也值得浪费您一点时间看一看
相信多多少少也会有一些收获
（如果没有，我深表歉意。）
暴力是NOI系列比赛中极为重要的一环。而打表就更不用说了，是上述两者的补充，虽然耍赖，却能拿分，何乐而不为？本蒟蒻今日把上述两种技巧总结一下，方便各位轻松AK。
（卡常我就不说了，我就在暴力的时候顺便用一下，优化暴力的时间复杂度就算了）
（鉴于本人经验不足，太懒了没有打过经典的骗分算法——模拟退火，就不讲了，推荐一篇给大家，更多的题目还需要自行百度：这里）
说到底还不是因为我太弱才会来讲这些
声明：并非所有的知识都为我原创，我会尽量注明出处，如果哪位dalao认为我触犯了您的知识产权，我深表歉意，请在评论或是私信联系我，我会把出处加上。
那咱们就暂时离开恶心人的各种算法，来到骗分的天地吧。
打表，顾名思义，就是『获得一个有序表或常量表，来执行程序某一部分，优化时间复杂度』（摘自度娘），说白了就是先暴力（题目数据较大，题目简单）或手算（题目数据较小，难度较大）出答案，然后放进代码里，直接输出。
在我看来，打表不只有输出答案，还可以佐以我们的思考，成就一顿美味的程序。
有些人会问：“打表还有什么技巧？不就是什么数据什么输出吗？”不急，来看道题：
洛谷P1463 POI2002,HAOI2007 反素数
这道题可谓是经典的打表题（个人觉得搜索简单些），但是也不能无脑直接『打出答案』，比如我一开始的打表思路就是如下的伪代码：
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;这样可以得到一整个答案表。
但暂且不谈空间大小问题，单算算输出时间复杂度就够了。
输出
所以还是要优化一些。不难看出，速度瓶颈主要在输出上，于是可以上筛表，同时反素数个数实际上很少，不用全部输出对应答案，只要输出所有反素数即可。经非精确枚举，
时间太长时可能打不完，但是一般来讲这就可以了，因为暴力的时间平均也就比正解多几个
很多时候数据的种数很多，不可能全部打完，单纯的打表就不能满足我们的要求了。这个时候，打表可以帮助我们获得正解。
如《训练指南》P137，LA5059（UVA1482），这道题是个典型SG函数应用，汝佳大神就是先写了个递推程序，观察了SG函数的特点，得到
所以说明，打表不仅仅是直接输出答案，也可以找到数据与答案的联系，甚至推导正解。
如CSDN中的某位大神（似乎不止一位）所言：
遇到不会的题一定要想想能不能打表，运气好都能满分。
虽然本非酋表示不信但是就是觉得好霸气好有道理
遇到我们上面说反素数的问题，如果打不完怎么办？当然不能坐以待毙，肯定要奋起反击！
对于比较容易递推（可递推且依赖状态较少）的情况，我们可以请出打表的升级版：分段打表。
比如说，假设范围是2e9，答案种数又不如反素数那么少，那就只能让计算机算了，这时就可以以5e6为一块，打出BLOCK_SIZE（没错就是它）
（可以看看这里，相信会对分段打表有一个更清晰的认识）
有人可能会说，这不是分块的思想么？事实上我觉得，分块和分段打表都是同源的，把大的任务打散成块，只是分块稍微“优雅”一些而已。
块大小的问题吗……在可打出来的时间内尽可能把块变小，降低分段暴力的时间复杂度，这样最后拿高分的概率更大。
分段打表还可以用来算许多计数问题（包括组合数等）的答案。
许多计数问题可以把小数据的答案打出来，得到一个基础数列，然后可以放进这个神奇的网站
你没看错这清奇的画风，就是它：
它可以干嘛呢？
你可以试着点一下
或者说，想要锻炼或是比赛场上，得靠自己手算，人脑找规律，就可以有如下几种方法：
1、神犇型：直接观察
2、大佬型：凭经验
3、我型：借助纸笔好好算算
然后看看，能否线性递推，或是有直接多项式（每项相互独立）可以表示，再比如有没有与组合数相关的规律，再用对应的算法验证。或者也可以看看是否是积性函数。
什么？您问我积性函数是什么？
数论中，就是对于正整数
想了解更多？看这里
积性函数有一个有趣而有用的性质：
如果是积性函数怎么用？这就容易得多了，可以直接快速递推，麻麻再也不用担心我会超时啦。这样，可以只关注
1、不要一开始就全部输出，首先先输出一些比较小的，以便找到规律，或是大致推断答案的种数，是否能直接放到数组里输出。
2、就算是打表程序，为了在规定时间内打完，也要制定策略，优化复杂度（如反素数），否则打到比赛结束没打完，就得不偿失了。
3、打表程序要力求简单而正确，其次是高效，才能发挥打表的作用。
4、数据种类较多时，主要以发现规律为主，无脑输出为辅。
5、打表有很多变种，并不是只能输出答案。
6、不要太信任打表，有时间最好想想正解。大多数题目不能用打表做，平时要多练，直接打表输出是赛场上的方法。
暴力可谓是一个很深的学问。大多数时候，比如NOIPTG，普通选手（看到这里的各位dalao除外）能想出一两道题的正解，剩下的都得靠暴力拿部分分。
不要小瞧了这部分分，据yanQval大神所言，如果NOIP2016TG中，只用裸暴力，而且代码本身没有问题，对于下面六道题：
可以拿我就别想了qwq
详细信息：
（当然D1T1、D2T1正解相对比较容易，所以打的是正解）
当然这是最乐观估计，实际上400分应该是差不多的，但是单暴力能拿400分也很不错了啊！
讲得有点多了，现在回到正题上来。
所谓暴力，就是不用高级算法，用模拟，搜索，裸DP等等，复杂度感人，但是可以保证正确，还比较好打。
暴力涉及的算法很多：
普通状压DP/无优化DP
枚举（子集，染色等等）
DFS/BFS
迭代加深搜索IDA*
折半搜索
双向宽搜
一些看似不是暴力但本质是暴力的（比如下面那个Floyd）
……
还可以用一些碰运气的做法：比如人工定个下界，对于DP就是只枚举
出于可暴力的题目太多，我就不讲完了，重点挑一道题来看一看如何针对题目数据点分析暴力方法吧。
请见P1850 换教室，NOIP2016TG中暴力（理论上）拿分最高的题。（以下为yanQval大神所言，本人代码还没有调对……）
然后下面是25个数据点的范围：
注意到结点个数
观察可换教室的申请数
当然有用了。考虑枚举换的
哪怕常数大，应该也可以拿60多分吧！
我们还可以做得更好。
（洛谷图床万岁）
这道题只是一个例子，总的来讲，只要①想出暴力算法，先解决基本数据点，②然后再找到剩下数据点的共性，从特殊性质入手，解决特殊问题，就可以尽可能多地拿分。暴力，是非常重要的方法。
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();
...
}//调用和平时相同，注意是::真觉得试炼场应该加一个：
当然，这只是暴力的一角，如果想要拿到更高的分，在许多范围比较紧的时候，偏偏（像我这种人）常数又很大，就拿不到应该拿的分了。
也许就这样说还不能领悟到暴力骗分的精髓，那让我们实践一下吧！
实验名称：暴力
实验对象：P2119 魔法阵 NOIP2016PJT4
使用账号：我的小号@K423（U46777）
应用算法：
一开始：
代码主程序如下：
//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、赖皮
1、可以加上快读（我的玄学程序加快读更慢了）
2.4.5.7.8、可以改一下方式，不用这种储存（见下面代码），可以更快
3、根本不用sort，因为权值较小，可以用桶排序
6、还有更紧的上界
5.9、可以用二分查找
10、因为有相同值，可以存值而不是物品。
11、快速输出和以值为基本输出
中间提交：
其中的最优解：（洛谷评测机升级之后快了很多……但还没低于4000msqwq）
代码：
// 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！理论复杂度不变（虽然有二分，但是上界仍保持
原来是65分，几个优化就到了85分（不开O2就80分）！如果“中间”数据的点数更多，我们可以拿更多分！
这20分，可是有
再总结一下优化的地方：
1、快速输出
2、快速排序转桶排序
3、更换存储方式
4、二分
好像就剩算法没有改成正解了
（具体本题暴力的更快做法嘛……我最近看见一个3000ms以下的暴力，可惜后三个点太大，实在是过不了，大家可以看看评测记录里耗时比1000ms要长的代码，大多都是暴力，会觉得非常神奇的。）
（出于那些代码不是我本人写的，我就不拿来用了）
综上可知，暴力不是直接无脑上代码的，对暴力进行一些剪枝，就可以拿到更多的分。当然，这个是靠多练题，多总结，就可以掌握暴力的方法，轻松AKIOI。
骗分，怎能少了随机化和模拟退火！（输出随机数骗分这种就算了）（模拟退火因为我没经验，就不讲了，参见上面声明下方。）
随机化，即指『对于有些具有瑕疵的算法，配上随机数减小误差』，这可以得到意想不到的结果。
我知道有些dalao有强迫症，不准许有随机数出现在自己的程序里。这我可以理解，因为蒟蒻我平时连暴力都不敢打，更别说把自己的命运交给随机数了。但实际上，有些时候随机数异常有效，不仅代码比正解短，还跑的更快，虽然有些错误的概率，但是这也是可以接受的！
（比如您的Treap里就有随机数，复杂度很大程度上是由随机数决定的，期望是
大家应该都知道，往地上丢火柴可以算出粗略π值，到程序实现时，可以用“投点法”代替，一个圆内接于正方形，随机若干次，可以算出π/4的粗略值。（这只是随机化的一个例子，平时还是用
#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中的一种，就可以用随机化代替枚举，也可以在较高的概率下得到答案。
正如这两个例子，在枚举情况过多甚至没有上界时，可以把程序交给随机化，反倒可以收获意想不到的效果。
还有一些，是因为正解比较麻烦或是本来算法就要随机数，所以才加入随机数的。
最大团问题（
这是一个经典的
题目：参考BZOJ 4080
题意：给出平面上
这是一个最大团的模板，就用这道题来讲一下随机化贪心求最大团吧。
基本思路就是每次随机生成一个排列（就是随机交换
主过程代码如下：
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但是本题规模似乎不需要）
这样随机化，代码简短，比起回溯效率更高，比起最大独立集更易于编写，不失为一种拼人品的好算法。
蛤希嘛，历来就是个靠人品的东西，往往都会用一些大质数作为模数。
但是用什么比较好，至今未下定论。有些时候反而合数比质数好，而且还有些毒瘤出题人专门卡常用的大质数（比如某位长者的生日等等）
于是呢，随机模数蛤希就登场啦，随便随机一个初始的
当然，不排除有些极度毒瘤的出题人，出一大堆数据，包您满意被卡的舒舒服服。
（所以呢，如果有时间有能力（其实不差多少），还是打打双哈希比较好）
还有舍伍德、拉斯维加斯算法等，各有用处，百度上都非常的详细了。我也没有什么特别好的例子（如果Treap不算的话），就建议大家多看别人的博客，自己搜索，收获更大。
随机化算法比较难以驾驭（毕竟太随机了），但是多做一些题，还是可以掌握技巧的。
许多时候，考场上因为种种原因，不一定能想出正解，今天的骗分就非常重要了。
但是，打表和暴力并不是大家所想的那样，就是普通地上代码，优化可以帮助我们拿更多的分。这些看似朴素的算法，实际上也需要多思考多优化，难度和重要性并不比别的算法低。
希望这份总结能帮到大家，如有不足，请多指正！谢谢！
@白井黑子 卡常方面咨询
各位浴谷网校负责人 关于NOIP暴力讲解
@dyx666 @楚阳 等等同机房的dalao们（过多，不一一列出） 给予肉体和精神上的支持
https://sm.ms 提供一部分图床
http://oeis.org 提供技术支持
www.baidu.com 提供搜索引擎
我在改博客期间用过的三台电脑 给我提供基础
以及各位写了我引用的博客和知乎的dalao们，在此衷心感谢！
如果认为有用，请点个赞，谢谢！