Codeforces-1617-D1 Too Many Impostors (easy version)

题目大意

交互题，有\(n(6 \le n \le 10^4)\)个玩家，其中有\(k\)个\(impostors\)，\(n-k\)人为\(crewmates\),并且一定满足\(\frac{n}{3} < k < \frac{2n}{3}\)。

可以进行至多\(2n\)次询问，每次询问时，输出\(a,b,c\)，如果编号\(a,b,c\)中\(impostors\)较多，则会返回输入\(0\)，否则，则会返回输入\(1\)。

请在询问输出后，输出所有玩家的身份，\(crewmates\)为\(0\), \(impostors\)为\(1\)。 题目链接

思路

我们需要寻找一种可以确定两个玩家身份的方法，假设我们依次询问了\(a,b,c\),\(b,c,d\)，然后恰巧返回了不同的结果，那么就意味着\(a,d\)的身份一定不同,因为两次询问中\(b,c\)的身份不变并且一定是一个\(1\)，一个\(0\),否则两次询问结果不会不一样。

那么假如\(a,b,c\)返回了\(1\)，那么\(a\)就是\(crewmate\),反之则为\(impostor\)。

而题目条件中的\(\frac{n}{3} < k < \frac{2n}{3}\)，就是保证一定会出现上述的连续两组结果不同。

那么我们知道了一个\(0\),一个\(1\)之后，就可以用他们依次询问其它的了相当于每次询问\(1,0,a_i\)这样询问一次就能确定一个。

第一步需要花费\(n\)次，即从\((1,2,3)\),\((2,3,4)\)...\((n-2,n-1,n)\),\((n-1,n,1)\),\((n,1,2)\)

第二步需要花费\(n-2\)次，即确定其他的，所以总次数完全够用。

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int maxN = 2e4 + 7;

int T, n, res[maxN];

int main()
{
    scanf("%d", &T);
    while(T--) {
        cin >> n;
        vector<int> imp;
        for(int i = 0; i < n; ++i) {
            cout << "? " << i + 1 << " " << (i+1) % n + 1 << " " << (i+2) % n + 1 << endl;
            cin >> res[i];
        }
        for(int i = 0; i < n; ++i) {
            if(res[i] != res[(i + 1) % n]) {
                if(res[i] == 0)
                    imp.push_back(i + 1);
                else
                    imp.push_back((i + 3) % n + 1);
                for(int j = 0; j < n; ++j) {
                    if(j != i && j != (i + 3) % n) {
                        cout << "? " << i + 1 << " " << (i+3) % n + 1 << " " << j + 1 << endl;
                        int pd;
                        cin >> pd;
                        if(pd == 0)
                            imp.push_back(j + 1);
                    }
                }
                break;
            }
        }
        cout << "! " << imp.size();
        for(int x : imp) cout << " " << x;
        cout << endl;
    }
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/02/02/Codeforces-1617-D1/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！