题解：P17115 [Algo Beat 009 & MROI-R1] ANDOR

· · 题解

分享一个可以拓展到 2n-4 次操作的做法。

首先可以不看 n 号点，最后剩下的就是 a_n。

然后注意到不同二进制位直接是互不影响的，因此可以按位考虑。

当前只考虑某一位，设 f(x,y) 为 a_x 和 a_y 只看当前这一位的与，g(x,y) 为 a_x 和 a_y 只看当前这一位的或，那么对于一对 x 和 y，f 和 g 只有三种情况:

因此，可以依次询问相邻的点，只要出现过前两种情况就可以确定整个序列（因为任意相邻数的关系都是确定的，确定一个数就可以顺着推出所有数）。

举个例子：-1,1,1,-1,-1,0,0,-1,-1，其中 -1 表示不确定的。那么可以复原序列：0,1,1,0,1,0,0,1,0。

不看 n 号点，对前面相邻的位置都询问两次，这样做的操作次数是 2n-4。

那问题来了，如果没有任何点可以确定，也就是 -1,-1,-1,-1,-1,-1，就会有两种结果（1,0,1,0,1,0 和 0,1,0,1,0,1），无法确定，怎么办呢？

这里给出两种方法：

方法一

虽然无法确定具体值，但是可以知道奇偶性相同的项是相同的，因此再问 f(1,3) 和 g(1,3)，结果一定在前两种情况中。

总询问次数是 2n-2。

:::info[CODE]{close}

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;

int n,k,f[N],g[N],a[N],b[N],vis[N];

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<n-1;i++)
    {
        printf("? and %d %d\n",i,i+1);
        fflush(stdout);
        scanf("%d",&f[i]);
        printf("? or %d %d\n",i,i+1);
        fflush(stdout);
        scanf("%d",&g[i]);
    }
    printf("? and 1 3\n");
    fflush(stdout);
    scanf("%d",&f[0]);
    printf("? or 1 3\n");
    fflush(stdout);
    scanf("%d",&g[0]);
    for(int i=0;i<=17;i++)
    {
        memset(b,-1,sizeof(b));
        int flag=0;
        for(int j=1;j<n-1;j++)
        {
            int u=(f[j]>>i)&1,v=(g[j]>>i)&1;
            if(u==v)
            {
                flag=1;
                b[j]=b[j+1]=u;
            }
        }
        if(!flag)
            b[1]=b[3]=(f[0]>>i)&1;
        for(int j=2;j<n;j++)
            if(b[j-1]!=-1&&b[j]==-1)
                b[j]=!b[j-1];
        for(int j=n-2;j>=1;j--)
            if(b[j+1]!=-1&&b[j]==-1)
                b[j]=!b[j+1];
        for(int j=1;j<n;j++)
            a[j]+=b[j]<<i;
    }
    for(int i=1;i<n;i++)
        vis[a[i]]=1;
    for(int i=0;i<n;i++)
        if(!vis[i])
        {
            a[n]=i;
            break;
        }
    putchar('!');
    for(int i=1;i<=n;i++)
        printf(" %d",a[i]);
    putchar('\n');
    fflush(stdout);
    return 0;
}

:::

方法二

注意到，一个随机排列某一位 0 和 1 交错的概率是很低的，因此直接对原序列随机重排，就有大概率存在相邻的两个 0 或 1，n 越大时存在的概率越大。

总询问次数是 2n-4，在数据较小时容易被卡。

:::info[CODE]{close}

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

int n,k,f[N],g[N],a[N],b[N],vis[N],t1[N],t2[N];

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++)
        t1[i]=i;
    shuffle(t1+1,t1+n,rnd);
    for(int i=1;i<=n;i++)
        t2[t1[i]]=i;
    for(int i=1;i<n-1;i++)
    {
        printf("? and %d %d\n",min(t1[i],t1[i+1]),max(t1[i],t1[i+1]));
        fflush(stdout);
        scanf("%d",&f[i]);
        printf("? or %d %d\n",min(t1[i],t1[i+1]),max(t1[i],t1[i+1]));
        fflush(stdout);
        scanf("%d",&g[i]);
    }
    for(int i=0;i<=17;i++)
    {
        memset(b,-1,sizeof(b));
        for(int j=1;j<n-1;j++)
        {
            int u=(f[j]>>i)&1,v=(g[j]>>i)&1;
            if(u==v)
                b[j]=b[j+1]=u;
        }
        for(int j=2;j<n;j++)
            if(b[j-1]!=-1&&b[j]==-1)
                b[j]=!b[j-1];
        for(int j=n-2;j>=1;j--)
            if(b[j+1]!=-1&&b[j]==-1)
                b[j]=!b[j+1];
        for(int j=1;j<n;j++)
            a[j]+=b[j]<<i;
    }
    for(int i=1;i<n;i++)
        vis[a[i]]=1;
    for(int i=0;i<n;i++)
        if(!vis[i])
        {
            a[n]=i;
            break;
        }
    putchar('!');
    for(int i=1;i<n;i++)
        printf(" %d",a[t2[i]]);
    printf(" %d",a[n]);
    putchar('\n');
    fflush(stdout);
    return 0;
}

:::