预处理

预处理是指将答案提前处理好然后再进行查询的方法。

什么时候会用到预处理？

查询量特别大的时候。

例题

我们要查询斐波那契数列的第n项，n（n < 10000）。
并且我们要查询10万次。

错误的超时解法

#include<bits/stdc++.h>  
using namespace std;  
  
int f[10005];  
int main(){  
    int t;  
    scanf("%d", &t);//查询次数  
    while (t--) {  
        int n;  
        scanf("%d", &n);//查询第k项  
        f[1] = 1;  
        f[2] = 1;  
        for (int i = 3; i <= n; i++) {  
            f[i] = f[i-1] + f[i-2];  
        }  
        printf("%d\n", f[n]);  
    }  
    return 0;  
}  

超时分析：每一次查询，我们都递推了一遍斐波那契数列，如果每一次查询的都是最后一项。那么最坏情况就是：100000*10000，必然是会超时的。

正确的预处理解法

#include<bits/stdc++.h>  
using namespace std;  
  
int f[10005];  
int main(){  
    f[1] = 1;  
    f[2] = 1;  
    for (int i = 3; i <= 10000; i++) {  
        f[i] = f[i-1] + f[i-2];  
    }  
    int t;  
    scanf("%d", &t);//查询次数  
    while (t--) {  
        int n;  
        scanf("%d", &n);//查询第k项  
        printf("%d\n", f[n]);  
    }  
    return 0;  
}  

可以发现两段代码惊人的相似，有什么区别呢？
区别在于下面的代码只会递推一遍斐波那契数列，然后将所有的答案都存储于f数组中。

一般打表技巧

打表是指我们提前使用暴力的方法，将答案记录下来写到纸上或代码中，然后再根据题目的实际需求去直接输出提前记录好的答案。

例题

求一个数x的100000000次方模2333的值是多少。
x的范围是(1<= x <=10)

解析：这个时候我们如果不会二分快速幂的话，可以直接用一个暴力的代码将1到10的答案分别求出来，可能要等上几分钟，然后直接判断输入的值对应输出结果即可。

打表找规律

在一些可能存在规律的问题中，我们可以通过暴力打表求出前几十项的值，发现其中的规律，从而帮助我们解出该题。

&nbs...

题目练习

DreamJudge 1488 数字填充