[NC记录]AT2348 [ARC070D] HonestOrUnkind

**题意** ： 有 $n$ 个人，有 $a$ 个人是好人，剩下的 $b$ 个人是坏人。 这 $n$ 个人都互相知道各自的身份，试图通过询问来得知他们的身份。 你可以指定两个人 $x,y$ ，并向 $x$ 询问 $y$ 是否是诚实的。 - 如果 $x$ 是好人，那么他会按照事实返回答案，也就是说如果 $y$ 是好人，答案就为 $\rm YES$ ，否则为 $\rm NO$。 - 如果 $x$ 是坏人，那么他会**任意**选择 $\rm YES$ 和 $\rm NO$ 来回答。 在 $2n$ 次询问以内确定 $n$ 个人的身份，或指出不可能。 $a,b\leq 2000$。 ------------ 若 $a\leq b$ 则无解。此时若 $a$ 个坏人装作好人，且将其他人视为坏人，则无法将他们与 $a$ 个真正的好人区分开来。 于是我们只需处理 $a>b$ 的情况。 当 $a+b=1$ 时，显然只可能是 $a=1$ ，故仅有的一个人一定是诚实的。 对于询问 $(x,y),(y,x)$ ，可能的答案有 $4$ 种 ，两人的状态也有 $4$ 种。 列表如下： | | $(N,N)\ $ | $(N,Y)\ $ | $(Y,N)\ $ | $(Y,Y)\ $ | | :--: | :--: | :--: | :--: | :--: | | (好,好) | $\times$ | $\times$ | $\times$ | $\sqrt{}$ | | (好,坏) | $\sqrt{}$ | $\sqrt{}$ | $\times$ | $\times$ | | (坏,好) | $\sqrt{}$ | $\times$ | $\sqrt{}$ | $\times$ | | (坏,坏) | $\sqrt{}$ | $\sqrt{}$ | $\sqrt{}$ | $\sqrt{}$ | - $(N,N)$ ： 两人中至少有一个是坏人。 - $(N,Y)$ ： $y$ 必是坏人。 - $(Y,N)$ ： $x$ 必是坏人。 - $(Y,Y)$ ： $x,y$ 是同类人。 如果得到了 $(N,Y),(Y,N)$ ，则转化为 $b$ 减一的子问题。 若得到 $(N,N)$ ，则将两人同时暂时取出。这样得到的子问题中也满足 $a>b$ ，处理完子问题后，抓一个诚实的人验明两人正身。 这样，两人没人的花费都为 $2$ ，符合题目要求。 对于 $(Y,Y)$ ，则将两人连接。 现在有个麻烦，若将连接后的一群人直接看做一个人，则可能不满足 $a>b$ 的性质。 于是，我们不化简一群人，同时避免成群的人参与询问，因为问出个 $(N,Y),(Y,N)$ 就要把这群人暂时删除，也可能破坏性质。 于是，在一轮处理后，所有剩下的人都两两配对了，此时才能把两个人化简为一个人，继续处理。 有个小问题是可能剩余一个人没有配对。此时若对子有偶数个则将其保留，否则暂时删除。（讨论 $a=b+1$ 的情况即可） 不难证明上述算法所需的询问次数 $\leq 2n$。 注意标号从 $0$ 开始 ！！！ ```cpp #include<algorithm> #include<cstdio> #include<vector> #include<queue> #define pb push_back #define MaxN 4050 using namespace std; bool qry(int x,int y){ static char s[4]; printf("? %d %d\n",x-1,y-1);fflush(stdout); scanf("%s",s);return s[0]=='Y'; } int f[MaxN],st[MaxN],tn; char ans[MaxN]; int find(int u) {return !f[u] ? u : f[u]=find(f[u]);} queue<int> q; void solve(vector<int> g) { if (g.size()==1){ans[g[0]]='1';return ;} for (int i=0;i<g.size();i++)q.push(g[i]); vector<int> g2; while(q.size()>1){ int u=q.front();q.pop(); int v=q.front();q.pop(); bool e1=qry(u,v),e2=qry(v,u); if (e1==0&&e2==0){st[++tn]=u;st[++tn]=v;} if (e1==0&&e2==1){q.push(u);ans[v]='0';} if (e1==1&&e2==0){q.push(v);ans[u]='0';} if (e1==1&&e2==1)g2.pb(f[u]=v); }if (q.size()==1){ if (g2.size()&1)st[++tn]=q.front(); else g2.pb(q.front()); q.pop(); }if (!g2.empty())solve(g2); } vector<int> g; int main() { int a,b;scanf("%d%d",&a,&b); if (b>=a){puts("Impossible");return 0;} for (int i=1;i<=a+b;i++)g.pb(i); solve(g); int u=0; for (int i=1;i<=a+b;i++) if (ans[i]=='1')u=i; for (int i=1;i<=tn;i++) ans[st[i]]='0'+qry(u,st[i]); for (int i=1;i<=a+b;i++) if (f[i])ans[i]=ans[find(i)]; printf("! %s\n",ans+1); return 0; } ```