Luogu6982

Luogu6982 [NEERC2015] Jump

Description

有一个长为 的 串 。

你可以询问 次，每次可以任意给出一个长为 的 串 。

如果 与 有恰好 位或 位匹配，系统就会返回匹配的位数；否则返回 。

求串 。

。

Sol

思路非常清奇的小清新思维题。

我们首先考虑如何在得到一个有 位匹配的串的情况下求出完全匹配的串。

考虑到任意选取两个元素，它们的匹配状态只有相同和不同两种，因此我们使 作为“标杆”，然后对于后面的所有 都询问同时翻转 后的 （每次询问互不影响）。如果得到 ，那么说明 正确性相同，否则正确性不同。

这样我们就可以处理出任意位与第一位正确性是否相同，此时再分别假设第一位是否正确来推出整个串即可推出完全正确的串。这样最坏需要询问 次。

此时问题变成了如何在 次以内找到一个恰好有 位匹配的串。

看起来完全没法做，但是考虑恰好 位匹配的串有 个，则如果每次随机一个串不是 位匹配的概率就是 ，这个东西的 次方非常小，因此直接随机 串询问即可。

记得清缓冲区。

Code

非常丑陋。

#include<bits/stdc++.h>
using std::vector;
typedef vector<int> vi;
typedef long long ll;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}

int main(){
    int n=read();
    int ans=0;
    vi a(n+1),b(n+1);
    std::mt19937 rng(188716);
    while(ans!=n/2){
        for(int i=1;i<=n;++i)a[i]=rng()&1;
        for(int i=1;i<=n;++i)printf("%d",a[i]);
        puts("");fflush(stdout);
        ans=read();
        if(ans==n)return 0;
    }
    for(int i=2;i<=n;++i){
        a[i]^=1,a[1]^=1;
        for(int i=1;i<=n;++i)printf("%d",a[i]);
        puts("");fflush(stdout);
        ans=read();
        if(ans==n)return 0;
        if(ans==n/2)b[i]=1;
        else b[i]=0;
        a[i]^=1,a[1]^=1;
    }
    for(int i=1;i<=n;++i)if(b[i]==1)a[i]^=1;
    for(int i=1;i<=n;++i)printf("%d",a[i]);
    puts("");fflush(stdout);
    ans=read();
    if(ans==n)return 0;
    else{
        for(int i=1;i<=n;++i)a[i]^=1;
        for(int i=1;i<=n;++i)printf("%d",a[i]);
        puts("");fflush(stdout);
        ans=read();
        if(ans==n)return 0;
    }
    return 0;
}