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

· · 题解

SOLUTION

删除了原题中不和谐的内容。

参观同机房大佬做法，发现我们的做法非常丑陋，但是也是对的，遂写题解。

本题做法由 @songzirui_ 与 @OIer_sundingjia 共同得出。

首先我们需要知道迹实际上就是路径，而且没有要求是简单路径，也就是说可以重复经过一个点。

考虑 N 为奇数的情况，此时每个点的度都是 N-1，也就是说原图存在欧拉回路。

那我们求出欧拉回路，再把回路划分成 N-1 条路径，这是容易实现的。

对于 N 为偶数的情况，试图把图中的每个点权通过一些操作变为偶数。

具体地，把所有点两两配对。

不妨设一对点中左边的是 i，右边的是 i+1，点对从上到下编号递增。

尝试对每个 i \in [1,n] 且 i 为奇数，连一条迹，使得它从 i 开始，从 i+1 结束，长度为 \lfloor \frac{i}{2} \rfloor +1。

对 i \in [1,8] 尝试，得到一组可行解：

于是我们得到了迹长在 [1,4] 中的答案。

这启发我们把所有点八个一组分类。

对于 i > 8，尝试将其归纳到 i \le 8。

观察这个图形，可以发现它把从 i 开始的迹缩短了 4 个长度，可以以此为基础，将迹的长度缩短至 [1,4]。

需要注意的一点是，并不能直接使用这个图形当作长度为 4 的迹，因为它并不在 i+1 结束。

发现在第二张图中，每一条边都是平着连，或者隔一层连的，跨度不超过一层。

于是只要保证，第三张图的跨度大于一层，即可保证两张图所连接的边没有冲突。

此处证明读者感性理解即可，不再给出严格表示。

对于 (i,i+1) 且 i 是奇数，易知它需要连 \lfloor \frac{i}{8} \rfloor 次图三所示图形，而有 \lfloor \frac{i}{2} \rfloor -1 种选择，这肯定是足够的，还保证了不与 i=1,2 连边，这个条件后面有用。

这样我们就成功归纳出了一组操作，将已经连的边全部删除，使得原图上所有点的度数都是偶的。

对于 N=2，所有点没有度数，无需进行下一步操作。

否则只要原图连通，那一定有一条欧拉回路，于是只要证明原图依然连通。

显然 i=1 与除了 i=2 的所有点都连通，于是只要证明 i=1 与 i=2 连通。

据第二张图，有 (1,3),(3,6),(6,2) 三条边依旧存在，于是对于 n \ge 6，原图连通。

对于 N=4，原图不连通，直接特判即可，具体见代码。

最后求出欧拉路径，划分剩下的迹就做完了。

实现见代码。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
vector<int> vec[1010];
int tot=0;
int dis[1010][1010];//dis->disabled,dis[i][j]=1 代表i-j边已经被使用。
void link(int i,int j){
    dis[i][j]=dis[j][i]=1;
    vec[tot].push_back(j);
}
// @OIer_sundingjia 认为图二所示像是蝴蝶，遂命名。
void butterfly(int i,int j){
    link(i,j+1),link(j+1,i+1),link(i+1,j),link(j,i);
}
stack<int> stk;
int st[1010];//当前弧优化
void dfs(int u){
    for(int i=st[u]+1;i<=n;i++){
        if(i==u) continue;
        if(!dis[u][i]){
            dis[u][i]=dis[i][u]=1;
            dfs(i);
        }
        st[u]=i;
    }
    stk.push(u);
}
vector<int> e;//euler_path
void solve(){
    while(stk.size()){
        e.push_back(stk.top()),stk.pop();
    }
    int c=0;
    while(1){
        tot++;
        if(tot==n) break;
        vec[tot].push_back(e[c]);
        for(int i=c;i<c+tot;i++){
            link(e[i],e[i+1]);
        }
        c+=tot;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    if(n==4){//corner case，因为这个吃了两发罚时
        cout<<"1 2\n1 3 4\n1 4 2 3\n";
        return 0;
    }
    if(n%2==0){
        for(int i=1;i<=n;i+=2){
            int c=i/8;
            ++tot;
            vec[tot].push_back(i);
            for(int j=1;j<=c;j++){
                butterfly(i,i-2*(j+1));
            }
            if(i%8==1){
                link(i,i+1);
            }
            else if(i%8==3){
                link(i,i-2),link(i-2,i+1);
            }
            else if(i%8==5){
                link(i,i-2),link(i-2,i-1),link(i-1,i+1);
            }
            else{
                link(i,i+1),link(i+1,i-1),link(i-1,i-2),link(i-2,i+1);
            }//大分讨
        }
    }
    dfs(1);
    solve();
    for(int i=1;i<n;i++){
        for(int v:vec[i]){
            cout<<v<<' ';
        }
        cout<<'\n';
    }
    return 0;
}