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

这是一道经典的交互入门题。 首先明确交互题所需要的提交的代码的格式： ```cpp #include<cstdio>//如果您需要头文件，那么可以像普通程序一样在程序开头包含这些头文件 extern "C" int Seniorious(int);//交互库提供的函数请在程序开头声明定义 extern "C" int Chtholly(int n, int OvO)//题目需要实现的函数请在程序里进行实现 { return 0;//这里只是一个例子，具体内容请自行实现 } ``` ## 解法1 对于前$30\%$的数据，发现我们可以猜$n-1$次，那么我们就对$1$至$n-1$范围内的数都猜一遍，如果猜对了就返回，若果这个范围内的数都猜完了，仍然没有猜对，那么答案就是$n$了。 总共需要$O(n)$次的调用，期望得分$30$分。 实现： ```cpp extern "C" int Seniorious(int); extern "C" int Chtholly(int n, int OvO) { for(int i=1;i<n;++i) if(Seniorious(i)==0) return i; return n; } ``` ## 解法2 由于题目提供的函数不仅能告诉我们是否猜中，还能告诉我们要猜的数和我们猜的数的大小关系，所以我们可以使用二分法。 通过每次猜答案可能的范围内正中间的那一个数，如果猜对了直接返回，否则就把答案可能的范围缩小一半。 总共需要$O(\log n)$次的调用，足以通过本题。 实现： ```cpp extern "C" int Seniorious(int); extern "C" int Chtholly(int n, int OvO) { int l=1,r=n; while(r>l) { int mid=(l+r)/2; int res=Seniorious(mid); if(res==0)return mid; if(res==1)r=mid-1; else l=mid+1; } return l; } ``` ## (*)解法3 **本解法仅供有兴趣的读者阅读。** `algorithm`头文件中提供了`STL`的二分函数`lower_bound`，作用是通过二分找到一段已排好序的数组中第一个大于或等于待查找数的位置。 本题可以通过此函数求解，调用次数也为$O(\log n)$。 实现： ```cpp #include <algorithm> using namespace std; extern "C" int Seniorious(int); struct SpecialInt//通过定义结构体来自定义比较函数 { int num;//如果这个数已知，那么num为这个数，否则为-1 }a[1000000+1]; bool operator<(const SpecialInt s1,const SpecialInt s2)//比较两个数，其中一个数可能是要猜的数（用-1标记） { if(s1.num!=-1 && s2.num!=-1)return s1.num<s2.num;//如果两个数均为已知，直接比较 if(s1.num==-1) return Seniorious(s2.num)==1;//s1未知，通过询问s2得出大小关系 else return Seniorious(s1.num)==-1;//s2未知，通过询问s1得出大小关系 } extern "C" int Chtholly(int n, int OvO) { for(int i=1;i<=n;++i)a[i].num=i;//初始化1至n的数 SpecialInt k; k.num=-1;//要猜的数用-1标记 SpecialInt *p=lower_bound(a+1,a+n+1,k);//找到第一个大于等于要猜的数的位置 return p->num;//返回该位置的值 } ```