Link.
Description.
交互题。
有很多好人和坏蛋，你知道有 \(a\) 个好人和 \(b\) 个坏蛋。
你每次可以问 \(x\)：\(y\) 是不是好人。
如果 \(x\) 是好人他会如实回答，否则会按一定策略任意回答。
问你能否判断哪些人是好人，并交互。
Solution1.
首先考虑无解情况。
如果 \(a\le b\)，我们取出一个 \(b\) 的集合装成好人，肯定分不清。
否则就一定有解，证明通过构造。
首先，我们分别问 \(x\) \(y\) 的身份和问 \(y\) \(x\) 的身份。
分类讨论：
- 互喷：那肯定有一个是坏蛋，可以先不管最后找到一个诚实的人再问两遍
用了 \(4\) 步删除了一个人 - 互捧：要么两个都是坏蛋，要么都是诚实，可以少掉一个人
- 一捧一喷：被喷的肯定不是好人是坏蛋
递归时 \(a\le b\) 的性质不会变。
然后就做完了。
发现这个做法有点 shit，找到一个诚实的人很难。
反正博主是直接写挂了。
Solution2.
考虑维护一个栈，每次询问栈顶 新元素的身份。
如果是好人就说明身份相同，否则就肯定有一个坏人。
如果是好人的话就直接入栈，否则弹栈。
这样构成了一个“猜疑链”，如果有一个人是好人那后面所有人都是好人。
这样就找到了唯一好人。
Coding2.
点击查看代码
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
if(f) x=-x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
int n,a,b,st[100005],tp,rs[100005];
#ifndef ONLINE_JUDGE
int limit=0;char debug[100005];mt19937 rnd(time(0));
#endif
inline char qry(int x,int y)
{
#ifdef ONLINE_JUDGE
printf("? %d %d\n",x-1,y-1),fflush(stdout);
char ch[4];scanf("%s",ch);return *ch=='Y';
#else
limit++;if(debug[x]) return debug[y];
else return 0;
#endif
}
int main()
{
#ifdef ONLINE_JUDGE
read(a,b),n=a+b;
#else
scanf("%s",debug+1),n=strlen(debug+1);
for(int i=1;i<=n;i++) debug[i]^=48;
for(int i=1;i<=n;i++) a+=debug[i],b+=!debug[i];
#endif
if(a<=b) return puts("Impossible"),0;
for(int i=1;i<=n;i++) if(!tp) st[++tp]=i;
else if(qry(st[tp],i)) st[++tp]=i;else tp--;
int nw=st[tp];rs[nw]=1;
for(int i=1;i<=n;i++) if(i^nw) rs[i]=qry(nw,i);
#ifndef ONLINE_JUDGE
printf("cnt = %d\nlimit = %d\n",limit,n*2);
for(int i=1;i<=n;i++) if(rs[i]^debug[i]) return puts("Fail"),0;
return puts("Succeed"),0;
#else
printf("! ");for(int i=1;i<=n;i++) putchar(rs[i]^48);
return putchar('\n'),fflush(stdout),0;
#endif
}