打表法
打表法是信息学竞赛中常见的骗分方法，面对小数据，有着不可估量的作用，配合搜索、枚举等算法效果更好
例如火柴棒等式
给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是00）。用火柴棍拼数字0-9的对应如下所示：
0->6根1->2根2->5根3->5根
4->4根5->5根6->6根7->3根
8->7根9->6根
题目链接:https://vijos.org/p/1496
这道题看似复杂，其实并不难
正解和歪解都需要打表
歪解:纯打表
我们只需定义一个答案数组
int ans[25]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39,38,65,88,128};
然后输出ans的第a个元素(a代表输入的数)
scanf("%d",&a);
printf("%d",ans[a]);
就完成了
正解:回溯+打表
先打出10以内的需要火柴棒根数的表
int x[1001]={6,2,5,5,4,5,6,3,7,6};
然后生成10以外的需要火柴棒根数的表
for(i=10;i<=999;++i)x[i]=x[i/10]+x[i%10];
进行回溯,回溯部分由于篇幅原因需读者自己写
从这道题我们知道了
相对应的的关系可以用打表，例如输入n，输出ans这种
拓展出输入n，输出ans，ans-sum（各打一个表）
打表的拓展
打表作为骗分是一个很简单的手段，但有时打表用途会更大
例如一些标记问题，可以打表把它可以活动的区域（或禁区）标记出来，进行尝试
例如很多问题都有向上走，向下走，向左走，向右走的问题
我们可以这样打表
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
我们无需判断向哪个方向走
只需这样调用
for(i=0;i<4;i++)
{
int xx,yy;
xx=当前x坐标+dx[i];
yy=当前y坐标+dy[i];
...//干你需要干的
}
这样就轻松了许多
打表还可以优化时间复杂度
打表的程序大大提高了程序运行时间，有些都是O(1)的复杂度，而利用打表优化的程序复杂度通常可以减少许多
例如素数问题
朴素的筛素数（试除法）
int isprime(int x)
{
int i;
if(x<2)return 0;
if(x==2)return 1;
for(i=1;i<=floor(sqrt(x)+0.5);i++)
if(x%i==0)return 0;
return 1;
}
单个数判断复杂度是O(sqrt(x))
但是，如果一共需要判断n个数，那么复杂度是O(nsqrt(x))，对于一些题刁钻的数据，是不可接受的，那么我们怎么优化呢？
很多人就去学各种莫名其妙的筛法，然后写爆了
我们可以生成一个素数表
说到这有人就问了，如何去生成素数表呢？你要打那么多数据，不可能手算吧
所以我要教大家如何生成这个表
我们不是学了文件操作吗？我们可以利用文件操作进行生成，把表的数据写到文件里，起名随意
1. int main()
2. {
3. int i;
4. for(i=起始数;i<=结束数;i++)
5. if(isprime(i))fprintf(fin,"%d,",i);
6. return 0;
7. }
然后我们就可以用这个来打表，注意把最后一个逗号删掉,得出
int ans[...]={2,3,5,7,11,13,17,19,...};
然后这样的题就解决了
光说不练不行，还得实战检验
符号三角形
Problem Description
符号三角形的 第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同 。 n=7时的1个符号三角形如下:
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+
Input
每行1个正整数n <=24,n=0退出.
Output
n和符号三角形的个数.
Sample Input
15 16 19 20 0
Sample Output
15 1896
16 5160
19 32757
20 59984
提示：这道题考的是搜索剪枝，可以搜索不减枝打表
求斐波那契数列第n项
Problem Description
斐波那契数列就是兔子数列，现在要你求第n项，第一项1，第二项1，第三项2，n>=3时 第n项等于前两项之和
Input
n <=46
Output
斐波那契第n项
Sample Input
4
Sample Output
3
提示：这道题考的是递推，可以递归打表
！！！搜索剪枝题如果数据不是特别大又是1 1对应的，可以进行搜索打表，生成时间复杂度O(2^n*组数)
以上内容均来自于《骗分攻略》（我自己写的书，未发行）