ARC070F 题解

· · 题解

前言

题目传送门！

更好的阅读体验？

牛逼构造题。试图说得更好理解一些。

思路

如果 a \le b 也就是好人没坏人多：只要其中 a 个坏人说自己阵营的都是好人，对方阵营的都是坏人，坏人就变得和好人一样了，显然无法分辨。

首先要先找到一个好人。为了实现这个，我们考虑一种特别神仙的做法：

维护一个类似单调栈的玩意，它上面是好人，下面是坏人。对于每一个 u，做询问操作 \operatorname{query}(top, u)。

分类讨论。有四种情况：

  1. 栈顶是好人并且回答 \texttt{Yes}。那么这个人是好人，放进栈里仍然符合栈的性质。
  2. 栈顶是好人并且回答 \texttt{No}。那么这个人是坏人。
  3. 栈顶是坏人并且回答 \texttt{Yes}。那么我们无法知道这个人是谁，但是由于此时栈没有好人（顶部是坏人，说明没有好人）直接放进去也是没问题的。
  4. 栈顶是坏人并且回答 \texttt{No}。这个人可能是好人也可能是坏人。

注意到我们对 2 与 4 号情况没有好方法。观察一下，发现一个很重要的性质：栈顶和这个人至少有一个是坏人。

这里面有坏人啊，那我们当然要草掉他，于是把两个人都扔掉。

综上，操作完后，a > b。又因为我们操作完了，所以 b = 0，也就是说栈里面全是好人。

于是我们完成了我们的目标：找到了一个好人。

回过头来看一下流程。显然只用去了 n 次操作，剩下 n 次。

那就很简单了，抓这个人拷问 n 次就能知道全部人的身份了。

代码

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
bool query(int x, int y)
{
    cout << "? " << x - 1 << ' ' << y - 1 << endl;
    char ans; cin >> ans; return (ans == 'Y');
}
int a, b, n; bool zlt[114514];
void answer()
{
    cout << "! "; for (int i = 1; i <= n; i++) cout << zlt[i];
    cout << endl;
}
int main()
{
    cin >> a >> b, n = a + b;
    if (a <= b) {puts("Impossible"); return 0;}
    stack <int> stk;
    for (int i = 1; i <= n; i++)
        if (stk.empty()) stk.push(i);
        else
        {
            int top = stk.top();
            stk.push(i);
            if (!query(top, i)) stk.pop(), stk.pop(); //把这两个都丢出去
        }
    int good = stk.top(); //好人
    for (int i = 1; i <= n; i++) zlt[i] = query(good, i);
    answer();
    return 0;
}

希望能帮助到大家！