蓝桥杯(OI)赛制技巧：对拍

视频讲解

众所周知，OI赛制每道题提交之后都没有任何反馈，不会返还任何评测信息因为比赛的时候压根就没法评测，类似于你数学考试做卷子，考试的时候可以随便更改你写的内容等到考试结束就要交卷然后批改过几天才给分。 那当你一道题写完后，不知道自己是否是对的，自己也测了很多组数据，干瞪眼看也看不出来啥错的时候这时候就需要对拍来帮你验证自己写的是否正确，对拍简单的说就是写了一个简易得评测器。 对拍由三部分组成，一个是你准备交上去的程序，我们称为待测程序，一个是我们写的一个评测程序，通常是暴力写的，一定要保证他是对的，即使性能不好，还有一个就是随机生成数据的程序，接下来就吧随机生成的数据传给待测程序和评测程序，然后将他俩的结果进行比对，如果一样那大概率你写的这个就是对的，如果不一样那肯定就是错的（前提是你写的评测程序要是对的）。 这里说一下待测程序和评测程序区别，有些人可能会有疑问既然评测程序要保证是对的那为啥不直接交评测程序上去，这是个误区，评测程序是要保证对的但他的性能一般，举个例子，比如有个题数据量是1e6，你写了一个O(NlogN)的算法，但是不确定这个是不是对的，所以你写了一个暴力评测程序，因为是暴力写的所以正确率很高但是只能处理1e3的数据，所以我们就生成一些1e3以内的数据来用评测程序去验证你写的这个待测程序正确性，当然也不一定非得是暴力程序只要保证他一定是对的就行，性能无所谓当然越高越好这样能测的数据范围也越大，常见的有:

DFS(爆搜)测DP

Floyd测Dijkstra

Bellman-Ford测SPFA(已死勿扰）

Prim测Kruskal

…(挺多的其实）

那接下来就拿一道真题举个例子

真题链接

欢迎来我校OJ目前正在收录所有蓝桥杯历年真题已经收录了很多了 这里说一下打程序设计竞赛的时候看到一个题得一个分析切入点就是从数据量去反推他的时间复杂度，然后反推他可能涉及的算法。

yxc大佬总结的经验,一般ACM或者笔试题的时间限制是1秒或2秒。 在这种情况下，C++代码中的操作次数控制在 1e7∼1e8 为最佳。 下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

时间复杂度

常用算法

N≤30 => 指数级别

dfs+剪枝，状态压缩dp

N≤100 => O(N3)

floyd，dp，高斯消元

N≤1000 => O(N2)，O(N2logN)

dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

N≤10000 => O(N∗√N)，

块状链表、分块、莫队

N≤100000 => O(NlogN)

各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分

N≤1000000 => O(N)以及常数较小的 O(NlogN) 算法

单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)的做法：sort、树状数组、heap、dijkstra、spfa

N≤10000000=> O(N)

双指针扫描、kmp、AC自动机、线性筛素数

N≤1e9=> O(√N)

判断质数

N≤1e18=> O(logN)

最大公约数，快速幂, 二分

N≤1e1000 => O(k)

高精度加减乘除

N≤10100000=> O(logK×loglogK)

k表示位数，高精度加减、FFT/NTT

比如一道题数据量1e6那80%就是O(N)或者O(NlogN)这种时间复杂度，那可能设计的算法就那些再结合题分析就可以缩小设计算法范围可以帮助你去解决一道题。 这个题的思路也不需要过多的讲主要是说一下对拍咋写，视频里也说了我这里就贴一下模板代码

待测程序模板：

#include