题解 P9601 【[IOI2023] 最长路程】

· · 题解

注意到使用 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, 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;
}