一般 oi 场上的交互题都是使用 Grader 交互(cf 是 stdio 交互)。本文讲解一下怎么做交互题,评测交互题。
怎么做
基本知识
题目会给你几个函数接口,一般作为询问的方式。出题人会写一个 grader.cpp 里面就包含了这几个函数。
调用 grader 里面的函数的方法是:加上题目给的头文件/在前面声明要调用的函数(洛谷上用)。
而你要实现一个函数来完成出题人的问题(没有主程序),grader 中有主程序,也就是你完成的是 grader 中的一个函数。
以P1947 猜数为例。
题目上告诉你只用实现 一个函数 Chtholly
来猜数。每次可以调用一个叫 Seniorious
的函数询问是否大于一个数 \(x\)。
题目下方会给一个 grader,可以在调试中发挥作用(后文会讲到)。
此题的代码很好写:
#include <cstdio>
extern "C" int Seniorious(int); // 在这里需要声明一次交互库给出的函数。
extern "C" int Chtholly(int n, int OvO) {
int ans = 1;
for (int l = 1, r = n, mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) if (Seniorious(mid) >= 0) {
r = (ans = mid) - 1;
} else {
l = mid + 1;
}
return ans;
}
洛谷的交互是用 extern,extern可以置于变量或者函数前,以标示变量或者函数的定义在别的文件中,提示编译器遇到此变量和函数时在其他模块中寻找其定义。
简单来说就是这个函数在 grader 中被 extern 定义过,可以使用 grader 中的这个函数。而你实现的这个函数也加上的 extern 是因为 grader 也要调用这个函数。
当它与"C"一起连用时,如: extern "C" void fun(int a, int b);则告诉编译器在编译fun这个函数名时按着C的规则去翻译相应的函数名而不是C++的,C++的规则在翻译这个函数名时会把fun这个名字变得面目全非,可能是 fun@aBc_int_int#%$ 也可能是别的,这要看编译器的"脾气"了(不同的编译器采用的方法不一样),为什么这么做呢,因为C++支持函数的重载。
但赛场上一般是申明头文件就可以实现。
如 NOI2019」I 君的探险,申明 #include "explore.h" 就可以调用了,非常方便。
本地调试
在正规 oi 考试中会给你 grader.cpp 以及头文件的 C 文件。把你写的 cpp 文件和它们放在一个文件下:
如某次模拟测试,要求实现的 cpp 叫 forge,头文件叫:forge.h。
然后在此目的下打开 cmd,输入:
g++ forge.cpp forge.h grader.cpp -o forge.exe
然后会得到一个 exe 文件,打开它输出样例,要想看到答案一定要在 grader.cpp 中写一个 freopen 来输出答案。
打开 .out 文件即可得到答案,可以用它来调试。
怎么思考交互题
大概分为两种:答案不变与答案改变,两种的思考方式不一样。还有的题看着像静态的实则是动态的。
就如猜数,有些出题人会把答案设为动态的,根据你的询问来改变答案,只要保证答案符合所有询问即可,如果暴力枚举数字就一定要询问 \(O(n)\) 次才得到答案。
所以许多交互题要看成博弈题来做。
当然还有的出题人为了强制在线才出的交互题。
评测
得到数据后用 lemonlime/lemon 测交互题。
这里假设对 lemon 测传统题已经了解。
交互库路径与名称都是那个头文件,而接口实现路径是那个 grader.cpp。
记住一定要勾选:定向到标准输入/输出。
在 data 中不只要放测试点,还有 garder.cpp 以及头文件的 C 文件。
最后测试即可。
后言
如果要自己编写 grader.cpp 一定要防止选手通过一些别样的手段来 AC 这到题。
下发的 grader.cpp 一定要与真实评测时的 grader.cpp 不一样,好的 grader 比选手写的还要长。
参考资料:
- Authentic_k:函数式交互题的本地测试方式
- chao_yu:C/C++中extern关键字详解
- oi wiki 交互题板块。