题解 P1947 【猜数（交互测试题）】

· · 题解

好了，你谷终于支持交互题了呢...

这篇文章不仅仅是这道题的题解，同时也是一篇交互题的教程。笔者将在这道题的基础上，为各位详细叙述 stdio 交互和 grader 交互的实现方法和相关注意事项。

先就这道题本身谈起。

算法概述

毫无悬念这是一个二分的经典题目。

设当前数字的可能区间为 [L,R]，我们取 mid=\left \lfloor \dfrac{L+R}{2} \right \rfloor，如果猜的偏大，说明答案在 [L,mid-1] 范围内，否则在 [mid+1,R] 区间内。

显然这样做的时间复杂度为 O(\log n)。

grader 交互

本题采用 grader 交互，这意味着你需要实现题目中给定的函数，在编写过程中可以调用题目中给出的函数进行交互。

NOI 系列赛的交互题均采用 grader 交互方式。

// Problem : P1947 猜数（交互测试题）
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P1947
// Memory Limit : 125 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

extern "C" int Seniorious(int x);//函数声明
extern "C" int Chtholly(int n,int c)
{
 int l=1,r=n;
 while(1)
 {
  int mid=(l+r)>>1;
  int res=Seniorious(mid);
  if(res==1)r=mid-1;
  else if(res==-1)l=mid+1;
  else return mid;
 }
}

洛谷的 grader 交互机制与其他 OJ 略有差别，这里简单说明一下：

  1. 几乎所有的 grader 交互题都要求选手程序包含一个指定的头文件，而在洛谷，因为一些特殊原因，选手不需要，也不应该包含这个头文件。
  2. 也正是因为这个原因，为了确保程序能正常编译，选手需要在程序开头添加一些函数声明语句（这些函数都是交互库中可以供选手调用的函数）。

当然不同的题目有不同的要求，每道题的具体交互要求都在题目中有详细叙述。与原题有差别的地方我们也会详细标注。

grader 交互的本地调试

一般情况下，grader 交互会给你下发一个样例交互库，你可以利用这个交互库进行本地测试。

我们设交互库文件名为 grader.cpp，选手代码为 code.cpp。

则可以在命令行运行这条命令进行编译：

g++ grader.cpp code.cpp -o code

接下来你就可以利用题目中的样例测试了。

需要注意的是，样例交互库与最终评测时用的交互库不同，你的实现不应该依赖于交互库实现。

stdio 交互

在 ICPC 竞赛和 Codeforces 等平台上，选手需要通过输入输出与交互器进行交互。

具体来说，选手将询问等操作通过标准输出进行输出，并从标准输入中读取反馈信息。

还是以这个猜数题为例子：

交互器想了一个数字，你需要猜测这个数。

你的程序会读入两个整数 n,c，代表数的范围为 [1,n]，且你最多可以猜 c 次。

你可以向交互器输出一个数 x 执行猜测操作。

执行猜测操作后，你可以从标准输入中读入一个整数，表示猜测结果（设答案为 k）：

  • 若 k \lt x，则为 1；
  • 若 k \gt x，则为 -1；
  • 若 k = x，则为 0，此时你需要立刻终止你的程序。

如果你猜测的次数超过了 c 次，则交互器会返回 -2，你在读取到这个结果后应该立刻终止你的程序。

下面是这道题的一个实现：

// Problem : P1947 猜数（交互测试题）
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P1947
// Memory Limit : 125 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
using namespace std;
int main()
{
 int n,c;
 cin>>n>>c;
 int l=1,r=n;
 while(c--)
 {
  int mid=(l+r)>>1;
  cout<<mid<<endl;
  cin>>res;
  if(res==1)r=mid-1;
  else if(res==-1)l=mid+1;
  else return 0;
 }
 return 0;
}

在 stdio 交互中，由于输出存在缓冲问题，你需要在输出后立刻刷新缓冲区。

对于使用 cin/cout 的选手，在输出 endl 的时候会自动刷新缓冲区。

而对于使用 scanf/printf 的选手，你可以通过 fflush(stdout) 来执行刷新缓冲区操作。

练习题

好了，想必你已经熟练掌握交互题了，来做两道题小试牛刀吧！