传送门:

AtCoder

洛谷


题目大意:

现在有n个人,编号从0 ~ n-1。这些人中有a个人是诚实的,剩下的b个人是不友好的。这n个人都知道各自的身份,但是你只知道有a个诚实的人和b个不友好的人,你现在试图通过询问来得知他们的身份。

你可以进行询问,询问格式类似于? x y,表示向x询问y是否是诚实的。返回答案按照如下规则:

  • 如果x是诚实的人,那么他会按照事实返回答案,也就是说如果y是诚实的,返回答案就为\rm YES,否则返回\rm NO
  • 如果x是不友好的人,那么他会任意选择\rm YES\rm NO来回答。也就是说x是可以按照某种策略来回答你的问题的。

现在请你在2n次询问以内确定n​个人的身份,如果不可能,请输出Impossible,否则请按照! S0S1S2...Sn-1的格式输出(其中0,1,2,…,n-1都为下标,Si表示i的身份,如果第i个人是诚实的,请输出1,否则输出0,身份之间没有空格)。

如下是一个成功的询问的示例:

void query(int x,int y){printf("? %d %d\n",x,y);fflush(stdout);scanf("%s",s);}

上面这个交互函数中的s为字符串变量,用来读入返回的答案。

解题思路:

首先考虑什么时候无解,显然当a \leqslant b的时候就无解了,因为这个时候b个不友好的人中的a个人是可以假装那a个诚实的人的。

考虑有解的情况如何确定身份。显然我们可以先找出来一个诚实的人,然后由他来得到其他人的身份。

首先考虑两种返回答案和两者身份的关系(假设当前询问为?~x~y):

  • 对于返回\rm NO的情况,显然不论如何两个人肯定有一个人是不友好的。因为假设x返回的是正确的答案,那么y就是不友好的,假设x返回的不是正确的答案,那么x就是不友好的。
  • 对于返回\rm YES的情况,则两个人可能都是诚实的,也可能都是不友好的。

现在我们开一个栈出来,依次枚举每一个人,询问栈顶当前枚举的点是否是诚实的,如果返回\rm NO则弹栈,否则则将当前点加入栈中。

考虑我们这样做的正确性。我们现在将栈底到栈顶的元素依次连边,显然构成了一条询问链,只要链中有一个点是诚实的,那么显然链尾就是诚实的,且此时a>b,所以不存在有b演你的情况,所以这样做是正确的,且询问次数恰好2n

Code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=4e3+10;
char s[10];int top,sta[maxn],ans[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
void query(int x,int y){printf("? %d %d\n",x,y);fflush(stdout);scanf("%s",s);}
int main(){
    int a=read(),b=read(),n=a+b;
    if(a<=b){puts("Impossible");return 0;}
    for(int i=0;i<n;i++){
        if(!top)sta[++top]=i;
        else {
            query(sta[top],i);
            if(s[0]=='Y')sta[++top]=i;
            else top--;
        }
    }for(int i=0;i<n;i++){query(sta[top],i);if(s[0]=='Y')ans[i]=1;}
    printf("! ");for(int i=0;i<n;i++)printf("%d",ans[i]);puts("");
    return 0;
}

发表评论