OI的非切题相关内容

LaTeX

比较基础的 $\LaTeX$ 语法我已经在这篇博客里面写出了。对于写题解、出题面之类已经足够，对于出一套题面并整合成 pdf 文件这类需求，需要额外在网上查阅相关辅助资料。~~或者向他人寻求题目模板~~。

题面和题解通常都需要用规范美观的 $\LaTeX$ 和 markdown 排版。

markdown

比较基础的 markdown 已经在我的博客写出了。写题解、出题之类日用完全足够。当然改颜色之类没有什么必要提及，至于内嵌 HTML，首先你得会……

NOILINUX2.0

新版 NOILINUX 非常高级，它基于 Ubuntu20.04。最主要的变化就是 IDE 变多了。对于不喜欢不习惯用 Emacs 的人来说，除了 gedit 有了更多选择。主要（最吸引人的）多了 sublime，vscode。另外的新增，比如 codeblock 之类，一般不会用到。

其中 sublime 是没付钱的英文版本。vscode 是除编译插件（C++，C，Pas，Python）外没有任何其他插件（包括 code runner）的英文版本。这两个编辑器貌似都是自带括号自动补全的，如有不适自行调整。

支持了 Python3，对拍方面会更加方便。~~前提是会这个语言~~

其次就是 C++ 的兹瓷版本成功进化到了 C++14，值得注意的是 C++14 算是一个跑得比较快的版本，再加上最近这些比赛评测的时候编译选项都有 -O2，说明 CCF 正尽量不让常数问题成为一个很大的阻碍。编译的时候在编译选项里添加 -std=c++14 就可以用 C++14 的标准编译。auto,__int128,__gcd 等等功能现在都不会 CE 了！（主要是 int128，不过估计 CCF 后续也不会出什么高精度题了）。

当然也有一些东西在 C++14 里用就很危险了，比如 C++14 弃掉的 gets，还有 C++14 停用 C++17 废除的 random_shuffle。

平时练习可以参考的编译选项：

g++ -o code code.cpp -lm -Wall -O2 -std=c++14

这个编译选项下没有问题，就不会出事了。

不建议自家电脑装机装 NOILINUX，下个 Ubuntu20.04TLS 就已经足够了。

出题

部分内容参考了OI-Wiki，但没有照搬，均带有一点个人主见想法。

题目idea

idea 这方面纯粹都是灵感，大部分的 idea 来源于灵感、游戏、其他题目。不一定什么时候你的 idea 都可以成型成一个题目，也不一定是一个好题。平时出的 idea 大概率具有过恶心/过水/想出了题目想不出怎么做三种情况。

当然，如果先想好算法再出题面，就不会有第三种情况。

你的题目不应该和较为知名的题目重题（即，算法和代码基本相同，如果代码基本一致，但是算法上有很多的推导才能推到这一步，那显然不算重题，但是切掉的人可以双倍经验）。

出题的时候有很多废掉的题是很正常的，例如过水的题目和暂时只有暴力做法的题目。但是没必要直接丢到回收站清空，如果屯起来的话，说不定哪天发现这个题改一改哪个地方可以做。

当然这也提示了大家，如果一个题目要求的内容和题目保证的某个性质完全无关，一般说明去掉这个性质题目的复杂度就会假掉或者不可做，例如HNOI2010平面图判定，如果给定的就是一个一般图，平面图判定是 NP 的，只有其保证存在哈密顿回路，才可以用 2-SAT 做到 $\operatorname{O}(m)$ 解决。

题目定位

这里以出一套 NOIP 模拟题组（四道题）为例说明一下我的个人看法。

不推荐零零散散地出一些难度参差不齐的题目。如果事先有计划地认为我要出一套题目，这个是签到题，这个是杀 AKer 的题……出题会变得更有条理性。

一场比赛，无论多少个题，总会有一个签到题。这里的签到题的难度，应该是适合参赛的人群都能以较快的时间解决的难度。当然可能会有个别考场降智切不出来的例外，但是如果有一定的人都做不出来，这个签到题就不是签到题了。

对于互测赛之类，很多人都喜欢以恶心别人为目标，甚至有四个题三个 DS 一个 DP 的情况，这是绝对不可以的。当然如果你认为本次考试应该加大难度，或者抱着出一套 RP 赛为目的，对签到题的要求就没那么严格。

简单的 DP、分治、模拟，显然的贪心，初中范围内的简单数学题，裸题稍微拐一点弯（而且算法简单）的题，都可以放成签到题，同时签到题码量不宜大，例如不能以没有思维难度为理由放一个鸭棋（大模拟）为签到题。

然后应该放上一至二个较难题。较难题通常具有较难的思维性，不宜码量过大（数据结构之类除外）。应该保证具有一定的梯度，即有些人可以做出来，有些人做不出来，绝对不能放对知识点掌握要求明显高于整套题定位的题，例如 CSP-S 模拟赛放一个最终幻想。无论是数学难度还是实现难度（FFT）都高于比赛难度定位。

具有较强的思维性的 DP、DS、数论图论等等，很多类型都可以作为较难题，码量不以太大，比如 300+ 行之类。

最后应该垫上一个杀 AKer 的压轴题，只要不太变态（而且不是大模拟之类的纯恶心题），怎么恶心怎么来吧。这类题目通常不应该再注重考场上有多少切的人，而应该注重部分分给的是否合理。

总的来说，一套题目的定位，应该是 “ABBC” 式，即 “签到题-较难题-难题-压轴题”。其中较难题和难题在难度上没有明显的界限，可以视为就是两个中难题。

毒瘤和偏题

一套比赛失去了毒瘤，就失去了灵魂。——CZA

这互测赛太**毒瘤了，**出题人。——CZA

我们可以看出：出毒瘤题和做毒瘤题完全是两个概念。

关于一个题目的毒瘤程度，很多 OIER 各执己见。有人认为例如重量平衡树套线段树维护凸包就很毒瘤。我个人觉得这只能代表这个题目难，不是毒不毒瘤的问题。

确切而言，衡量一个题是否毒瘤，应该要从错误做法的得分、题目的思维性和代码等角度综合来看。例如正解没开 longlong 得分 0、std 跑了 990ms 且题目时间限制开 1s，显然就是不合理的。

一个题如果不毒瘤，应该要做到数据有多档部分分（水平不高的人可以拿到分，水平高的人可以拿到高分或者切掉）、部分分设置合理（正解分不能太少也不能太大，各个部分分根据思维和实现难度适当分配分数）、时间空间至少开到 std 的 1.5 倍（std 没有刻意卡常、错误的复杂度的做法应该能被假掉）。

对于一些错误的做法和复杂度假掉的做法，做一批数据卡掉，我是非常支持的。这并不属于毒瘤的范围，而是能体现出题人很细心尽责。毕竟如果数据太水把别人暴力放跑成满分，你自己心里也不舒服。

对于那些题目全是数学推导（且和 OI 无关）或物理推导的东西，或者强行叠加各种东西导致码量极大。这类题目一般不适合出现在 OI 题中，为偏题怪题。出题时因尽量避免。

还例如，一个题目如果让一些本来无关紧要的东西成为了最大的阻碍，比如一个区间加区间求和的线段树裸题，强制在线的敌方让你解一个多项式，显然就是本末倒置，这样的话还不如出一个多项式的题目，把区间加区间求和的线段树板子去掉。

造数据

除非题目保证了数据随机，造一套纯随机的数据是绝对不行的。原因大家心理都清楚，比如树高和树高有关的暴力在随机数据下变成了 $n\log n$ ，保留字符串匹配跑地和 kmp 差不多快……

对于和序列大小关系有关的题，常见的非随机数据做法就是递增递减 $k$ 峰 $k$ 谷。特别的，更多的峰或谷配合较大的数据范围可以有效地卡掉模拟退火等随机做法。

你的数据应该保证可以假掉已知的错解或细节写挂的代码，可以选择构造这类数据，也可以选择对拍（找到能让这个做法 WA 的点为止）。

最好可以手动加几个细节数据，包括但不限于擦边球、（可能存在的话）除以 $0$ 、无脑写过去没有考虑到的情况。比如计算 $a^b\bmod p$ ，不保证 $p$ 是质数的时候，不妨给一个 $a=1,b=0,p=1$ 的数据，想必很多人的快速幂都会被这样的细节卡假（答案是 $0$ 但是代码输出为 $1$ ）；再比如有根树上的问题，保证这个部分分每个点度不超过 $2$ （也就是一条链），但是不保证根节点在链头。

常见叉掉复杂度错误的解法的数据有：一个菊花挂诱导链（一个菊花，一个非正权链，链上每个节点都连一个非正权到菊花，使得 SPFA 做法每次在链上更新一个点都要回去跑一遍菊花）、网格图（也可以卡 SPFA）、蒲公英（一个链和一个菊花组成，根据链和菊花的比重不同，可以叉掉不同的复杂度解法）、根有两个儿子，其中一个儿子有三个儿子，其中一个儿子有四个儿子，以此类推的树（长链剖分变成根号级），二维平面一直往一个区域加点（卡重构写假的 KD-Tree）……等等。

关于批量造一套 .in 文件。如果不会 bat 的话，可以充分利用 freopen 的特性。它传入的第一个参数是一个字符串，代表文件名，通过改变这个传入的字符串，就可以新开一个文件接着造数据：

char in[100]="data01.in";
for(register int id=1;id<=20;++id){
    freopen(in,"w",stdout);
    // 造数据……
    ++in[5];
    if(in[5]>'9'){
        in[5]='0';
        ++in[4];
    }
}

关于批量造一套 .out 文件，可以注意到 C++ 的 main 函数实际上可以传入两个参数，其中一个为 int 类型，一个为 *char[] 类型。当你编译完后进行运行的时候，在 ./code.run 后面就可以输入一些东西表示传参，具体的话，第二个参数存入的是整个输入的字符，可以不管它；第一个参数就是传入的参的“数”（如果传若干整数，则“数”代表有多少个整数）加一。也就是说：

./code.run 1 1 1 1 1 1

此时 main 函数接到的传参的第一个参数，应该是 $6$ ，即参数数量（ $1$ 的个数） $+1$ 。

因此在你的 std.cpp 中做如下操作：

// 省略 std 内容
char in[100]="data00.in";
char ot[100]="data00.out";
int main(int argc,char *argv[]){
    for(register int i=1;i<=argc;++i){
        ++in[5];
        if(in[5]>'9'){
            in[5]='0';
            ++in[4];
        }
    }
    ot[5]=in[5],ot[4]=in[4];
    freopen(in,"r",stdin);
    freopen(ot,"w",stdout);
    // 标算……
}

然后写一个造数据的代码，利用 system 函数，函数中传入一个字符串参数，相当于你在终端输入的指令。

那么造一批（包括 in 和 out）数据的 cpp 代码可以这样写：

#include<bits/stdc++.h>
using namespace std;
const int N=20;// N 为数据组数
char run[10000000]="./std.run                        ";
// 后面全是空格，空格数和你要造的数据组数直接相关，可多不可少。
int main(){
    system("g++ -o makedata.run makedata.cpp -O2");
    system("./makedata.run"); // 先造一批 .in
    system("g++ -o std.run std.cpp -O2");// O2 加速造数据的速度，不管题目要不要开这里都可以开
    int pos=10
    for(register int i=1;i<=N;++i){
        system(run);
        run[pos]='1',run[pos+1]=' ';
        pos+=2;
    }
    return 0;
}

即使不知道 bat 或 python 等其他知识，也可以快乐批量造数据了。

其他细节

题解，要保证适合做这一套题的正常人可以读懂，不宜凭空冒出来一些概念，比如不解释状态直接写转移，或者一个很复杂的转移方程不解释为什么。

std，不宜邪恶码风（比如无缩进等等），不宜有过多冗余部分，调试信息全部注释掉，保证你给别人的 std 不加任何改动就可以直接 AC 你的题。如果自认为题解足够详细，std 可以不加注释解释，加的话不宜过多过杂。

一套题涵盖的知识点，应该要涵盖广泛，除非是专题训练。（比如四个题目里面三个 DS 很明显不合理）

如果有的话，SPJ 和交互库应该保证正确，且不合法的输入都应该能判断出来并且判 WA。

如果不希望题目有任何公开风险，不要放在网上。可以自己出好然后用 lemon 在本地测试自己的题目。

暴力

暴力有两种分类：果断的暴力和优雅的暴力。当然那些过于优雅的暴力（柯朵莉树之类）以至于可以把这个题目切掉的，和本文标题冲突，这里不写。

显然暴力一般是考场上才会写的，平时练习并不会特意地去写一个暴力出来，因此更多的还是要看考场心态等因素。

这里以一个 CCF 的题目为例子简述我对暴力的看法：NOIP2021T2 数列，正解是什么和这里讨论的主题无关，我们只考虑暴力。

给定 $n,m,k$ 和一个长度为 $m+1$ 的正整数序列 $v_0,v_1,\cdots,v_m$ 。

对于一个长度为 $n$ ，下标从 $1$ 开始，每个元素不超过 $m$ 的非负整数序列 $\{a_i\}$ ，其贡献为 $\prod_{i=1}^n v_{a_i}$ ，权值为 $\sum_{i=1}^n 2^{a_i}$ 。

当一个序列的权值满足其二进制表示中 $1$ 的个数不超过 $k$ 时，就会产生贡献。求贡献和对 $998244353$ 取模的值。

对于 $20\%$ 的数据， $n=8,m=9,k\leqslant n$ ；

对于 $50\%$ 的数据， $n\leqslant 30,m\leqslant 12,k\leqslant n$ 。

果断的暴力

虽然大家考场上的策略和做法不尽相同，这里我就直接按照我的考场经历简述一下，T1 开考十分种左右的时候切掉了，剩下的三个题目都已经看过了，剩余时间非常充足，属于考试刚开始没多久的时候。

看到这个题的数据范围，马上对大暴力有了一个复杂度的概念，大体是枚举每一位填什么数，然后判断得到的数是否符合条件。

一般在考试时间明显充足的时候，如果对于一个题一开始没有很好的进展，先写好一个暴力一定不会差的。

因此我很快就干上了一个果断地暴力，先拿到 $20$ 分再说。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=10,mod=998244353;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int calc(int x){
	int res=0;
	while(x){
		++res;
		x-=(x&-x);
	}
	return res;
}

int n,m,k;
int v[max_n];

namespace BUF{
	int ans=0;
    #define int long long
	inline void dfs(int l,int S,int val){
		if(l>n){
			if(calc(S)<=k) ans+=val,ans%=mod;
			return;
		}
		for(register int i=0;i<=m;++i)
            dfs(l+1,S+(1<<i),val*v[i]%mod);
	}
	inline void sol(){
        dfs(1,0,1);
		write(ans);
	}
}

signed main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
	n=read(),m=read(),k=read();
	for(register int i=0;i<=m;++i)
		v[i]=read();
	BUF::sol();
	return 0;
}

注意到暴力的部分被写在一个 namespace 里面，这也是我的习惯，这样子更方便数据分治，对于那种保证某种特殊性质的部分分非常有用。

注意 namespace 里面数组不能开太大，如果较大的话，把 int 改成 static int。

后续就是把别的题目的暴力干出来了。这一份暴力是 $20$ 分。也就是大枚举分。一般而言这样的果断暴力为以下几种中的一个：

阶乘或组合数级别地枚举某个顺序，然后跑一遍计算贡献之类。
二进制或多进制（如本题，实际上是 $m$ 进制）枚举状态，然后跑一遍计算贡献之类。
枚举一个点或位置，或对于每个操作，暴力跑一遍整个图或序列。在图论和数据结构里一般是这种。

通常果断暴力具有好想好写的特点，当然也可能有例外，就是好像不好写的那种，不做举例。一般考场上，对于不会的题目至少都要搞到一个果断分。

优雅的暴力

优雅，永不过时。

写完别的题目暴力我一回来，发现这一档分的 $m$ 明显小于后面的部分分（ $m\geqslant 50$ ），而且 $12$ 这个数字就很适合三进制或者二进制的状压。

然后你可以回去看你的暴力，因为很多时候一个题的高档分是低档分一步一步优化来的。考虑你的搜索能不能在哪个地方状压一下。

然后你就发现把 $l,S$ 放在状态里刚好，数组大小是 $n2^m$ 。那就把原来的暴力备份一遍，就开写呗：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_m=102,max_n=32,mod=998244353;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int calc(int x){
	int res=0;
	while(x){
		++res;
		x-=(x&-x);
	}
	return res;
}

int n,m,k;
int v[max_n];

namespace BUF{
	int ans=0;
	static int f[32][32*(1<<13)];
	inline int dfs(int l,int S){
		if(l>n){
			if(calc(S)<=k) return 1;
			return 0;
		}
		if(f[l][S]!=-1) return f[l][S];
		f[l][S]=0;
		for(register int i=0;i<=m;++i){
			f[l][S]+=dfs(l+1,S+(1<<i))*v[i],
			f[l][S]%=mod;
		}
		return f[l][S];
	}
	inline void sol(){
		memset(f,-1,sizeof(f));
		write(dfs(1,0));
	}
}

signed main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
	n=read(),m=read(),k=read();
	for(register int i=0;i<=m;++i)
		v[i]=read();
	BUF::sol();
	return 0;
}

这个东西，它现在是一个记忆搜，它的 DP 本质就是：记录状态 $f_{i,state}$ 表示考虑到第 $i$ 个位置，此时序列的权值是 $state$ ，可以造成的贡献是多少。转移时枚举这个位置填哪个数字：

f_{i,state}\leftarrow\sum_{j=0}^m f_{i+1,state+2^j}

这样子就写出了一个优雅的暴力，可以拿到 $50$ 分的好成绩。

优雅的暴力通常带有如下几个性质中的至少一个：

对这个题有一个初步的进展，但是这个进展不知道如何突破。
常见算法有： $n^2$ DP，状压 DP，推出一个性质之后暴力维护。
后续更优秀的算法大概率从这里开始一步一步突破得到。

对于不会做的题目，应该要能打多少分打多少分。只要暴力足够优雅，不排除有靠暴力分过线的情况。

平时研究优雅暴力的过程的含金量，应该是和研究正解相当的。

卡常

尤其是分块、KD-Tree 等东西，常数如果较大，就会原地爆炸。这是最根源的卡常的目的。

其次就是让自己考场上的暴力能放跑多一点点哪怕是一个点的分。~~再其次是卡最优解榜一~~

卡常有正常的卡常和不正常的卡常。不正常的卡常比如循环展开等，过于离谱而且对代码阅读影响是很大的，这里我不想说。

时刻注意，打代码的时候一定还是要按照自己的习惯码，切忌边写边搞卡常，不然你样例没过的时候 debug 的样子就会很狼狈。

细节上的卡常有下面几种：

循环变量用 register，可惜的是它从 C++14 起不起到优化作用了。
快读快写，可以在我上面的代码里找到，速度比 scanf,printf 快一些，用于输入输出文件较大的时候。
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0); 使 cin,cout 的用时和 scanf,printf 相当。如果字符串定义的 string，是只能用 cin,cout 的，一般这个时候会用到。
switch 的速度慢于 if-else 慢于三目运算符。
通常数据结构上用 STL 比手写慢。非数据结构的函数有一部分比手写慢，但是例如 sort 等 STL 是快于手写的归并排序或快速排序的。
位运算比四则运算快，但是如果你是把 i+1 写成 i=-~i 这种，搞不好会慢一点。
同一条语句中如果有较多（但不能过多，要合理）的计算，会促进 CPU 并发，略微变快。但是定义中间变量如 tmp 等取代一些重复计算的时候，如果重复计算的次数不多就不需要，如果较多还是搞一个中间变量比较好。
指针比写个存下标的数组快，但是不怎么会用指针的话还是算了吧。
int 是计算速度最快的常用变量类型，当然 bool 可能快一点但是没什么题目保证输入的数字都是 $0$ 或 $1$ 计算也都是 $0,1$ 的计算吧……
短路运算符，让你觉得更不可能满足条件的判断放前面。比如 a>n || a==-inf，如果你的初值全是 -inf，不合法情况是 >n，那不妨改成 a==-inf || a>n。不过卡常效果甚微。
main 函数类型改成 signed，不会 CE，但卡常效果甚微，不过这样改了也很方便你直接 #define int long long。

其他方面的卡常就和写的东西不一样因人而异了：

替罪羊的 $\alpha$ 取 $0.62$ 或 $0.74$ 可能较快，当然根据写的人和方式不同会有较大的改变，个人推荐 $0.75$ ，不管怎么写速度都可观。

来看下面一个代码：

inline bool interv(int mid,int l,int r){
	if(l<=mid && mid<=r) return 1;
	return 0;
}
inline bool check(int x,int i,int j){
	if(!x) return 0;
	if(a[x].l.x<=p[j].x && (interv(a[x].l.y,p[i].y,p[j].y) || interv(a[x].r.y,p[i].y,p[j].y))) return 1;
	if(a[x].r.x>=p[i].x && (interv(a[x].l.y,p[i].y,p[j].y) || interv(a[x].r.y,p[i].y,p[j].y))) return 1;
	if(a[x].l.y<=p[j].y && (interv(a[x].l.x,p[i].x,p[j].x) || interv(a[x].r.x,p[i].x,p[j].x))) return 1;
	if(a[x].r.y>=p[i].y && (interv(a[x].l.x,p[i].x,p[j].x) || interv(a[x].r.x,p[i].x,p[j].x))) return 1;
	if(interv(p[i].x,a[x].l.x,a[x].r.x) && interv(p[i].y,a[x].l.y,a[x].r.y) && interv(p[j].x,a[x].l.x,a[x].r.x) && interv(p[j].y,a[x].l.y,a[x].r.y)) return 1;
	return 0;
}
inline int ask(int x,int id1,int id2){
	if(!x) return 0;
	if(a[x].l.x>=p[id1].x && a[x].r.x<=p[id2].x && a[x].l.y>=p[id1].y && a[x].r.y<=p[id2].y)
		return a[x].sm;
	int res=0;
	if(interv(a[x].x.x,p[id1].x,p[id2].x) && interv(a[x].x.y,p[id1].y,p[id2].y))
        res+=a[x].x.val;
	if(check(ls(x),id1,id2)) res+=ask(ls(x),id1,id2);
	if(check(rs(x),id1,id2)) res+=ask(rs(x),id1,id2);
	return res;
}

这玩意的常数绝对不是你能想象的，而它的本质，只不过是 KD-Tree 上求一个矩形内点的点权和。实测原题这个代码最大的数据点要跑 40s。

如果巧妙地做一点变换，让它判断少一点：

inline bool interv(int mid,int l,int r){
	if(l<=mid && mid<=r) return 1;
	return 0;
}
inline int ask(int x,point i,point j){
	if(!x || a[x].l.x>j.x || a[x].r.x<i.x || a[x].l.y>j.y || a[x].r.y<i.y) return 0;
	if(a[x].l.x>=i.x && a[x].r.x<=j.x && a[x].l.y>=i.y && a[x].r.y<=j.y)
		return a[x].sm;
	int res=0;
	if(interv(a[x].x.x,i.x,j.x) && interv(a[x].x.y,i.y,j.y))
        res+=a[x].x.val;
	res+=ask(ls(x),i,j)+ask(rs(x),i,j);
	return res;
}

显然少了很多 if，实际上这个代码在这个题上最慢的点就不到 2s 了。中间的 $20$ 倍的常数，就是反复调用 $\text{check,interv}$ 函数，且逻辑判断非常多造成的。

通常情况，写成递推会比写成递归常数小。
LCT 是 $\log$ 级数据结构中常数极大的一个，其次是常数大一些的平衡树，再其次为线段树合并，线段树常数也不小；树状数组是常数近乎最小的。

对拍

你应该要准备好三份代码，不一定要按照这里的命名，但是这三个代码都要有：

造数据的代码 make.cpp。
保证正确的一份代码（例如题解或暴力）std.cpp。
你自己想要对拍测试的代码 code.cpp。

并保证这三个代码都开了文件输入输出。

根据前文（出题部分里面写了）所述，system 函数相当于在终端执行了一个指令。众所周知，diff A B -q -b 可以忽略文末回车和空行，并在两个文件不同的时候产生一个返回值（如果两个文件相同，没有返回值，即返回值为 $0$ ）。

因此不难干出这样一个对拍代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    system("g++ -o mak make.cpp -O2");
    system("g++ -o cod code.cpp -O2");
    system("g++ -o std std.cpp -O2");
	int i=0;
	while(1){
		printf("\n");
		++i;
		printf("%d :\n",i);
		system("./mak.r");
		system("./std.r");
		system("./cod.r");
		if(system("diff data.out data.ans -q -b")){
			puts("WA");
			return 0;
		}
		puts("AC");
	}
	return 0;
}

如果想要加个计时，就搞个 clock 函数：

#include<bits/stdc++.h>
#include<time.h>
using namespace std;
int main(){
    system("g++ -o mak make.cpp -O2");
    system("g++ -o cod code.cpp -O2");
    system("g++ -o std std.cpp -O2");
	int i=0;
	while(1){
		printf("\n");
		++i;
		printf("%d :\n",i);
		system("./mak.r");
		system("./std.r");
        double a=clock();
		system("./cod.r");
        double b=clock();
		if(system("diff data.out data.ans -q -b")){
			puts("WA");
			return 0;
		}
		printf("AC, %.2lf ms\n",(b-a)/CLOCK_PER_SEC*1000.0);
	}
	return 0;
}

编译运行，就可以快乐对拍了，直到有 WA 的数据的时候，就是 data.in/ans 这一组数据。造数据的时候数据不宜过大，好在抓到错之后可以手玩。但是大数据也需要拍一些的。

打表

一般而言，适合打表的题目具有几个特征：

题目给定的参数很少，且参数的范围适合打一个不 MLE 的表，比如 NOIP2021T1 单次询问只会询问一个参数，且值域为 $10^7$ 。
模数是固定的，或者模数是个摆设（即不取模也不会爆 __int128）。
暴力很好写，或者推导到一定步骤之后很好办。

打表分为两种：一种是你不知道这个题的做法，而且你的暴力在有限的时间内（一般为考试时间）无法把满分的数据的表做出来，因此只能暴力打表；第二种是你已经推导到一个高级地步了，只需要写一个复杂度可以的打表，就可以满分。

前者就是暴力没啥好说的，重点看后者，特别是怎么把代码压在提交代码的长度限制内。

先来看看这样一个题目：NOIP2021T1 报数。

多组询问，每次给定一个数字 $n$ ，求 $n$ 是否合法，若合法，求下一个合法的数。一个数合法定义为他不能被任何十进制数位带 $7$ 的数字整除。

询问数不超过 $2\times 10^5$ ， $n\leqslant 10^7$ 。

直接打表

考虑这样一个题目的暴力是什么：枚举每个数字，然后判断是否合法，判断方法是：找到所有比它小的带 $7$ 的数字，验证能否整除。

打表的时候还可以用一下 cerr，用法和 cout 是一样的，例如cerr<<cnt<<"\n"，特别的是，即使你开了文件输入输出，cerr 仍然会把内容输出到终端，方便调试。

根据这个思路我们打出一个打表代码，得到所有合法的数字：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}

inline bool calc(int x){
	while(x){
		int tmp=x%10;
		x/=10;
		if(tmp==7) return 1;
	}
	return 0;
}

int cnt;
vector<int> a;

inline bool check(int x){
	int _n=a.size();
	for(register int i=0;i<_n;++i)
		if(x%a[i]==0)
			return 0;
	return 1;
}

signed main(){
	int n=read();
	freopen("biao.txt","w",stdout);
	for(register int i=1;i<=n;++i){
		if(calc(i)){
			a.push_back(i);
			continue;
		}
		else if(check(i)){
			++cnt;
			printf("%d,",i);
		}
	}
	cerr<<"cnt= "<<cnt<<"\n";
	return 0;
}

随便算一下，枚举一个数之前的数字就假设是 $\operatorname{O}(n)$ 的，那么时间复杂度就是 $\Theta(n\times(n-1)\times\frac{1}{2})$ ， $n=10^7+10$ （多打一点点避免问你 $10^7$ 的下一个合法的数字是多少你的表搞不定），代入，大约是 $5\times 10^{13}$ ，你需要 $34$ 小时来运行它。看起来考场上显然不可取。

但是实际上呢？比一个数小的带 $7$ 的数字怎么可能约为 $n$ ，它显然是组合数级别的，而因为最多只有 $8$ 位数字，所以大不到哪里去。事实上，这个代码可以在 $1$ 小时内得到结果。

于是就暴力打表了。

差分表

差分表就是对原来的表（即答案表，直接存答案的表）进行差分，得到一个新表，在答案表中相邻两个数之差不大时，差分表的大小明显小于答案表。将差分表放在提交代码里时，只需要做个前缀和处理就可以转化为原表。

仍然以上面那个题为例子，那个题的答案表打出来一共 $6\text{MB}$ ，你先不说放在代码里能不能交得上去，这个源码大小交上去算不算卡了 CCF 评测都说不清。

如何在已经得到了这个表的前提下，想办法缩小这个表的大小？显然，这个题是不适合分段打表的。

我们随便取表里面的一段，发现：

8042,8044,8045,8048,8049,8053,8059,8060,8065,8069,8080,8081

虽然这里的数字已经达到了 $8000$ （一个数字 $4$ 个字符），但是两个数字的差是很小的，而且都是个位数（一个数字 $1$ 个字符）。为了验证它可以把表大小变得很小，我们再看看后面一段：

368843,368846,368848,368859,368863,368881,368882,368884,368889

相邻的两个数的差仍然是个位数。事实上对于这样数字相对连续的表，出现位数超过 $4$ 的都比较少了，所以表的大小明显缩短。因此不妨写个求差分的代码，把原来的答案表做成差分表：

#include<bits/stdc++.h>
using namespace std;
signed main(){
	freopen("biao.txt","r",stdin),
	freopen("biao2.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int x,last=0;
	while(cin>>x){
		printf("%d,",x-last);
		x=last;
	}
	return 0;
}

在你的提交代码里面里面，对你放进去的这个差分表做一个前缀和处理，就变成答案表了。

分段打表

分段打表就是，我们发现一个表是非常大的，而且差分表无法把它压在一个合适的大小，不过我们可以通过表的一部分，通过复杂度能过的算法得到实际的答案，那么就会之打出一部分情况下的表，一般表的数字个数打成根号级别，即分块表。

相对于前面的打表，分段打表往往更有思维难度，特别是有的题目，对于怎么从一个分段表推出当前输入的数据的答案，需要用到的推导和推正解没什么区别了。

以这个题为例子，我们考虑一下怎么打表：P5388 最终幻想。

求用 $k$ 个 $n-1$ 维超平面可以把一个 $n$ 维超球最多划分为多少块。答案对 $998244353$ 取模。

$n,k\in[1,998244353)$

抛开所有的数学推导（~~我还是打表找规律找到结论然后敲诈勒索数学组骗到做法的~~），我们可以得到一个结论：

Ans=\begin{cases} 2^k&(k\leqslant n)\\ \sum_{i=0}^n\operatorname{C_k^n}&(k>n) \end{cases}

对于 $k\leqslant n$ 的做法，显然快速幂。但是对于 $k>n$ 的做法我们不好打表。最明显的不当就是它有 $n,k$ 两个元素，差分的方法不适合运用上来，而且它呈现一个组合数前缀和的模式，差分数值也会比较大。

洛谷的代码提交上限是 $50\text{KB}$ ，我们尽量压一下。首先得到模数不超过是 $10^9$ ，即一个答案最多为 $9$ 位数，也就是说最多只能记录 $10^4$ 个数字。因此考虑 $n,k$ 都以 $10^7$ 为打表间隔，打一个二维数组的表，刚好 $(\frac{10^9}{10^7})^2=10^4$ 。

现在问题转化为，给定 $\operatorname{C}_n^k$ ，求 $\operatorname{C}_{n+\Delta n}^{k+\Delta k}$ 。 $0<\Delta n,\Delta k\leqslant 10^7$ 。

因为 $\Delta n,\Delta k$ 相对小一些，如果我每次可以根据 $\operatorname{C}_n^m$ ， $\operatorname{O}(1)$ 复杂度求出 $\operatorname{C}_{n+1}^m$ 和 $\operatorname{C}_n^{m+1}$ ，这题就做完了。

\begin{aligned} \operatorname{C}_n^m &=\frac{n!}{m!(n-m)!}\\ &=\frac{\prod_{i=n-m+1}^n i}{\prod_{i=1}^m i} \end{aligned}

分别另 $n\leftarrow n+1,m\leftarrow m+1$ ，分别可以得到：

\operatorname{C}_{n+1}^m=\operatorname{C}_n^m\times \frac{n+1}{n-m+1}\\ \operatorname{C}_n^{m+1}=\operatorname{C}_n^m\times \frac{n-m}{m+1}

因此直接递推就可以了。