IOI 2023 最长路程 题解

First Post:

Last Update:

magic!

下文用 表示 点与 点有直接连边。

首先注意到 时问题不弱于无向图哈密顿路，所以要找最长肯定需要用到 带来的一些性质。

容易发现整张图的连通块个数不超过 。

考虑维护两条链 ，容易发现，加入一个点 之后，整个图仍然可以被划分成两条不自交的链（我也不知道这个 idea 怎么能够被想出来，可能这样可以契合三个点的限制？反正我没有想出来）。

具体地，设 的末尾点为 ， 的末尾点为 ，那么如果 或 ，就将 加入对应的链尾，否则一定有 ，此时把 倒序接到 的末尾，让 成为新的 即可。

接下来，我们用 次询问判断 的起点、终点之间分别有无连边，如果有的话，显然可以将 与 拼接起来，形成原图的一条哈密顿路，否则，由 的限制， 的起点与终点， 的起点与终点之间，肯定都有边，也就是说， 和 在原图上是一个环。

因此，如果 中任意点与 中任意点有连边，显然也可以将这两个环拼成哈密顿路，否则输出大小较大的哪个环即可。

如何找到 与 之间的连边？可以进行一次二分，二分时检查 与 有没有边。二分后就能找到这条边在 中的端点 ，然后再在 上二分，检查 的一个前缀是否与 有边。这样就能找到有直接连接的两个点 和 。

上述做法的询问数上界为 ，可以通过 的限制，拿到 分的高分。

容易发现瓶颈在于维护 时每个点都进行了两次操作。通过做交互题的一些经验，我们容易想到尝试用三次询问来确定两个点。

在加入 和 时，进行如下过程：

  1. 如果
    1. 如果 ，令 。(这里 号表示拼接)
    2. 如果 ，令 。
    3. 此时一定有 ，令 (这里 表示 翻转后的结果)
  2. 否则，如果 。
    1. 如果 ，令 。
    2. 否则，一定有 ，令 。
  3. 否则，一定有 。
    1. 如果 ，令
    2. 否则，一定有 ，令 。

于是询问上界变为 。

完全想不到这种题目啊。/hanx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
const int N = 3e2 + 5;
int n,D;
vector<int> L1,L2;
bool are_connected(int x,int y) {
	vector<int> A(1,x),B(1,y);
	return are_connected(A,B);
}
vector<int> longest_trip(int _n,int _d) {
	n = _n;D = _d;L1.clear();L2.clear();
	auto Add2 = [&](const int &C,const int &D) {
		int A = L1.back(),B = L2.back();
		// printf("A,B,C,D:%d,%d,%d,%d\n",A,B,C,D);
		if(are_connected(C,D)) {
			if(are_connected(A,C)) { L1.push_back(C);L1.push_back(D);return;}
			if(are_connected(B,C)) { L2.push_back(C);L2.push_back(D);return;}
			while(L2.size()) L1.push_back(L2.back()),L2.pop_back();
			L2.push_back(C);L2.push_back(D);return;
		} 
		if(are_connected(A,C)) {
			if(are_connected(B,D)) { L1.push_back(C);L2.push_back(D);return;}
			L1.push_back(C); while(L2.size()) L1.push_back(L2.back()),L2.pop_back();
			L2.push_back(D);
			return;
		}
		if(are_connected(B,C)) {
			L1.push_back(D);L2.push_back(C);
			return;
		}
		L1.push_back(D); while(L2.size()) L1.push_back(L2.back()),L2.pop_back();
		L2.push_back(C);
	};
	for(int i = 0;i < n;i++) {
		if(L1.empty()) {L1.push_back(i);continue;}
		if(L2.empty()) {L2.push_back(i);continue;}
		if(i + 1 < n) { Add2(i,i + 1);++i;continue;}
		if(are_connected(L1.back(),i)) { L1.push_back(i);continue;}
		if(are_connected(L2.back(),i)) { L2.push_back(i);continue;}
		while(L2.size()) L1.push_back(L2.back()),L2.pop_back();
		L2.push_back(i);
	}
	auto Chk0 = [&]() {
		if(are_connected(L1.back(),L2.front())) return true;
		return false;
	};
	auto Mge = [&]() {
		auto res = L1;
		for(auto i : L2) res.push_back(i);
		return res;
	};
	if(Chk0()) return Mge();
	reverse(L2.begin(),L2.end());
	if(Chk0()) return Mge();
	swap(L1,L2);
	if(Chk0()) return Mge();
	reverse(L1.begin(),L1.end());
	if(Chk0()) return Mge();
	int c1 = 0,c2 = 0;
	int lef = 0,rig = L1.size();
	while(lef < rig) {
		int mid = lef + rig >> 1;
		vector<int> pre;
		for(int i = 0;i <= mid;i++) pre.push_back(L1[i]);
		if(are_connected(pre,L2)) rig = mid;
		else lef = mid + 1;
	}
	c1 = lef;
	if(c1 == L1.size()) {
		return L1.size() > L2.size() ? L1 : L2;
	}
	lef = 0,rig = L2.size() - 1;
	while(lef < rig) {
		int mid = lef + rig >> 1;
		vector<int> pre,nd(1,L1[c1]);
		for(int i = 0;i <= mid;i++) pre.push_back(L2[i]);
		if(are_connected(pre,nd)) rig = mid;
		else lef = mid + 1;
	}
	c2 = lef;
	vector<int> res;
	
	for(int i = (c1 + 1) % L1.size();i != c1;i = (i + 1) % L1.size())
		res.push_back(L1[i]);
	res.push_back(L1[c1]);
	res.push_back(L2[c2]);
	for(int i = (c2 + 1) % L2.size();i != c2;i = (i + 1) % L2.size())
		res.push_back(L2[i]);
	return res;
}
≡