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

### 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 函数。 ```cpp 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 系统的编译方法，其它系统大同小异。 一般而言，题目会给出一个[交互库源代码](https://www.luogu.com.cn/paste/uimmq4nj)，在得到这个代码后，请将其保存至本地，与选手代码存放于同一目录下。 如果您已经将 g++ 所在目录添加至系统的环境变量，可以将上述代码保存至任意位置（但是同样要求存放于同一目录下），否则请保存至 g++ 所在的目录下，或[添加环境变量](https://jingyan.baidu.com/article/1974b28973bfa1f4b1f774bd.html)。 - 需要指出的是，如果您按照上面的教程添加环境变量，不需要另行下载编译器，直接使用您电脑上已有的 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` 的可执行文件。如果编译错误，命令行会给出错误信息。 \*：打开命令行的方法有两个： 1. 按住 shift 后在对应文件夹空白处按右键，会有「在此处打开 powershell（或命令行/cmd）窗口」选项，单击即可。如果您打开的是 powershell，请输入 `cmd` 命令打开对应目录下的命令行。 2. 按 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` 即可再次运行一次可执行程序。 如果源代码经过了修改，请使用上述命令重新编译一遍程序。