「杂谈·一」浅谈打表

大家好，欢迎来到IT知识分享网。

1. 打表之“是什么”“为什么”“怎么办”

1-1. 打表是什么？

打表，顾名思义，就是将所有可能的答案打成一个表，进行看似不太正经地求解。

1-2. 为什么要打表？

有时，题目输入的数据很小，我们无法用程序高效求出，这时，我们就可以预先算出答案，存储进一个数组中，然后就可以“对号入座”了。

1-3. 怎么打表？

一般地，我们会有一个 table.cpp/py（用来打表的程序）与 solve.cpp（最终程序），先执行 table.cpp，一般会输出到文件 table.txt，然后复制 table.txt 的内容到 solve.cpp 轻松解题。

2. 打表题选——直接打表

这些题目，我们直接打表输出即可。

2-1. 蛇形方阵

题目描述

给出一个不大于 $9$ 的正整数 $n$，输出 $n\times n$ 的蛇形方阵。
从左上角填上 $1$ 开始，顺时针方向依次填入数字，如同样例所示。注意每个数字有都会占用 $3$ 个字符，前面使用空格齐。

输入格式

输入一个正整数 $n$，含义如题所述。

输出格式

输出符合题目要求的蛇形矩阵。

样例输入

4 

样例输出

 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 

提示

数据保证，$1\le n\le 9$。

记得在学数组时，我们会写出类似这样的程序：

#include<bits/stdc++.h> using namespace std; int n,t,i,j,a[105][105]; int main() { 
        cin>>n; t=i=j=1; while(t<=n*n) { 
        while(j<=n&&!a[i][j]){ 
       a[i][j]=t++;j++;}i++;j--; while(i<=n&&!a[i][j]){ 
       a[i][j]=t++;i++;}i--;j--; while(j>=1&&!a[i][j]){ 
       a[i][j]=t++;j--;}i--;j++; while(i>=1&&!a[i][j]){ 
       a[i][j]=t++;i--;}i++;j++; } for(int i=1;i<=n;i++) { 
        for(int j=1;j<=n;j++) { 
        cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; } 

数据保证，$1\le n\le 9$。

#include<bits/stdc++.h> using namespace std; int main() { 
        int n; cin>>n; if(n==1) puts(" 1"); if(n==2) puts(" 1 2\n 4 3"); if(n==3) puts(" 1 2 3\n 8 9 4\n 7 6 5"); if(n==4) puts(" 1 2 3 4\n 12 13 14 5\n 11 15 16 6\n 10 9 8 7"); if(n==5) puts(" 1 2 3 4 5\n 16 17 18 19 6\n 15 24 25 20 7\n 14 23 22 21 8\n 13 12 11 10 9"); if(n==6) puts(" 1 2 3 4 5 6\n 20 21 22 23 24 7\n 19 32 33 34 25 8\n 18 31 36 35 26 9\n 17 30 29 28 27 10\n 16 15 14 13 12 11"); if(n==7) puts(" 1 2 3 4 5 6 7\n 24 25 26 27 28 29 8\n 23 40 41 42 43 30 9\n 22 39 48 49 44 31 10\n 21 38 47 46 45 32 11\n 20 37 36 35 34 33 12\n 19 18 17 16 15 14 13"); if(n==8) puts(" 1 2 3 4 5 6 7 8\n 28 29 30 31 32 33 34 9\n 27 48 49 50 51 52 35 10\n 26 47 60 61 62 53 36 11\n 25 46 59 64 63 54 37 12\n 24 45 58 57 56 55 38 13\n 23 44 43 42 41 40 39 14\n 22 21 20 19 18 17 16 15"); if(n==9) puts(" 1 2 3 4 5 6 7 8 9\n 32 33 34 35 36 37 38 39 10\n 31 56 57 58 59 60 61 40 11\n 30 55 72 73 74 75 62 41 12\n 29 54 71 80 81 76 63 42 13\n 28 53 70 79 78 77 64 43 14\n 27 52 69 68 67 66 65 44 15\n 26 51 50 49 48 47 46 45 16\n 25 24 23 22 21 20 19 18 17"); return 0; } 

2-2. T 型骨牌

题目描述

在 $n\times m$ 的棋盘上，摆入 T 型，T 型可以旋转，具体包括如下四个样式（# 代表被 T 型占据的格子，. 代表自由的格子）：

 ..# .#. #.. .#. .#. .#. ..# #.. 

问最多能在 $n\times m$ 的棋盘上摆入多少个不重叠的T型。

输入格式

两个数 $n,m(1\le n,m\le 9)$。

输出格式

一个数，最多能放入多少个 T 型。

样例输入

5 6 

样例输出

4 

提示

会发现，我们直接写这题，可以得到 $70\text{pts}$ 的好成绩。可惜你颓废了，不会优化（雾）。
此时，你又发现：

两个数 $n,m(1\le n,m\le 9)$。

#include<bits/stdc++.h> using namespace std; int ans[10][10]; int main() { 
         ans[3][3]=1; ans[3][4]=1; ans[3][5]=2; ans[3][6]=2; ans[3][7]=3; ans[3][8]=3; ans[3][9]=4; ans[4][3]=1; ans[4][4]=2; ans[4][5]=2; ans[4][6]=3; ans[4][7]=4; ans[4][8]=4; ans[4][9]=5; ans[5][3]=2; ans[5][4]=2; ans[5][5]=4; ans[5][6]=4; ans[5][7]=5; ans[5][8]=6; ans[5][9]=7; ans[6][3]=2; ans[6][4]=3; ans[6][5]=4; ans[6][6]=5; ans[6][7]=6; ans[6][8]=7; ans[6][9]=8; ans[7][3]=3; ans[7][4]=4; ans[7][5]=5; ans[7][6]=6; ans[7][7]=8; ans[7][8]=9; ans[7][9]=10; ans[8][3]=3; ans[8][4]=4; ans[8][5]=6; ans[8][6]=7; ans[8][7]=9; ans[8][8]=10; ans[8][9]=12; ans[9][3]=4; ans[9][4]=5; ans[9][5]=7; ans[9][6]=8; ans[9][7]=10; ans[9][8]=12; ans[9][9]=13; int n,m; cin>>n>>m; cout<<ans[n][m]; return 0; } 

2-3. 球的体积

题目描述

已知一个半径为 $r$ 的球体，现在问这个球的体积为多少？
计算时，取 $\pi =3.14$。

输入格式

输入共一行，其中包括一个正整数 $r$ 表示球体的半径。

输出格式

输出共一行，其中包括球体的体积。要求保留小数点后 $5$ 位。

样例输入

5 

样例输出

523.33333 

提示

$1\le r\le 100$。

假如你不会处理保留小数点（雾）。

2-4. 旋转数塔

题目描述

小 $\text{X}$ 是 $\text{C}$ 城著名的考古学家。一日，他被重金聘请调查一座荒漠中的宫殿。
宫殿大门紧闭，但这难不倒聪明的小 $\text{X}$ 。他在隐蔽处发现了两个数字正方形：

小 $\text{X}$ 略加思索便发现了其中的奥妙：把数字从小到大依次填入正方形中，每次填最外面的一圈；每一圈从左上角开始，按照顺时针、逆时针、顺时针……的顺序填。
作为小 $\text{X}$ 的助手，他希望你帮助他以相同的规律填上旁边 $n\times n$ 的空白方阵。这里方阵是数字正方形的简称，通常用二维数组来存放其中的数字。

输入格式

输入数据仅有一行，包含一个正整数 $n$ ，表示方阵的边长，即每行每列有多少个数。

输出格式

输出仅 $n$ 行，每行 $n$ 个正整数，相邻两数之间严格用一个空格隔开。

样例输入

6 

样例输出

1 2 3 4 5 6 20 21 32 31 30 7 19 22 33 34 29 8 18 23 36 35 28 9 17 24 25 26 27 10 16 15 14 13 12 11 

提示

数据规模：
本题共有 $10$ 个测试点，每个测试点 $10$ 分：
对于测试点 $1$：$n=1$；对于测试点 $2$：$n=2$；
对于测试点 $3$：$n=3$；对于测试点 $4$：$n=4$；
对于测试点 $5$：$n=7$；对于测试点 $6$：$n=8$；
对于测试点 $7$：$n=10$；对于测试点 $8$：$n=15$；
对于测试点 $9$：$n=25$；对于测试点 $10$：$n=50$。

与 2-1 类似。

2-5. 阶乘之和

题目描述

用高精度计算出 $S=1!+2!+3!+\cdots +n!$（$n\le 50$）。
其中 ! 表示阶乘，定义为 $n!=n\times (n-1)\times (n-2)\times \cdots \times 1$。例如，$5!=5\times 4\times 3\times 2\times 1=120$。

输入格式

一个正整数 $n$。

输出格式

一个正整数 $S$，表示计算结果。

样例输入

3 

样例输出

9 

提示

对于 $100\%$ 的数据，$1\le n\le 50$。

假如你不会高精度（雾），可以先用 Python 计算答案然后存进表中。

3. 打表题选——打表找规律

这些题目，我们可以通过把答案打一个表，然后寻找其中的规律。

3-1. 无穷的序列

题目描述

输入格式

第一行一个正整数 $N$ ，表示询问次数；
接下来的 $N$ 行每行一个正整数 $A_i$，$A_i$ 表示在序列中的位置。

输出格式

输出为 $N$ 行，每行为 $0$ 或 $l$ ，表示序列第 $A_i$ 位上的数字。

样例输入

4 3 14 7 6 

样例输出

0 0 1 0 

提示

对于 $100\%$ 的数据，$N\le 1500000$，$A_i\le 10^9$。

我们可以通过打表，来列举出所有是 $1$ 的位：$1,2,4,7,11,16,22,\cdots$。
我们发现，第 $n$ 个就是 $1+1+2+3+4+5+\cdots +n=\frac{n(n+1)}{2}+1$。
故对于第 $n$ 个是不是 $1$，只要判断 $\frac{\sqrt{2(n-1)}\times (\sqrt{2(n-1)}+1)}{2}=n-1$ 即可。
AC Code：

#include<bits/stdc++.h> using namespace std; int main() { 
              int t; scanf("%d",&t); while(t--) { 
              int n; scanf("%d",&n); n--; printf("%d\n",int(sqrt(n*2))*int(sqrt(n*2)+1)==n*2); } return 0; } 

3-2. 数列之异或

题目描述

求 $1⨁2⨁\cdots ⨁N$ 的值。
$A⨁B$ 即$A$ , $B$ 按位异或。

输入格式

1 个整数$N$。

输出格式

1 个整数，表示所求的值。

样例输入

3 

样例输出

0 

提示

• 对于50% 的数据，$1\le N\le 10^6$；
• 对于100% 的数据，$1\le N\le 10^{18}$。

对于这道题，我们先从 $1$ 打表找规律：$1,3,0,4,1,7,0,8,1,11,0,12,\cdots$。
我们把其四个四个分成一组：$(1,3,0,4),(1,7,0,8),(1,11,0,12),\cdots$。
会发现，每组的第一、三个分别为 $1,0$；第二、四个分别为 $n+1,n$。
AC Code：

#include<bits/stdc++.h> using namespace std; int main() { 
               long long n; cin>>n; long long ans[]={ 
              1,n+1,0,n}; cout<<ans[(n-1)%4]; return 0; } 

4. 打表题选——间接打表

这些题目，我们可以在某些操作上进行打表，方便求解。

4-1. 马的遍历

题目描述

有一个 $n\times m$ 的棋盘，在某个点 $(x,y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 $n,m,x,y$。

输出格式

一个 $n\times m$ 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 $-1$）。

样例输入

3 3 1 1 

样例输出

0 3 2 3 -1 1 2 1 4 

提示

对于全部的测试点，保证 $1\le x\le n\le 400$，$1\le y\le m\le 400$。

#include<bits/stdc++.h> using namespace std; const int X[]={ 
                1,1,2,2,-1,-1,-2,-2}; const int Y[]={ 
                2,-2,1,-1,2,-2,1,-1}; int n,m,sx,sy,ans[405][405],qx[],qy[]; void bfs() { 
                 int h=1,t=1; qx[h]=sx; qy[h]=sy; ans[sx][sy]=0; while(h<=t) { 
                 int x=qx[h]; int y=qy[h]; for(int i=0;i<8;i++) { 
                 int x_=x+X[i]; int y_=y+Y[i]; //... } h++; } } int main() { 
                 //... } 

4-2. 靶形数独

题目描述

输入格式

一共 $9$ 行。每行 $9$ 个整数（每个数都在 $0\sim 9$ 的范围内），表示一个尚未填满的数独方格，未填的空格用“$0$”表示。每两个数字之间用一个空格隔开。

输出格式

输出共 $1$ 行。输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数 $-1$。

样例输入 1

7 0 0 9 0 0 0 0 1 1 0 0 0 0 5 9 0 0 0 0 0 2 0 0 0 8 0 0 0 5 0 2 0 0 0 3 0 0 0 0 0 0 6 4 8 4 1 3 0 0 0 0 0 0 0 0 7 0 0 2 0 9 0 2 0 1 0 6 0 8 0 4 0 8 0 5 0 4 0 1 2 

样例输出 1

2829 

样例输入 2

0 0 0 7 0 2 4 5 3 9 0 0 0 0 8 0 0 0 7 4 0 0 0 5 0 1 0 1 9 5 0 8 0 0 0 0 0 7 0 0 0 0 0 2 5 0 3 0 5 7 9 1 0 8 0 0 0 6 0 1 0 0 0 0 6 0 9 0 0 0 0 1 0 0 0 0 0 0 0 0 6 

样例输出 2

2852 

提示

• 对于 $40\%$ 的数据，数独中非 $0$ 数的个数不少于 $30$；
• 对于 $80\%$ 的数据，数独中非 $0$ 数的个数不少于 $26$；
• 对于 $100\%$ 的数据，数独中非 $0$ 数的个数不少于 $24$。

#include<bits/stdc++.h> using namespace std; const int PTS[15][15]={ 
                 { 
                 6,6,6,6,6,6,6,6,6}, { 
                 6,7,7,7,7,7,7,7,6}, { 
                 6,7,8,8,8,8,8,7,6}, { 
                 6,7,8,9,9,9,8,7,6}, { 
                 6,7,8,9,10,9,8,7,6}, { 
                 6,7,8,9,9,9,8,7,6}, { 
                 6,7,8,8,8,8,8,7,6}, { 
                 6,7,7,7,7,7,7,7,6}, { 
                 6,6,6,6,6,6,6,6,6}}; struct node{ 
                  int s,h; }zr[15]; int a[15][15],ans=-1; bool h[15][15],l[15][15],g[15][15]; bool cmp(node x,node y) { 
                  //... } int f() { 
                  int res=0; for(int i=1;i<=9;i++) { 
                  for(int j=1;j<=9;j++) { 
                  res+=PTS[i-1][j-1]*a[i][j]; } } return res; } void dfs(int now,int x,int y,int s) { 
                  //... } int main() { 
                  //... return 0; } 

4-3. 生活大爆炸版石头剪刀布

题目描述

输入格式

第一行包含三个整数：$N,N_A,N_B$,分别表示共进行 $N$ 次猜拳、小 A 出拳的周期长度，小 B 出拳的周期长度。数与数之间以一个空格分隔。
第二行包含 $N_A$ 个整数,表示小 A 出拳的规律,第三行包含 $N_B$ 个整数,表示小 B 出拳的规律。其中，$0$ 表示“剪刀”，$1$ 表示“石头”，$2$ 表示“布”，$3$ 表示“蜥蜴人”，$4 $表示“斯波克”。数与数之间以一个空格分隔。

输出格式

输出一行，包含两个整数，以一个空格分隔，分别表示小 A、小 B 的得分。

样例输入 1

10 5 6 0 1 2 3 4 0 3 4 2 1 0 

样例输出 1

6 2 

样例输入 2

9 5 5 0 1 2 3 4 1 0 3 2 4 

样例输出 2

4 4 

提示

对于$100\%$的数据，$0<N\le 200,0<N_A\le 200,0<N_B\le 200$ 。

#include<bits/stdc++.h> using namespace std; const int A[5][5]={ 
                  { 
                  0,0,1,1,0},{ 
                  1,0,0,1,0},{ 
                  0,1,0,0,1},{ 
                  0,0,1,0,1},{ 
                  1,1,0,0,0}}; int main() { 
                   //... for(int i=0;i<n;i++) { 
                   ans1+=A[a[i%na]][b[i%nb]]; ans2+=A[b[i%nb]][a[i%na]]; } //... return 0; } 

5. 打表优化

有时，打的表代码长度很长，导致 MLE。通常我们有以下的优化：

• 部分打表。对于可以在规定时间计算的答案，我们直接算；其余的输入的数均打成一个表。
• 十六进制优化。如果输出的是数字，我们可以对部分表进行十六进制的转换以缩短代码长度（具体方法参见 洛谷 P8115）。类似地，我们甚至可以三十六进制优化。
• 分段打表。也是比较常用的方法，要有分块基础。与分块类似，将答案分成若干块，对于每一块先计算答案。最后输出时利用与分块类似的做法进行处理答案（详见 OI Wiki）。
• 差分优化。类似十六进制优化。
• 二次差分优化。
• ……

CSP 2022-J2/S2 将至，愿大家考出好成绩！