P6644 Sol

· · 题解

给定一个无向完全图，每条边是红色或蓝色，构造一条经过 n 个点恰好一次的路径使得只有一个颜色分界点。

之前做构造的时候一直避免调整，但是本题不得不用调整。

考虑动态往答案中加点，并调整答案的形态，答案一定形如一段颜色和另一段不同颜色，记为一颜色和二颜色。

图画的太丑了就不放了，意会吧。

考虑分讨，当前新增 x：

若 x 与第二段颜色末尾的连边颜色正好是二颜色，那直接第二段 \xrightarrow 2 x 即可。

否则，如果 x 与第一段颜色末尾的颜色是一颜色，则可以第一段末尾 \xrightarrow 1 x\xrightarrow 1 第二段末尾，再倒着跑完第二段。

否则，我们可以第一段倒数第二个元素 \xrightarrow {1/2} x\xrightarrow 2 第一段末尾，再接上第二段。

所以我们维护两个双端链表，需要支持链表翻转。

翻转可以打个 \text{tag}，插入删除的时候改改方向即可。

但有一些特殊的点：由于我们第一个元素是固定不能动的（必须是答案要求的第一个元素），所以当”第一段倒数第二个元素“不存在的时候跑上面的算法虽然合法，但会导致首元素错误。

这个时候我们可以委曲求全，把第二个链表的元素全扔进第一个链表，形成一个纯色链表，再直接接上 x。

由于每个元素至多只会经历该操作一次，所以复杂度不变，是 O(n^2)。

（实际上 O(n^3) 也可以水过去。）

Code：

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##end(b);i<=i##end;i++)
#define gc getchar
#define sz(x) int(x.size())
#define pb emplace_back
using namespace std;
int read() {
    int s=0;char c=gc(),w=0;
    while(c<'0'||c>'9') w|=c=='-',c=gc();
    while(c>='0'&&c<='9') s=s*10+(c^48),c=gc();
    return w?-s:s;
} const int N=2e3+5;
char w[N][N];int n,vis[N];
struct L {
    int nxt[2][N],o;
    void clr() {memset(nxt,0,sizeof nxt);o=0;}
    #define pre(x) nxt[o][x]
    #define nxt(x) nxt[!o][x]
    void rev() {o^=1;}
    int front() {return nxt(0);}
    int back() {return pre(0);}
    void popf() {int x=nxt(0);nxt(pre(x))=nxt(x);pre(nxt(x))=pre(x);}
    void popb() {int x=pre(0);nxt(pre(x))=nxt(x);pre(nxt(x))=pre(x);}
    void pf(int x) {nxt(pre(nxt(0))=x)=nxt(0);pre(nxt(0)=x)=0;}
    void pb(int x) {pre(nxt(pre(0))=x)=pre(0);nxt(pre(0)=x)=0;}
    void print(int x) {/*memset(vis,0,sizeof vis);*/while(x=nxt(x)) /*cerr<<x<<endl,assert(vis[x]==0),*/vis[x]=1,printf("%d ",x);}
} l1,l2;
int main() {//freopen("hamil.in","r",stdin);freopen("hamil.out","w",stdout);
    F(i,2,n=read()) {
        F(j,1,i-1) {
            char c;while(isspace(c=gc()));c=c=='R';
            w[i][j]=w[j][i]=c;
        }
    }
    F(i,1,n) {
        [&](int x) {
            l1.clr();l2.clr();
            int c=w[x][x==1?2:1];
            l1.pb(x);l1.pb(x==1?2:1);l2.pb(x==1?2:1);
            F(i,3,n) [&](int x){
                if(w[l2.back()][x]^c) return l2.pb(x);
                if(w[l1.back()][x]==c) return l1.back()==l2.back()?l2.popf(),l2.pf(x),l1.pb(x):(l1.pb(x),l1.pb(l2.back()),l2.popf(),l2.rev());
                l2.pf(x);l1.popb();
                if(!l1.back()) {
                    l2.popf();while(l2.front()) l1.pb(l2.front()),l2.popf();
                    l2.pb(l1.back());l2.pb(x);c=!c;
                }
                else if(w[l1.back()][x]==c) l1.pb(x);
                else l2.pf(l1.back());
            }(i<=x?i-1:i);
            printf("%d\n",n);
            l1.print(0);l2.print(l2.front());puts("");
        }(i);
    }
    return 0;
}