XCPC Notes

Appearance

发布时间：2024-07-28

2sat ​

概念 ​

给定x1,x2,x3,x4,...,xn的bool值，以及多对aVb这样的形式，问是否存在一组解
根据离散数学的知识 a∨b=¬a→b=¬b→aa \vee b = \neg a \rightarrow b = \neg b \rightarrow a

  • 建边后，tarjan缩点，选拓扑排序更靠后的点
  • 如果 xi,¬xix_i, \neg x_i 在一个强连通分量，则无解
  • tarjan缩点后编号即为拓扑排序逆序

模板 ​

cpp
int h[N],e[M],ne[M],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfn[N],low[N],stk[N],id[N],timestamp,top,cnt;
bool in_stk[N];
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stk[v])low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        int y;
        cnt++;
        do{
            y=stk[top--];
            in_stk[y]=0;
            id[y]=cnt;
        }while(y!=u);
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int i,a,j,b;
        cin>>i>>a>>j>>b;
        i--,j--;
        add(2*i+!a,2*j+b);
        add(2*j+!b,2*i+a);
    }
    for(int i=0;i<2*n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(int i=0;i<n;i++){
        if(id[2*i]==id[2*i+1]){
            cout<<"IMPOSSIBLE\n";
            return;
        }
    }
    cout<<"POSSIBLE\n";
    for(int i=0;i<n;i++){
        if(id[2*i]<id[2*i+1])cout<<"0 ";
        else cout<<"1 ";
    }
}

P3825 [NOI2017] 游戏 ​

题意：
小明有三辆车A,B,C，有四种地图分别为a,b,c,x，其中x允许所有车玩，a不允许A玩，b，c同理
给定一个游玩序列，有a,b,c,x
还有m个条件，每个条件有i,x,j,y，如果第i个图玩了x，那么第j个图就要玩y
问是否存在方案
思路：

  • 如果没有地图x，那么就是个2sat问题
  • x的地图最多有8种，因此可以考虑让x变成a或b地图(不用变c地图，因为如果c地图成立，那么a或b其中一种必定成立)
  • 然后暴力枚举x，对于每种情况建图跑2sat
  • 注意，如果 x→yx \rightarrow y ，但y不能成立，需要建 x→¬xx \rightarrow \neg x 的边，表示 ¬x∨¬x=¬x\neg x \vee \neg x=\neg x
cpp
int h[N],e[M],ne[M],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfn[N],low[N],stk[N],id[N],timestamp,top,cnt;
bool in_stk[N];
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stk[v])low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        int y;
        cnt++;
        do{
            y=stk[top--];
            in_stk[y]=0;
            id[y]=cnt;
        }while(y!=u);
    }
}
int pos[10];
struct Node{
    int i,A,j,B;
} op[N];
int n,d,m;
string s;
int get(int x,int i,int j){
    int a=s[x]-'a';
    if(((a+1)%3==i)^j)return x;
    return x+n;
}
char put(int x,int i){
    int a=s[x]-'a';
    return ((a+i+1)%3)+'A';
}
bool work(){
    memset(h,-1,sizeof h);
    memset(dfn,0,sizeof dfn);
    idx=timestamp=cnt=0;
    for(int i=0;i<m;i++){
        auto [x,a,y,b]=op[i];
        if(s[x]-'a'!=a){
            if(s[y]-'a'!=b)add(get(x,a,0),get(y,b,0)),add(get(y,b,1),get(x,a,1));
            else add(get(x,a,0),get(x,a,1));
        }
    }
    for(int i=0;i<2*n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(int i=0;i<n;i++){
        if(id[i]==id[n+i])return false;
    }
    for(int i=0;i<n;i++){
        if(id[i]<id[n+i])cout<<put(i,0);
        else cout<<put(i,1);
    }
    return true;
}
void solve(){
    cin>>n>>d>>s>>m;
    int j=0;
    for(int i=0;i<m;i++){
        if(s[i]=='x')pos[j++]=i;
    }
    for(int i=0;i<m;i++){
        char a,b;
        cin>>op[i].i>>a>>op[i].j>>b;
        op[i].i--,op[i].j--;
        op[i].A=a-'A';
        op[i].B=b-'A';
    }
    for(int k=0;k<1<<d;k++){
        for(int i=0;i<d;i++){
            if(k>>i&1)s[pos[i]]='a';
            else s[pos[i]]='b';
        }
        if(work())return;
    }
    cout<<"-1\n";
}

CF1971H ±1 ​

题意：
给定3行n列的数组，数字要么为a要么为-a,a≤n，每种不同的数字如果选择1，那么-a表示-1
问是否存在一种方案，使得选好数后，对于每一列排序，中间那行全为1
思路：

  • 一个数只有两种选择，考虑2sat
  • 对于每一列来讲，最多有一个-1
  • 因此考虑枚举同一列三个数的其中两个(x,y)，如果x最终为-1，那么y最终一定要是1
  • 建好图后跑2sat即可
cpp
int h[N],e[M],ne[M],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfn[N],low[N],stk[N],id[N],timestamp,top,cnt;
bool in_stk[N];
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stk[v])low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        int y;
        cnt++;
        do{
            y=stk[top--];
            in_stk[y]=0;
            id[y]=cnt;
        }while(y!=u);
    }
}
int n,g[4][N];
int get(int x,int i){
    x=abs(x);
    if(i==0)return x+n;
    return x; 
}
void solve(){
    cin>>n;
    idx=timestamp=cnt=0;
    for(int i=0;i<=2*n;i++)h[i]=-1,dfn[i]=id[i]=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=n;j++)cin>>g[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            for(int k=1;k<=3;k++){
                if(j==k)continue;
                int x=g[j][i],y=g[k][i];
                if(x<0&&y<0)add(get(x,1),get(y,0));
                if(x<0&&y>0)add(get(x,1),get(y,1));
                if(x>0&&y<0)add(get(x,0),get(y,0));
                if(x>0&&y>0)add(get(x,0),get(y,1));
            }
        }
    }
    for(int i=1;i<=2*n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(int i=1;i<=n;i++){
        if(id[i]==id[n+i]){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
}

Wenwei Lin · 2022 — 2025