题解：P17740 [ICPC 2019 Xuzhou R] Loli, Yen-Jen, and a graph problem

Nuclear_Fish_cyq · 2026-10-22 21:55:10 · 题解

什么时候才能做出构造题啊。

考虑将大问题递归到小问题。将规模为 n 的问题转到规模为 n+1 的不是很好处理，我们考虑将规模为 n 的问题转到规模为 n+2 的。具体地，我们假设我们已经有了一组对于规模为 n 的问题的答案，我们考虑如何处理新加入的两个点带来的新增连边，即所有的 (i,n+1) 和 (i,n+2) 与 (n+1,n+2)，其中 i\in[1,n]。

我们构造长度为 2n+1 的路径 n+1\rightarrow1\rightarrow n+2\rightarrow2\rightarrow n+1\rightarrow3\rightarrow n+2 \rightarrow\cdots\rightarrow n+1\rightarrow n+2，这个路径显然把新增的边都遍历了一遍。之后再把这个路径拆成长度为 n 和 n+1 的两块即可。

#include <bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define inf INT_MAX
#define linf LLONG_MAX
#define ninf INT_MIN
#define nlinf LLONG_MIN
#define mod 998244353
#define lwbd lower_bound
#define upbd upper_bound
//#define range
using namespace std;
void read(int &x){
    cin >> x;
    return;
}
void readll(ll &x){
    cin >> x;
    return;
}void readdb(db &x){
    cin >> x;
    return;
}
ll n, cnt, now, p[2005];
void solve(ll qwq){
    if(qwq <= 1){
        return;
    }
    solve(qwq - 2);
    cnt = 0;
    now = qwq - 1;
    p[cnt] = now;
    for(int i = 1; i <= qwq - 2; i++){
        cnt++;
        p[cnt] = i;
        now = 2 * qwq - 1 - now;
        cnt++;
        p[cnt] = now;
    }
    cnt++;
    p[cnt] = 2 * qwq - 1 - now;
    if(qwq > 2){
        for(int i = 0; i <= qwq - 2; i++){
            cout << p[i] << " ";
        }
        cout << endl;
    }
    for(int i = qwq - 2; i <= 2 * qwq - 3; i++){
        cout << p[i] << " ";
    }
    cout << endl;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    solve(n);
    return (0 - 0);
}