CF512E

· · 题解

本题存在线性做法，时间复杂度 O(n)，操作次数上界为 2n。

仍然是考虑一个朴素的中继状态，任何状态都可以简单地转移到此状态，那么我们分别求出起始和终止态到这个中继状态的步骤，然后对于终止态到中继态的操作全部取反就可以了。

以上做法其实其他题解已经提到过，但是实现都使用了 n^2 的构造法，接下来我介绍一种线性构造法。

注意到我们每次都会选择一个形如 1-a-x-b 的四边形，其中 a 和 b 都直接与 a 相连，并且 a，b 之间有直接连边。然后对 (a,b) 执行操作，就得到了 (1,x) 的边。

一种做法是寻找有连边的 (a,b)，然后枚举 x 检查是否与 (a,b) 都有连边，其他部分题解是这个做法我不再多说，但这样是没有前途的 n^2，最多使用 bitset 优化到 \frac {n^2}\omega。

另外一种方法更好地利用了题目的性质，我们称与 1 直接相连的点为关键点，则我们转为维护每个点与多少个关键点相连。具体的方法是当每个点成为关键点的时候我们枚举其出边，若终点还未与关键点相连，则记录下来终点与此关键点相连；否则，终点已经连向的关键点和当前关键点就形成了一组 (a,x,b)。现在的问题是如何检查 (a,b) 是否有边相连呢？事实上，如果此时 1 不与 x 联通，则 a 就一定与 b 相连。我们对 (a,b) 执行操作，然后将 x 设为关键点就可以了，这里我们递归地实现。

完了。每个点和边只会被遍历一次，所以是线性。

#include<bits/stdc++.h>
const int N=4050;
using namespace std;

#define _to e[i].to
#define fore(k) for(int i=hd[k];i;i=e[i].nx)
struct edge{
    int to,nx;
}e[N];int hd[N],S;
void add(int fr,int to){
    e[++S]=(edge){to,hd[fr]},hd[fr]=S;
}
int v[N],con[N];
vector<pair<int,int>>ans1,ans2;

int n,fl;

void push(int k){
    v[k]=-1;//已经遍历过了
    fore(k){
        if(v[_to]==0)
            v[_to]=k;
        else if(v[_to]!=-1){
            if(fl){
                if(!con[_to])ans1.push_back({k,v[_to]});
            }
            else{
                if(!con[_to])ans2.push_back({1,_to});
            }
            push(_to);
        }
    }
}

void solve(){
    memset(hd,0,sizeof(hd));S=0;
    memset(v,0,sizeof(v));
    memset(con,0,sizeof(con));
    v[1]=-1;
    for(int i=1;i<=n;i++)
        add(i,i%n+1),add(i%n+1,i);
    for(int i=1;i<=n-3;i++){
        int x,y;cin>>x>>y;
        add(x,y),add(y,x);
        if(x==1||y==1)
            con[x+y-1]=1;
    }
    fore(1)push(_to);
}

int main(){
    cin>>n;
    fl=1;solve();
//  cout<<endl;
    fl=0;solve();
    cout<<ans1.size()+ans2.size()<<endl;
    for(int i=0;i<ans1.size();i++)
        cout<<ans1[i].first<<' '<<ans1[i].second<<endl;
    for(int i=ans2.size()-1;~i;i--)
        cout<<ans2[i].first<<' '<<ans2[i].second<<endl;
}

稍微解释一下这个代码：