题解 P6982 【[NEERC2015]Jump】

Star_Cried · 2020-12-08 10:17:16 · 题解

P6982 [NEERC2015]Jump

题意

给你一个未知的 01 串，每次可以输出询问一个 01 串，如果该串中正确的个数刚好等于 n 或者 n/2 ，将会返回相应的答案，否则会返回 0 。求出这个串。（询问次数不大于 n+500 )

思路

先无视询问次数，我们来想一下确定性算法怎么做。

第一步，我们来试着找出 n/2 正确的串。

首先，我们设一个全 0​ 串，每次修改最左边的 0 为 1，在这至多 n 次询问中，我们一定能找到一个有 n/2 位正确的串。

• 正确性证明：假设全 0 时有小于 n/2 位正确，那么最糟情况，也就是变成全 1 时一定有多于 n/2 位正确；反之亦然。我们每次只改变一位的正确性，也就是说每次正确的位数只会改变 1，这样在移动的过程中一定会有一个情况恰好 n/2 位正确。

第二步，我们来找到正确的串。

我们固定一个位置，每次询问将该位置和其他一个位置取反。显然：若返回的答案为 n/2 ，那么说明固定位置和这个位置的正确性是相反的。我们这样询问固定位置和其他每一个位置，就能够得到包含所有位置的两个正确性相反的集合。然后，我们将这个得到的 01 串和取反后的串询问，找到正确的输出即可。

于是我们得到一个询问次数为 2n 的确定性算法。

过不了。怎么办呢？不要伤心，不要心急！然后我们发现第一步我们随机选择的正确率是挺高的。询问499次，每次询问有 \frac{\tbinom{\frac{n}{2}}{n}}{2^n} 的几率询问到 n/2 正确的串，询问499次后，发现这个几率非常大，用电脑算出来是 0.99997 ……于是我们就做完了。

实现

记得清空缓冲区。下面的代码使用了阴间的bitset实现，常数挺大。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<bitset>
#include<cstdlib>
#include<ctime>
using namespace std;
inline int read(){
    int w=0,x=0;char c=getchar();
    while(!isdigit(c))w|=c=='-',c=getchar();
    while(isdigit(c))x=x*10+(c^48),c=getchar();
    return w?-x:x;
}
namespace star
{
    int n,ans;
    bitset<1002> a,b;
    inline void write(bitset<1002>& x){
        for(int i=0;i<n;i++) cout<<x[i];
        cout<<endl;
    }
    inline void work(){
        srand(time(0));
        ios::sync_with_stdio(false);
        cin>>n;
        for(int i=1;i<=499;i++){
            for(int j=0;j<n;j++) a[j]=rand()%2;
            write(a);
            cin>>ans;
            if(ans==n)return;
            else if(ans==n/2)break;
        }
        a[0]=a[0]^1;
        for(int i=1;i<n;i++){
            a[i]=a[i]^1;
            write(a);
            cin>>ans;
            b[i]=a[i]^(ans==n/2);
            a[i]=a[i]^1;
        }
        b[0]=a[0];
        write(b);
        cin>>ans;
        if(ans==n)return;
        b.flip();
        write(b);
        cin>>ans;
    }
}
signed main(){
    star::work();
    return 0;
}