浅谈打表与其技巧

打表是啥？

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

因为交上去的程序运行时间有严格限制，但是本机运行则时间可以很长。所以提前用本机算出所有可能的数据的答案，拷贝到代码里。交上去的程序只用查表格就能得到答案。

这种方法适用于数据范围较小的情况。当然，本机的运行时间也要可以接受。

打表的代码，一般来说是时间可以接受，但又过不了的题目。比如跑 10^9，一般跑 10s，对于时限 1s 的测评机显然是不行的，但是本机可以。可是假如跑 2^{100} 那本机也无法在有意义的时间内跑完。

如果正解相当复杂，而打表又可以获得较高的分数甚至满分，在时间紧迫的赛场上是非常有用的。

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

例子：P1035 级数求和

数据范围只有 [1,15] 且是正整数。所以可以写出这样的打表代码：

#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,

怎么操作这个东西呢？拷贝到代码里。

#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）

假定您们随便爆切区间筛素数等等 orz

两问。莫比乌斯函数直接裸的区间筛，但欧拉函数的前缀和太大了。应该如何优化表的大小呢？

首先，为什么要优化表的大小呢？

一般来说，块长越小，表越大，程序运行速度越快。通过优化手段减小表的大小，可以通过减小块长达到优化程序效率的作用。

以欧拉函数为例：

你会发现欧拉函数一般是 n 级别的，在区间大小充分大（我取 10^6）的时候，表是递增的。所以相邻两项做差可以减小数的大小，表的大小自然减小了。

然后大眼观察法发现，经过第一次优化，表的每一项十分接近。对于这种情况，可以用下面两种方法：

• 每个数都减去表的最小值。

• 相邻两项继续做差。

似乎差不多？不过第二项更普适些（如果表中有一两个极小值优化 1 就失效了）。

还有如转换进制之类的，当然还是要按照数据的特性优化。

（插一个区间筛的小技巧）

对于上面的杜教筛板子，你会发现这东西数据范围达到了 2^{31}，无法直接筛（空间问题）。只能使用区间筛，一块一块的做筛。然后要调调参数，不一定每次直接筛块长，可以切成几部分来筛。这种调参可以用小数据尝试。

练习题

这种东西为啥有练习题

P2567 [SCOI2010]幸运数字（简单）

P4213 【模板】杜教筛（Sum）

P2657 [SCOI2009] windy 数

P4318 完全平方数

P5325 【模板】Min_25筛（较难 49.37KB 的代码你没有看错）

这里给出 P4318 的代码实现