浅谈打表与其技巧

## 打表是啥？ >打表，是一个信息学专用术语，意指对一些题目，通过打表技巧获得一个有序表或常量表，来执行程序某一部分，优化时间复杂度。这种算法也可用于在对某种题目没有最优解法时，用来得到分数的一种策略。——百度百科 因为交上去的程序运行时间有严格限制，但是本机运行则时间可以很长。所以提前用本机算出所有可能的数据的答案，拷贝到代码里。交上去的程序只用查表格就能得到答案。 这种方法适用于数据范围较小的情况。当然，本机的运行时间也要可以接受。 打表的代码，一般来说是时间可以接受，但又过不了的题目。比如跑 $10^9$，一般跑 $10s$，对于时限 $1s$ 的测评机显然是不行的，但是本机可以。可是假如跑 $2^{100}$ 那本机也无法在有意义的时间内跑完。 如果正解相当复杂，而打表又可以获得较高的分数甚至满分，在时间紧迫的赛场上是非常有用的。 一般来说打表分为两部分：**打表程序**和**提交程序**。 例子：[P1035 级数求和](https://www.luogu.com.cn/problem/P1035) 数据范围只有 $[1,15]$ 且是正整数。所以可以写出这样的打表代码： ```cpp #include<bits/stdc++.h> using namespace std; int f(int k) { double i=1,s=0; while(s<=k) { s=s+1/i; i++; } return i-1; } int main() { for(int i=1;i<=15;i++) cout<<f(i)<<','; } ``` 运行后得到这样的结果： ``` 2,4,11,31,83,227,616,1674,4550,12367,33617,91380,248397,675214,1835421, ``` 怎么操作这个东西呢？拷贝到代码里。 ```cpp #include<bits/stdc++.h> using namespace std; int a[]={2,4,11,31,83,227,616,1674,4550,12367,33617,91380,248397,675214,1835421},k; int main() { cin>>k; cout<<a[k-1]; } ``` ## 分块打表 如： $$\sum_{i=1}^n f(i)$$ 这种式子。 一般来说，洛谷上的代码长度提交限制是 50k，CCF 是 100k。如果上面的 $n$ 给到 $10^9$ 打表就无能为力了。 （根据我自己的经验打表一般就存不多于 $10^4$ 个数） 然而，仔细想想…… **真的有必要吗？** 比如 $\sum_{i=1}^{100} f(i)$ 已经在表里了，要算 $\sum_{i=1}^{101} f(i)$，你还老老实实的把这个东西放到表里面，但其实只用 $\sum_{i=1}^{100} f(i)$ 再加上 $f(101)$ 就好了。 分块打表就是这种思想。预处理出一部分的数值。以上面的式子为例，$\sum_{i=1}^n f(i)$ 可以分成两部分：$\sum_{i=1}^k f(i)+\sum_{i=k+1}^n f(i)$。 其中 $\sum_{i=1}^k f(i)$ 是表中已经有的，这部分直接查表。对于另一部分，因为前面已经被减掉了大部分所以也不会太多，这部分直接暴力。 事实上，分块打表顾名思义，就是把数据范围分成多个块，预处理每一块的信息，对不满一块的直接暴力，和分块数据结构异曲同工。 假定块长为 $b$，则不满一块的最多有 $b$ 个要暴力的，这就保证了分块打表的复杂度。要预处理的部分为 $[1,b],[b+1,2b],[2b+1,3b]\dots [kb+1,n]$。 复杂度为暴力计算的复杂度。 所以，分块打表是一种平衡了代码长度和时间复杂度的算法（技巧？）。 ~~图略丑~~  ## 分块打表的优化 例子：[P4213 【模板】杜教筛（Sum）](https://www.luogu.com.cn/problem/P4213) ~~假定您们随便爆切区间筛素数等等 orz~~ 两问。莫比乌斯函数直接裸的区间筛，但欧拉函数的前缀和太大了。应该如何优化表的大小呢？ 首先，为什么要优化表的大小呢？ 一般来说，块长越小，表越大，程序运行速度越快。通过优化手段减小表的大小，可以通过减小块长达到优化程序效率的作用。 以欧拉函数为例： 你会发现欧拉函数一般是 $n$ 级别的，在区间大小充分大（我取 $10^6$）的时候，表是递增的。所以相邻两项做差可以减小数的大小，表的大小自然减小了。 然后大眼观察法发现，经过第一次优化，表的每一项十分接近。对于这种情况，可以用下面两种方法： * 每个数都减去表的最小值。 * 相邻两项继续做差。 似乎差不多？不过第二项更普适些（如果表中有一两个极小值优化 $1$ 就失效了）。 还有如转换进制之类的，当然还是要按照数据的特性优化。 （插一个区间筛的小技巧） 对于上面的杜教筛板子，你会发现这东西数据范围达到了 $2^{31}$，无法直接筛（空间问题）。只能使用区间筛，一块一块的做筛。然后要调调参数，不一定每次直接筛块长，可以切成几部分来筛。这种调参可以用小数据尝试。 ## ~~练习题~~ ~~这种东西为啥有练习题~~ [P2567 [SCOI2010]幸运数字](https://www.luogu.com.cn/problem/P2567)（简单） [P4213 【模板】杜教筛（Sum）](https://www.luogu.com.cn/problem/P4213) [P2657 [SCOI2009] windy 数](https://www.luogu.com.cn/problem/P2657) [P4318 完全平方数](https://www.luogu.com.cn/problem/P4318) [P5325 【模板】Min_25筛](https://www.luogu.com.cn/problem/P5325)（较难 ~~49.37KB 的代码你没有看错~~） [这里给出 P4318 的代码实现 ](https://www.luogu.com.cn/paste/xeupjlge)