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

一扶苏一

2020-04-19 02:18:15

题解

Analysis

这是一道交互试机题。

题目是经典的猜数问题，可以通过二分答案的方式来求得所求。具体的，首先设答案区间为 [1, n]，然后询问区间中值 m = \left\lfloor\frac{1 + n}{2}\right\rfloor 与 k 的大小关系，如果 k \leq m，则答案显然不会比 m 大，则将答案先设为 m，再询问区间 [1, m - 1]，否则不更新答案，询问区间 [m + 1, n]。

迭代进行，当答案区间为 [l, r] 时，询问 m = \left\lfloor\frac{l + r}{2}\right\rfloor 与 k 得大小关系，如果 k \leq m，则将 r 置为 m - 1，否则将 l 置为 m + 1。

可以发现，每次进行查询，答案区间的长度减少至少一半，因此只会进行至多 \log_2 n 次询问。而 \log_2 n < 20，因此可以在 20 次询问内求出答案。

Code

在实现时，交互库提供了函数 Seniorious，在选手程序中需要先声明再调用。

此类交互题只需要选手实现题目所要求实现的函数，选手不需要也不应该实现 main 函数。

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;
}

Note

下面说明应该怎么在本地调试所提交的程序。

由于本机是 Windows 10 系统，这里只说明 Win 系统的编译方法，其它系统大同小异。

一般而言，题目会给出一个交互库源代码，在得到这个代码后，请将其保存至本地，与选手代码存放于同一目录下。

如果您已经将 g++ 所在目录添加至系统的环境变量，可以将上述代码保存至任意位置（但是同样要求存放于同一目录下），否则请保存至 g++ 所在的目录下，或添加环境变量。

需要指出的是，如果您按照上面的教程添加环境变量，不需要另行下载编译器，直接使用您电脑上已有的 g++ 即可。也即直接从第二步操作即可。

下面不妨设交互库源代码文件名为 interactive_lib.cpp，选手代码名为 mycode.cpp。

这张图片里，已经将两个代码存放于 C:\Users\HP\Downloads\data(22) 目录下。

然后打开对应目录下的命令行*，将两个程序一起编译，生成一个可执行文件。例如，在命令行中输入 g++ interactive_lib.cpp mycode.cpp -o OvO.exe -std=c++14 即可生成一个名为 OvO.exe 的可执行文件。如果编译错误，命令行会给出错误信息。

*：打开命令行的方法有两个：

按住 shift 后在对应文件夹空白处按右键，会有「在此处打开 powershell（或命令行/cmd）窗口」选项，单击即可。如果您打开的是 powershell，请输入 cmd 命令打开对应目录下的命令行。
按 win+R 后输入 cmd 打开命令行，然后输入 cd 路径 命令，例如上述例子可以输入 cd C:\Users\HP\Downloads\data(22)。特别的，如果目标路径与当前路径（当前路径会显示在 cmd 每行的开头）的盘符不同，需要先输入 X: 切换盘符，然后输入 cd 路径，其中 X 表示目标路径的盘符。

例如上图中，打开 cmd 时当前路径为 C:\Users\HP，我试图切换至 D:\Fusu\cpp，则需要首先输入 D: 切换盘符，然后输入 cd D:\Fusu\cpp 来更改目录。

特别提醒：如果生成可执行文件以前已有同名文件，执行上述命令后会直接覆盖以前的同名文件，因此编译前请确定没有重要的同名文件在该目录下。例如，如果该目录下有一个被我命名为 OvO.exe 的 TXQQ 启动程序，则编译后生成的 OvO.exe 会直接覆盖启动程序，该程序无法找回。特别的，如果您在 g++ 所在目录下进行该编译，请格外注意生成的可执行文件名不是该目录下任何一个可执行文件的名字。例如，将上述命令中的 OvO 改成 g++ 则会造成灾难性的后果。

编译选项添加 -std=c++14 是因为在洛谷上，交互库是以 cpp14 标准进行编译的。如果您的编译器不支持 cpp14 标准的话，请将 14 改成 11，如果代码和交互库均未用到 cpp14 有关特性的话，可以编译成功。

生成可执行文件后，在命令行中输入 OvO.exe，即可调用该可执行文件，继续输入样例输入，即可得到程序输出。

在源代码没有被修改时，如果要测试多个样例，无需重新编译，直接在命令行中输入 OvO.exe 即可再次运行一次可执行程序。

如果源代码经过了修改，请使用上述命令重新编译一遍程序。