题解 P1947 【猜数(交互测试题)】

2020-04-22 20:29:17


我们首先观察数据范围:

$2\leq n\leq 10^6$, $\min(20,n-1)\leq c\leq n$

我们发现,这个数据范围已经暴露了本题的解法:我们对 $10^6$ 取个以2为底的对数,发现最终的值小于 $20$ 且接近 $20$。所以我们要在 $O(\log_2n)$ 的复杂度内解决这题。

考虑使用二分的思想。

然后我们发现这是一个非常明显的二分答案题。

于是我们就愉快的A了。

extern "C" int Seniorious(int);
extern "C" int Chtholly(int n,int c){
    int l=1,r=n,mid,k;
    while(1){
        k=Seniorious(mid=((l+r)>>1));
        if(k==0)return mid;(k>0?r:l)=k>0?mid-1:mid+1;
    }
}

这里给出蒟蒻曾经想到的倍增思想。但是发现它常数有点大...

如果有哪位神仙用这个思想A了记得教教蒟蒻/kel

extern "C" int Seniorious(int);
int f[1000001],vis[1000001];
int check(int x){return vis[x]?f[x]:vis[x]=1,f[x]=Seniorious(x);}
extern "C" int Chtholly(int n,int c){
    int i=1,delta=1;
    while(1){
        if(check(i)==0)return i;
        while(check(i+delta)==1)delta>>=1;
        i+=delta;delta<<=1;
    }
}