题解：CF2133C The Nether

题目链接

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

CPP

#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;
}

题解：CF2133C The Nether

文章操作

题目链接

分析

Code

相关推荐

评论

题解：CF2133C The Nether