[NOI2017]游戏

迈不过友情╰ 2023-10-11 05:21 13阅读 0赞

[题目][Link 1]

来复习\\(\\text\{2-sat\}\\)了

首先对于\\(\\operatorname\{'a'\},\\rm\{'b'\},\\rm\{'c'\}\\)这三种地图，能放在上面的车只有两种

但是对于\\(\\rm\{'x'\}\\)能放三种车，变成一个\\(\\text\{3-sat\}\\)

众所周知\\(\\text\{3-sat\}\\)只能搜索，于是我们爆搜这个位置放什么车

剩下的我们还是直接用\\(\\text\{2-sat\}\\)来判定

对于一组限制\\(u,h\_i,v,h\_j\\)，如果\\(u\\)上不能放\\(h\_i\\)这辆车，那么这个操作就不用处理了

如果\\(v\\)上不能放\\(h\_j\\)这辆车，那么就让\\(u->u'\\)，表示一旦选择\\(u\\)就不合法了

否则我们就正常连边，连\\(u->v\\)，表示选择\\(h\_i\\)就必须选\\(h\_j\\)；**最重要的是，根据对称性，我们还得连\\(v'->u'\\)，表示不选\\(h\_j\\)就不能选\\(h\_i\\)**

这样做的复杂度是\\(O(3^d(n+m))\\) ，不大可行

考虑我们爆搜的时候不搜\\('x'\\)放什么车了，改为搜\\('x'\\)不放什么车，不放\\(A\\)车，那么就能放\\(B\\)车和\\(C\\)车；不放\\(B\\)车就能放\\(A\\)车和\\(C\\)车；所以我们只搜这个位置填成\\(a\\)还是\\(b\\)就把三种情况都计算了

于是复杂度\\(O(2^d(n+m))\\)

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=1e5+5;
    char S[maxn],opv[maxn],opu[maxn];
    struct E{int v,nxt;}e[maxn*3];
    int u[maxn],v[maxn],tot,pos[15];
    int head[maxn],n,m,num,d,__,top,cnt;
    int dfn[maxn],col[maxn],low[maxn],st[maxn],f[maxn],id[2][maxn];
    inline void add(int x,int y) {
        e[++num].v=y;e[num].nxt=head[x];head[x]=num;
    }
    void tarjan(int x) {
        dfn[x]=low[x]=++__,f[x]=1,st[++top]=x;
        for(re int i=head[x];i;i=e[i].nxt) 
        if(!dfn[e[i].v]) tarjan(e[i].v),low[x]=min(low[x],low[e[i].v]);
        else if(f[e[i].v]) low[x]=min(low[x],dfn[e[i].v]);
        if(dfn[x]==low[x]) {
            ++cnt;int now;
            do{now=st[top--];col[now]=cnt;f[now]=0;}while(now!=x);
        }
    }
    inline int getid(int i,char c) {
        if(S[i]==c+'a'-'A') return -1;
        if(S[i]=='a') return c=='B'?0:1;
        if(S[i]=='b') return c=='C'?0:1;
        if(S[i]=='c') return c=='A'?0:1;
    }
    inline void put(int i,int c) {
        if(S[i]=='a') putchar(c?'C':'B');
        if(S[i]=='b') putchar(c?'A':'C');
        if(S[i]=='c') putchar(c?'B':'A');
    }
    inline void solve() {
        cnt=__=0;num=0;memset(head,0,sizeof(head));top=0;
        memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
        memset(col,0,sizeof(col));memset(f,0,sizeof(f));
        for(re int i=1;i<=m;i++) {
            int x=getid(u[i],opu[i]);
            if(x==-1) continue;
            int y=getid(v[i],opv[i]);
            if(y==-1) {add(id[x][u[i]],id[x^1][u[i]]);continue;}
            add(id[x][u[i]],id[y][v[i]]);
            add(id[y^1][v[i]],id[x^1][u[i]]);
        }
        for(re int i=1;i<=n+n;i++) if(!dfn[i]) tarjan(i);
        for(re int i=1;i<=n;i++) if(col[i]==col[i+n]) return;
        for(re int i=1;i<=n;i++) 
            if(col[i]<col[i+n]) put(i,0);else put(i,1);
        exit(0);
    }
    void dfs(int x) {
        if(x==d+1) {solve();return;}
        S[pos[x]]='a';dfs(x+1);
        S[pos[x]]='b';dfs(x+1);
    }
    int main() {
        n=read();d=read(),scanf("%s",S+1);m=read();
        for(re int i=1;i<=m;i++) {
            u[i]=read();std::cin>>opu[i];
            v[i]=read();std::cin>>opv[i];
        }
        for(re int i=1;i<=n;i++) id[0][i]=i,id[1][i]=i+n;
        for(re int i=1;i<=n;i++) if(S[i]=='x') pos[++tot]=i;
        dfs(1);puts("-1");return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11563233.html

[Link 1]: https://www.luogu.org/problem/P3825