Codeforces-1617-D2

题目大意

此题为hard版本，与easy版本的差别在于可询问次数不一样，其余全一样。

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

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

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

思路

建议先看一看D1（简单版）的题解，弄懂之后就好理解这一篇题解了。

前一种方法的步骤在第一步中花费的比较多，即寻找一组\(01\)，且询问的三人组结果在第二步中并没有进行使用，那么hard版本的答案就是要在这两点上进行优化。

step1: 寻找一组\(1,0\) 要做的方法是寻找两组连续的查询，返回结果不同。我们连续寻找的话，会花费很多额外的步骤，所以我们就隔三个一查询，即\((a_1,a_2,a_3),(a_4,a_5,a_6)\)。并把它们的结果分别记为\(triple[1],triple[4]\),那么假如它们两个返回值不同，就说明一组\(0\)多，一组\(1\)多，意味着一定会出现寻找两组连续的查询，返回结果不同这种结果，所以我们在这\(6\)个人中连续查询，这样就能找到一组\(0,1\)分别记为\(imp,crew\)。

step2: 确定其他人的身份:

还是三个一组进行。

假设当前的查询的组是第一步中连续查询的，那么我们就直接查询这个数\(query(imp,crew,a_x)\)

假设\(triple[i]=0\)(这一结果在第一步中就已经产生)，那就意味着当前组\(0\)多，那么就先看一看是否前两个数中有两个\(0\)，即\(query(a_i,a_{i+1},crew)\): * 如果返回\(0\)说明前两个全是\(0\),那么单独查询第三个\(query(a_{i+_2},imp,crew)\) * 如果返回\(1\)，说明前两个中一个\(1\)一个\(0\)(也就意味着第三个数是\(0\)),那么我们就查一下第一个的成分就能确定前两个人的成分了 (查成分是吧),\(query(a_i,crew,imp)\)

假设\(triple[i]=1\)，那么就按照前面的思路，反着来就好了，查询\(query(a_i,a_{i+1},imp)\)，剩下的就不写了.(什么懒狗)

不难发现，我们查询一组，这一步只用了两次查询机会，所以加起来，还是够用的。

代码

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

const int maxN = 2e4 + 7;

int T, n, triple[maxN], role[maxN];

int query(int a, int b, int c)
{
    cout << "? " << a << ' ' << b << ' ' << c << endl;
    int r;
    cin >> r;
    return r;
}

int main()
{
    cin >> T;
    while(T--) {
        cin >> n;
        int imp, crew;
        memset(role, -1, sizeof role);
        for(int i = 1; i + 2 <= n; i += 3)
            triple[i] = query(i, i + 1, i + 2);
        for(int i = 1; i + 5 <= n; i += 3)
            if(triple[i] != triple[i + 3]) {
                for(int j = i + 1; j <= i + 2; ++j)
                    triple[j] = query(j, j + 1, j + 2);
                for(int j = i; j <= i + 2; ++j) {
                    if(triple[j] != triple[j + 1])
                        if(triple[j] ==0) {
                            role[j] = 0; role[j + 3] = 1;
                            imp = j; crew = j + 3;
                        }
                        else {
                            role[j] = 1; role[j + 3] = 0;
                            imp = j + 3; crew = j;
                        }
                    }
                break;
            }
        for(int i = 1; i + 2 <= n; i += 3) {
            if(i == imp || i + 1 == imp || i + 2 == imp || i == crew || i + 1 == crew || i + 2 == crew) {
                //cout << "#1" << endl;
                for(int j = i; j <= i + 2; ++j)
                    if(role[j] == -1) {
                        //cout << "# judging " << j << endl;
                        role[j] = query(j, crew, imp);
                    }
            }
            else if(triple[i] == 0) {
                //cout << "#2" << endl;
                if(query(i, i + 1, crew) == 0) {
                    role[i] = role[i + 1] = 0;
                    role[i + 2] = query(i + 2, crew, imp);
                }
                else {
                    if(query(i, crew, imp) == 0) {
                        role[i] = 0; role[i + 1] = 1;
                    }
                    else {
                        role[i] = 1; role[i + 1] = 0;
                    }
                    role[i + 2] = 0;
                }
            }
            else {
                //cout << "#3" << endl;
                if(query(i, i + 1, imp) == 1) {
                    role[i] = role[i + 1] = 1;
                    role[i + 2] = query(i + 2, crew, imp);
                }
                else {
                    if(query(i, crew, imp) == 1) {
                        role[i] = 1; role[i + 1] = 0;
                    }
                    else {
                        role[i] = 0; role[i + 1] = 1;
                    }
                    role[i + 2] = 1;
                }
            }
        }
        cout << "! ";
        vector<int> ans;
        for(int i = 1; i <= n; ++i)
            if(role[i] == 0)
                ans.push_back(i);
        cout << ans.size();
        for(int i = 0; i < ans.size(); ++i)
            cout << ' ' << ans[i];
        cout << endl;
    }
}

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