[atARC070F]HonestOrUnkind

考虑当$a\le b$时，构造两种方案，满足诚实的人不交，接下来要求对于任意询问，这两种方案的答案都有可能相同

考虑询问$(i,j)$，若$i$在两种方案中有一种不诚实，那么总可以让答案相同，又因为诚实的人不交，因此一定可行

当$a>b$，我们只需要找到一个诚实的人就可以做了，考虑如何找到这个诚实的人：

对于询问$(i,j)$，若结果为不诚实，至少存在一个人不诚实，考虑同时删去$i$和$j$，显然最终不可能只剩下不诚实的人

维护一个栈（初始为空），从1到$n$遍历所有人，并询问$(栈顶,i)$，考虑结果：

1.结果为不诚实，同时删去（弹出）栈顶和$i$即可

2.结果为诚实，将$i$加入栈中，并继续此过程

当我们询问完之后，可以发现栈中若栈顶不诚实，由于栈顶的下一个元素认为栈顶诚实，因此其也不诚实，以此类推，整个栈中所有人都不诚实，即矛盾

通过栈顶再$n$次询问即可确定剩余的人

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 4005

 4 stack<int>st;

 5 int a,b,ans[N];

 6 char s[11];

 7 int query(int x,int y){

 8     printf("? %d %d\n",x-1,y-1);

 9     fflush(stdout);

10     scanf("%s",s);

11     return s[0]=='Y';

12 }

13 int main(){

14     scanf("%d%d",&a,&b);

15     if (a<=b){

16         printf("Impossible");

17         return 0;

18     }

19     for(int i=1;i<=a+b;i++)

20         if (st.empty())st.push(i);

21         else{

22             if (query(st.top(),i))st.push(i);

23             else st.pop();

24         }

25     for(int i=1;i<=a+b;i++)ans[i]=query(st.top(),i);

26     printf("! ");

27     for(int i=1;i<=a+b;i++)printf("%d",ans[i]);

28 }

巴特西

[atARC070F]HonestOrUnkind

最新文章

热门文章