算法技巧——打表

什么是打表？

打表，是一个信息学专用术语，意指对一些题目，通过打表技巧获得一个有序表或常量表，来执行程序某一部分，优化时间复杂度。这种算法也可用于在对某种题目没有最优解法时，用来得到分数的一种策略。

交上去的代码有严格的运行时间限制，但是代码在本地运行时间没有限制，所以可以提交前，先在本地运行，算出所有可能的结果，正式提交代码，开个数组把所有答案存起来，做到直接输出。

注意这个技巧只适用于输入的值域不大（如，输入只有一个数，而且范围很小）的问题，否则可能会导致代码过长、MLE、打表需要的时间过长等问题。

打表

一般来说打表分为两部分：打表程序和提交程序。

打表程序算出所有可能数据对应结果，提交程序存储答案并输出

例子：级数求和

首先写程序，计算出不同输入值对应的所有答案

#include<bits/stdc++.h>
using namespace std;int f(int k)
{double s=0;double i=1;while(s<=k){s=s+1/i;i++;}return i-1;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);for(int i=1;i<=15;i++){cout<<f(i)<<',';}return 0;
}

接着编写提交程序，把所有结果存储到数组中，根据输入的变量值，直接查找对应答案

#include<bits/stdc++.h>using namespace std;int res[15]={2,4,11,31,83,227,616,1674,4550,12367,33617,91380,248397,675214,1835421};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int k;cin>>k;cout<<res[k-1];return 0;}

分段打表

代码长度有限，如果每个结果都存下来，不太现实，应用分块的思想，将数据范围分成多个块，预处理每一块的信息，对不满一块的直接暴力，即一种平衡了代码长度和复杂度的技巧