题解：CF2133C The Nether

ZesteYdaZ · 2025-08-25 23:47:29 · 题解

题目链接

https://www.luogu.com.cn/problem/CF2133C

分析

首先，对于每个点可以查出以它为起点，集合中包含所有点时的最长路径，记为 len_i。最长路径的起点即为 len_i 最大的 i。

考虑如何找到一个点在最长路径上的后继。可以将点按照 len 分层。设当前找到的最长路径上的最后一个点为 p。枚举最长路径长度为 len_p - 1 的所有点。若 p 在集合中排除同一层中除当前点外的所有点时，最长路径长度仍为 len_p，则当前点是 p 在最长路径上的后继。

第一遍查询 n 次，第二遍最坏情况每个点查一次，也是 n 次，总数不超过 2n 次。

Code

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 505;
int len[N];

vector<int> ans, vec, lth[N];

int main()
{
    // freopen(".in", "r", stdin), freopen(".out", "w", stdout);

    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int T; cin >> T;
    for (int $ = 0; $ < T; ++ $)
    {
        int n; cin >> n;

        int tmp, max_lth = 0;
        for (int i = 1; i <= n; ++ i)
        {
            cout << "? " << i << ' ' << n;
            for (int j = 1; j <= n; ++ j) cout << ' ' << j;
            cout << endl, cin >> tmp, lth[tmp].push_back(i), len[i] = tmp, max_lth = max(max_lth, tmp);
        }

        ans.push_back(lth[max_lth].back());
        for (int i = max_lth; i > 1; -- i)
        {
            int now = ans.back(); bool f = true;
            for (int j : lth[i - 1])
            {
                vec.clear();
                for (int k = 1; k <= n; ++ k) if (len[k] != i - 1 || k == j) vec.push_back(k);
                cout << "? " << now << ' ' << vec.size();
                for (int k : vec) cout << ' ' << k;

                cout << endl, cin >> tmp;
                if (tmp == i) { f = false, ans.push_back(j); break; }
            }

            if (f) ans.push_back(lth[i - 1].back());
        }

        cout << "! " << ans.size();
        for (int i : ans) cout << ' ' << i; cout << endl;

        ans.clear();
        for (int i = 1; i <= max_lth; ++ i) lth[i].clear();
    }
    return 0;
}