模板：舞蹈链

2018年11月21日
由 everlasting 发表

#include<bits/stdc++.h>

using namespace std;

inline int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*y;
}

struct DLX{
    #define maxnode 1000010
    #define maxn 1010
    
    int n,m,tot;
    //n行 m列 现在一共有tot个元素
    int U[maxnode],D[maxnode],L[maxnode],R[maxnode];
    //U D L R 表示每个点四个方向所指向的节点编号
    int Row[maxnode],Col[maxnode];
    //Row Col 表示每个点所在的行号和列号
    int H[maxn],num[maxn];
    //H 是每行的开始位置    num 是每一列有多少个元素
    int ansnum,ans[maxn];
    //记录答案，表示我们选择了哪些行
    inline void init(int N,int M){
        n=N,m=M;
        for(int i=0; i<=m; i++){
            num[i]=0;
            U[i]=D[i]=i;
            L[i]=i-1;
            R[i]=i+1;
        }
        L[0]=m;
        R[m]=0;
        tot=m;
        for(int i=1; i<=n; i++)H[i]=-1;
    }
    inline void add(int x,int y){//在x行y列插入一个元素
        tot++;
        Col[tot]=y;
        Row[tot]=x;
        num[y]++;
        D[tot]=D[y];
        U[D[y]]=tot;
        U[tot]=y;
        D[y]=tot;
        //在第y列的列首元素下面插入当前元素
        if(H[x]<0){//如果第x行为空，那么将当前元素设为行首元素
            H[x]=L[tot]=R[tot]=tot;
        }
        else{//否则在第x行的第一个元素后插入当前元素
            R[tot]=R[H[x]];
            L[R[H[x]]]=tot;
            L[tot]=H[x];
            R[H[x]]=tot;
        }
    }
    inline void remove(int y){//将第y列删除，并删除第y列中所有元素所在的行
        L[R[y]]=L[y];
        R[L[y]]=R[y];
        for(int i=D[y]; i!=y; i=D[i]){
            for(int j=R[i]; j!=i; j=R[j]){
                U[D[j]]=U[j];
                D[U[j]]=D[j];
                num[Col[j]]--;
            }
        }
    }
    inline void restore(int y){//反过来，进行恢复
        L[R[y]]=y;
        R[L[y]]=y;
        for(int i=U[y]; i!=y; i=U[i]){
            for(int j=L[i]; j!=i; j=L[j]){
                U[D[j]]=j;
                D[U[j]]=j;
                num[Col[j]]++;
            }
        }
    }
    bool dance(int deep){
        if(R[0]==0){
            ansnum=deep;
            return true;
        }
        int now=R[0];
        for(int i=R[0]; i!=0; i=R[i]){
            if(num[i]<num[now])now=i;
        }
        //找到列中包含1最少的列，因为这样可以减少dfs的分支
        remove(now);
        for(int i=D[now]; i!=now; i=D[i]){
            ans[deep]=Row[i];
            for(int j=R[i]; j!=i; j=R[j])remove(Col[j]);
            if(dance(deep+1))return true;
            for(int j=L[i]; j!=i; j=L[j])restore(Col[j]);
        }
        restore(now);
        return false;
    }
    
    #undef maxnode
    #undef maxn
}dlx;

inline void init(){
    int n=rd(),m=rd();
    dlx.init(n,m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int x=rd();
            if(x)dlx.add(i,j);
        }
    }
}

inline void work(){
    if(dlx.dance(0)){
        for(int i=0; i<dlx.ansnum; i++){
            printf("%d ",dlx.ans[i]);
        }
        puts("");
    }
    else puts("No Solution!");
}

int main(){
    init();
    work();
    
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include<bits/stdc++.h>

using namespace std;

inline int rd(){

int x=0,y=1;char c=getchar();

while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}

while(isdigit(c))x=x*10+c-'0',c=getchar();

return x*y;

}

struct DLX{

#define maxnode 1000010

#define maxn 1010

int n,m,tot;

//n行 m列现在一共有tot个元素

int U[maxnode],D[maxnode],L[maxnode],R[maxnode];

//U D L R 表示每个点四个方向所指向的节点编号

int Row[maxnode],Col[maxnode];

//Row Col 表示每个点所在的行号和列号

int H[maxn],num[maxn];

//H 是每行的开始位置 num 是每一列有多少个元素

int ansnum,ans[maxn];

//记录答案，表示我们选择了哪些行

inline void init(int N,int M){

n=N,m=M;

for(int i=0; i<=m; i++){

num[i]=0;

U[i]=D[i]=i;

L[i]=i-1;

R[i]=i+1;

}

L[0]=m;

R[m]=0;

tot=m;

for(int i=1; i<=n; i++)H[i]=-1;

}

inline void add(int x,int y){//在x行y列插入一个元素

tot++;

Col[tot]=y;

Row[tot]=x;

num[y]++;

D[tot]=D[y];

U[D[y]]=tot;

U[tot]=y;

D[y]=tot;

//在第y列的列首元素下面插入当前元素

if(H[x]<0){//如果第x行为空，那么将当前元素设为行首元素

H[x]=L[tot]=R[tot]=tot;

}

else{//否则在第x行的第一个元素后插入当前元素

R[tot]=R[H[x]];

L[R[H[x]]]=tot;

L[tot]=H[x];

R[H[x]]=tot;

}

inline void remove(int y){//将第y列删除，并删除第y列中所有元素所在的行

L[R[y]]=L[y];

R[L[y]]=R[y];

for(int i=D[y]; i!=y; i=D[i]){

for(int j=R[i]; j!=i; j=R[j]){

U[D[j]]=U[j];

D[U[j]]=D[j];

num[Col[j]]--;

}

inline void restore(int y){//反过来，进行恢复

L[R[y]]=y;

R[L[y]]=y;

for(int i=U[y]; i!=y; i=U[i]){

for(int j=L[i]; j!=i; j=L[j]){

U[D[j]]=j;

D[U[j]]=j;

num[Col[j]]++;

}

bool dance(int deep){

if(R[0]==0){

ansnum=deep;

return true;

}

int now=R[0];

for(int i=R[0]; i!=0; i=R[i]){

if(num[i]<num[now])now=i;

}

//找到列中包含1最少的列，因为这样可以减少dfs的分支

remove(now);

for(int i=D[now]; i!=now; i=D[i]){

ans[deep]=Row[i];

for(int j=R[i]; j!=i; j=R[j])remove(Col[j]);

if(dance(deep+1))return true;

for(int j=L[i]; j!=i; j=L[j])restore(Col[j]);

}

restore(now);

return false;

}

#undef maxnode

#undef maxn

}dlx;

inline void init(){

int n=rd(),m=rd();

dlx.init(n,m);

for(int i=1; i<=n; i++){

for(int j=1; j<=m; j++){

int x=rd();

if(x)dlx.add(i,j);

}

inline void work(){

if(dlx.dance(0)){

for(int i=0; i<dlx.ansnum; i++){

printf("%d ",dlx.ans[i]);

}

puts("");

}

else puts("No Solution!");

}

int main(){

init();

work();

return 0;

}

模板：splay

2018年11月20日2019年5月6日
由 everlasting 发表

#include <bits/stdc++.h>

#define MAXN 100010
#define inf INT_MAX/2

using namespace std;

inline int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*y;
}

struct splay_tree{
    int son[MAXN][2],fa[MAXN],val[MAXN],key[MAXN],sz[MAXN];
    int tot,root;
    bool rev[MAXN];
    
    void init(){
        memset(son,0,sizeof(son));
        memset(fa,0,sizeof(fa));
        memset(rev,0,sizeof(rev));
        val[1]=-inf,val[2]=inf;
        key[1]=-inf,key[2]=inf;
        son[2][0]=1;
        sz[2]=2;sz[1]=1;
        fa[1]=2;
        tot=2;
        root=2;
    }
    void Set(int x,int f,int w){
        son[f][w]=x;
        fa[x]=f;
    }
    void pushup(int x){
        sz[x]=sz[son[x][0]]+sz[son[x][1]]+1;
    }
    void add(int x,int k){
        int now=root,pre;
        while(1){
            pre=now;
            now=son[now][k>key[now]];
            if(!now){
                now=++tot;
                Set(now,pre,k>key[pre]);
                val[now]=x;
                key[now]=k;
                sz[now]=1;
                pushup(pre);
                splay(now,0);
                return;
            }
        }
    }
    bool getlr(int x){
        return son[fa[x]][1]==x;
    }
    void Rev(int x){
        if(!x)return;
        rev[x]^=1;
        swap(son[x][0],son[x][1]);
    }
    void pushdown(int x){
        if(!x)return;
        if(rev[x]){
            Rev(son[x][0]);
            Rev(son[x][1]);
            rev[x]^=1;
        }
    }
    void Rotate(int x){
        int f=fa[x],ff=fa[f],w=getlr(x);
        Set(x,ff,getlr(f));
        Set(son[x][w^1],f,w);
        Set(f,x,w^1);
        pushup(f),pushup(x);
    }
    void splay(int x,int to){
        pushdown(x);
        for(int f=fa[x]; f!=to; f=fa[x]){
            if(fa[f]!=to)Rotate(getlr(x)==getlr(f)?f:x);
            Rotate(x);
        }
        if(to==0)root=x;
    }
    int getkth(int x){
        int now=root;
        while(now){
            pushdown(now);
            if(sz[son[now][0]]==x-1)return now;
            else if(sz[son[now][0]]<x)x-=sz[son[now][0]]+1,now=son[now][1];
            else now=son[now][0];
        }
    }
    void spilit(int l,int r){
        splay(getkth(l),0);
        splay(getkth(r+2),root);
    }
    void Reverse(int l,int r){
        spilit(l,r);
        Rev(son[son[root][1]][0]);
    }
    void print(int x){
        if(!x)return;
        pushdown(x);
        print(son[x][0]);
        if(val[x]!=inf && val[x]!=-inf)printf("%d ",val[x]);
        print(son[x][1]);
    }
}splay;

int n,m;

int main(){
    n=rd(),m=rd();
    splay.init();
    for(int i=1; i<=n; i++)splay.add(i,i);
    while(m--){
        int x=rd(),y=rd();
        splay.Reverse(x,y);
    }
    splay.print(splay.root);
    puts("");

    return 0;
}