zcmimi's blog
avatar
zc
2020-10-06 10:38:49
  • 本文总阅读量

查看原题

点击跳转

可以发现除了x地图,其他地图都只有两种状态,

如果没有x地图,那就是2-sat裸题,

x地图最多只有8张,我们可以暴力枚举x地图

#include<bits/stdc++.h>
const int N=100011;
int n,d,m,cnt,head[N],a[N],b[N],pos[N];
char s[N],ca[N],cb[N];
struct edge{int to,nxt;}e[N*2];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int dfn[N],low[N],sz,st[N],tp,bl[N],tt;
bool v[N];
void cmin(int&x,int y){if(y<x)x=y;}
void tarjan(int x){
    dfn[x]=low[x]=++sz;st[++tp]=x;v[x]=1;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(!dfn[to])tarjan(to),cmin(low[x],low[to]);
        else if(v[to])cmin(low[x],dfn[to]);
    if(low[x]==dfn[x]){
        ++tt;
        while(int k=st[tp--]){
            bl[k]=tt;v[k]=0;
            if(k==x)break;
        }
    }
}
int neg(int x){return x>n?x-n:x+n;}
int trans(int x,char c){
    if(s[x]==c)return -1;
    if(s[x]=='A'||s[x]=='B')return x+n*(c=='C');
    if(s[x]=='C')return x+n*(c=='B');
}
char snart(int x,int c){
    if(s[x]=='A')return c?'B':'C';
    else if(s[x]=='B')return c?'A':'C';
    else if(s[x]=='C')return c?'A':'B';
}
void solve(){
    cnt=0,memset(head,0,sizeof head),memset(dfn,0,sizeof dfn),sz=0,tt=0;
    for(int i=1;i<=m;++i){
        int x=trans(a[i],ca[i]),y=trans(b[i],cb[i]);
        if(~x){
            if(~y)add(x,y),add(neg(y),neg(x));
            else add(x,neg(x));
        }
    }
    for(int i=1;i<=n*2;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;++i)if(bl[i]==bl[i+n])return;
    for(int i=1;i<=n;++i)putchar(snart(i,bl[i]<bl[i+n]));
    exit(0);
}
int main(){
    std::ios::sync_with_stdio(0);std::cin.tie(0);
    std::cin>>n>>d>>s+1>>m;
    for(int i=1,j=0;i<=n;++i)
        if((s[i]-=32)=='X')pos[++j]=i;
    for(int i=1;i<=m;++i)
        std::cin>>a[i]>>ca[i]>>b[i]>>cb[i];
    for(int i=0;i<(1<<d);++i){
        for(int j=1;j<=d;++j)s[pos[j]]=((i>>j)&1)?'A':'B';
        solve();
    }
    puts("-1");
}
LG 3825 [NOI2017]游戏
comment评论
Search
search