浅谈打表与其技巧
9098
浅谈打表与其技巧
critnos
·
2020-06-27 12:34:38
·
算法·理论
打表是啥？
打表，是一个信息学专用术语，意指对一些题目，通过打表技巧获得一个有序表或常量表，来执行程序某一部分，优化时间复杂度。这种算法也可用于在对某种题目没有最优解法时，用来得到分数的一种策略。——百度百科
因为交上去的程序运行时间有严格限制，但是本机运行则时间可以很长。所以提前用本机算出所有可能的数据的答案，拷贝到代码里。交上去的程序只用查表格就能得到答案。
这种方法适用于数据范围较小的情况。当然，本机的运行时间也要可以接受。
打表的代码，一般来说是时间可以接受，但又过不了的题目。比如跑 10^9，一般跑 10s，对于时限 1s 的测评机显然是不行的，但是本机可以。可是假如跑 2^{100} 那本机也无法在有意义的时间内跑完。
如果正解相当复杂，而打表又可以获得较高的分数甚至满分，在时间紧迫的赛场上是非常有用的。
一般来说打表分为两部分：打表程序和提交程序。
例子：P1035 级数求和
数据范围只有 [1,15] 且是正整数。所以可以写出这样的打表代码：
#include
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< } 运行后得到这样的结果： 2,4,11,31,83,227,616,1674,4550,12367,33617,91380,248397,675214,1835421, 怎么操作这个东西呢？拷贝到代码里。 #include 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< } 分块打表 如： \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） 假定您们随便爆切区间筛素数等等 orz 两问。莫比乌斯函数直接裸的区间筛，但欧拉函数的前缀和太大了。应该如何优化表的大小呢？ 首先，为什么要优化表的大小呢？ 一般来说，块长越小，表越大，程序运行速度越快。通过优化手段减小表的大小，可以通过减小块长达到优化程序效率的作用。 以欧拉函数为例： 你会发现欧拉函数一般是 n 级别的，在区间大小充分大（我取 10^6）的时候，表是递增的。所以相邻两项做差可以减小数的大小，表的大小自然减小了。 然后大眼观察法发现，经过第一次优化，表的每一项十分接近。对于这种情况，可以用下面两种方法： 每个数都减去表的最小值。 相邻两项继续做差。 似乎差不多？不过第二项更普适些（如果表中有一两个极小值优化 1 就失效了）。 还有如转换进制之类的，当然还是要按照数据的特性优化。 （插一个区间筛的小技巧） 对于上面的杜教筛板子，你会发现这东西数据范围达到了 2^{31}，无法直接筛（空间问题）。只能使用区间筛，一块一块的做筛。然后要调调参数，不一定每次直接筛块长，可以切成几部分来筛。这种调参可以用小数据尝试。 练习题 这种东西为啥有练习题 P2567 [SCOI2010]幸运数字（简单） P4213 【模板】杜教筛（Sum） P2657 [SCOI2009] windy 数 P4318 完全平方数 P5325 【模板】Min_25筛（较难 49.37KB 的代码你没有看错） 这里给出 P4318 的代码实现