自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:50:00，当前版本为作者最后更新于2023-09-02 21:23:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到使用 $C_n^2$ 次操作问出图的形态就可以在 Subtask 4 中获得 $20$ 分的好成绩了，考虑已知图的形态后如何计算最长简单路径。

直接当成一般图来做是 NPC 问题，考虑利用题目给出的性质，可以发现：

• 这张图至多存在两个连通块。

证明：如果存在三个连通块，分别抓出三个点 $u, v, w$，则 $u, v, w$ 之间两两无边，与题给条件矛盾。

• 如果存在两个连通块，则两个连通块均为团。

证明：如果某个连通块中存在两个无边的 $u, v$，任取另一个连通块中的点 $w$，则 $u, v, w$ 之间两两无边，与题给条件矛盾。

因此，若存在两个连通块，则我们以任意形式遍历其中较大者的所有点即可。

否则，考虑利用形如“若 $u, v$ 与 $u, w$ 之间均不存在边，则 $u, w$ 之间必然存在边”的关系找最长简单路径。

考虑依次加入每个点。注意到无论何时原图都满足其至多存在两个连通块，考虑维护两条路径 $P, Q$，初始分别加入 $0, 1$ 两个点。

接下来考虑加入点 $i$：

• 若 $P$ 的末端与 $i$ 间有边，则将 $i$ 加入 $P$ 的末尾。
• 若 $Q$ 的末端与 $i$ 间有边，则将 $i$ 加入 $Q$ 的末尾。
• 否则，注意到此时 $P, Q$ 的末端直接一定有边，则将 $P, Q$ 串起来作为新 $P$，将 $i$ 单独作为新 $Q$ 即可。

若 $P, Q$ 首端、末端或首尾之间有边，我们不难直接构造出一条长为 $n$ 的路径。

否则，$P, Q$ 各自的首尾之间有边，且由于 $P, Q$ 中点两两连通，考虑抓出一条边 $(u, v)$，其中 $u \in P, v \in Q$，于是也不难构造出一条长为 $n$ 的路径。

现在考虑减少询问次数。

注意到上面构造 $P, Q$ 的过程只需要 $\leq 2n - 4$ 次询问，判断 $P, Q$ 是否连通只需要 $1$ 次询问，判断 $P, Q$ 首端、末端或首尾之间是否有边只需要 $4$ 次询问，抓出 $u, v$ 的过程可以通过两次二分做到 $\leq 2 \lceil \log_2 n \rceil$ 次询问，则总询问次数 $\leq 2n + 2 \lceil \log_2 n \rceil + 1 \leq 545$，于是我们可以在 Subtask 4 中获得 $45$ 分的好成绩了。

注意到最终限制 $400$ 为 $\max(1.5n + 2 \lceil \log_2 n \rceil)$，考虑只用三次询问往 $P, Q$ 中加入两个点。具体的操作可以类似地讨论，此处略去。需要注意的是 $n$ 为奇数时我们需要单独加入最后一项。

最终我们发现按照之前的询问方式可能会恰好多出一次询问。注意到当 $P, Q$ 首端、末端和其中一对首尾之间均无边，$P, Q$ 各自的首尾之间一定有边，于是我们可以减少恰好一次操作。

最终，$n$ 为偶数时的询问次数 $\leq 1.5n + 2 \lceil \log_2 n \rceil$、$n$ 为奇数时的询问次数 $\leq 1.5(n - 1) + 2 \lceil \log_2 n \rceil + 2$，于是最大总询问次数为 $400$ 次，可以通过。

代码：

#include <iostream>
#include <vector>
#include "longesttrip.h"

using namespace std;

pair<int, int> find1(int u, vector<int> v1){
	if (v1.size() == 1) return make_pair(u, v1[0]);
	int mid = v1.size() / 2;
	vector<int> v2;
	for (int i = 1; i <= mid; i++){
		v2.push_back(v1.back());
		v1.pop_back();
	}
	if (are_connected(vector<int>{u}, v1)) return find1(u, v1);
	return find1(u, v2);
}

pair<int, int> find2(vector<int> v1, vector<int> v2){
	if (v1.size() == 1) return find1(v1[0], v2);
	int mid = v1.size() / 2;
	vector<int> v3;
	for (int i = 1; i <= mid; i++){
		v3.push_back(v1.back());
		v1.pop_back();
	}
	if (are_connected(v1, v2)) return find2(v1, v2);
	return find2(v3, v2);
}

vector<int> longest_trip(int N, int D){
	vector<int> v1, v2;
	v1.push_back(0);
	v2.push_back(1);
	for (int i = 2; i + 1 < N; i += 2){
		if (are_connected(vector<int>{v1.back()}, vector<int>{i})){
			v1.push_back(i);
			if (are_connected(vector<int>{i}, vector<int>{i + 1})){
				v1.push_back(i + 1);
			} else if (are_connected(vector<int>{v2.back()}, vector<int>{i + 1})){
				v2.push_back(i + 1);
			} else {
				while (!v2.empty()){
					v1.push_back(v2.back());
					v2.pop_back();
				}
				v2.push_back(i + 1);
			}
		} else if (are_connected(vector<int>{v2.back()}, vector<int>{i})){
			v2.push_back(i);
			if (are_connected(vector<int>{i}, vector<int>{i + 1})){
				v2.push_back(i + 1);
			} else {
				v1.push_back(i + 1);
			}
		} else {
			if (are_connected(vector<int>{i}, vector<int>{i + 1})){
				while (!v2.empty()){
					v1.push_back(v2.back());
					v2.pop_back();
				}
				v2.push_back(i);
				v2.push_back(i + 1);
			} else {
				v1.push_back(i + 1);
				while (!v2.empty()){
					v1.push_back(v2.back());
					v2.pop_back();
				}
				v2.push_back(i);
			}
		}
	}
	if (N % 2 == 1){
		if (are_connected(vector<int>{v1.back()}, vector<int>{N - 1})){
			v1.push_back(N - 1);
		} else if (are_connected(vector<int>{v2.back()}, vector<int>{N - 1})){
			v2.push_back(N - 1);
		} else {
			while (!v2.empty()){
				v1.push_back(v2.back());
				v2.pop_back();
			}
			v2.push_back(N - 1);
		}
	}
	if (!are_connected(v1, v2)){
		if (v1.size() > v2.size()) return v1;
		return v2;
	}
	int p = v1[0], q = v2[0], size1 = v1.size(), size2 = v2.size();
	vector<int> ans;
	if (are_connected(vector<int>{p}, vector<int>{q})){
		for (register int i = size1 - 1; i >= 0; i--){
			ans.push_back(v1[i]);
		}
		for (register int i = 0; i < size2; i++){
			ans.push_back(v2[i]);
		}
	} else {
		int r = v1[size1 - 1], s = v2[size2 - 1];
		if (are_connected(vector<int>{r}, vector<int>{s})){
			for (register int i = 0; i < size1; i++){
				ans.push_back(v1[i]);
			}
			for (register int i = size2 - 1; i >= 0; i--){
				ans.push_back(v2[i]);
			}
		} else if (are_connected(vector<int>{p}, vector<int>{s})){
			for (register int i = size1 - 1; i >= 0; i--){
				ans.push_back(v1[i]);
			}
			for (register int i = size2 - 1; i >= 0; i--){
				ans.push_back(v2[i]);
			}
		} else {
			int posu, posv;
			pair<int, int> pr = find2(v1, v2);
			for (register int i = 0; i < size1; i++){
				if (v1[i] == pr.first){
					posu = i;
					break;
				}
			}
			for (register int i = 0; i < size2; i++){
				if (v2[i] == pr.second){
					posv = i;
					break;
				}
			}
			for (register int i = posu - 1; i >= 0; i--){
				ans.push_back(v1[i]);
			}
			for (register int i = size1 - 1; i >= posu; i--){
				ans.push_back(v1[i]);
			}
			for (register int i = posv; i < size2; i++){
				ans.push_back(v2[i]);
			}
			for (register int i = 0; i < posv; i++){
				ans.push_back(v2[i]);
			}
		}
	}
	return ans;
}