[NOI2017]游戏(2-SAT)

bzoj4945 luoguP3825

题目描述参照luogu

题解：

乍一看三辆车，你以为我是$3-SAT$,其实还是我$2-SAT$哒！

能放三辆车的只有至多$8$条，似乎暴力枚举所有状态都行...?

我们发现$3^8$有点太大了。。。

但我们考虑一下

x赛道可以放三种车，但我们将它改成随便两种赛道就可以让三辆车都能在上面放

之后剩下的裸跑2-SAT就完事

加边？

对于限制$x选p则y选q$

分类讨论：

x不能放p：不加边

x能放p但y不能放q：(x,p)连(x,另一种车)

其他的：(x,p)连(y,q)，(y,另一种)连(x,另一种)

完结，时间复杂度$O(2^{d}*n)$

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100069;
template<typename TP>inline void read(TP &_t)
{
    TP _r=0,_f=1;char _c=getchar();
    while(_c<'0'||_c>'9'){if(_c=='-')_f=-1;_c=getchar();}
    while(_c>='0'&&_c<='9'){_r=_r*10+_c-'0';_c=getchar();}
    _t=_r*_f;
}
inline void gc(int &_t)
{
    char _c=getchar();
    while(_c<'A'||_c>'C') _c=getchar();
    _t=_c;
}
struct ban{int x,p,y,q;ban(){}ban(int x,int p,int y,int q):x(x),p(p),y(y),q(q){}}b[N];
int n,d;
char trackstr[N];
int track[N];
int xpos[10],xc;
int m;


struct sumireko{int to,ne;}e[N<<2];
int he[N],ecnt;
void addline(int f,int t)
{
    e[++ecnt].to=t;
    e[ecnt].ne=he[f];
    he[f]=ecnt;
}

int bl[N],ba;
int dep[N],low[N],da;
int sta[N],stp;
bool ins[N];
void tj(int x)
{
    dep[x]=low[x]=++da;
    sta[++stp]=x,ins[x]=1;
    for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)
    {
        if(!dep[t]) tj(t),low[x]=min(low[x],low[t]);
        else if(ins[t]) low[x]=min(low[x],dep[t]);
    }
    if(dep[x]==low[x])
    {
        ba++;
        int px=0;
        while(px!=x)
        {
            px=sta[stp--];
            bl[px]=ba,ins[px]=0;
        }
    }
}

bool check()
{
    for(int i=1;i<=n;i++) if(bl[i]==bl[i+n]) return 0;
    return 1;
}
inline int pt(int x,int p)
{
    switch(track[x])
    {
        case 0:{return p==1?x:x+n;break;}
        default:{return p==0?x:x+n;break;}
    }
}
inline int op(int x,int p)
{
    switch(track[x])
    {
        case 0:{return p==1?x+n:x;break;}
        default:{return p==0?x+n:x;break;}
    }
}
void memclr()
{
    memset(bl,0,sizeof(bl));
    memset(dep,0,sizeof(dep));
    memset(low,0,sizeof(low));
    memset(he,0,sizeof(he));
    ecnt=ba=da=stp=0;
}

int xi,yi,pi,qi;
int main()
{
    read(n),read(d);
    scanf("%s",trackstr+1);
    for(int i=1;i<=n;i++) switch(trackstr[i])
    {
        case 'x':{xpos[++xc]=i;break;}
        default:{track[i]=trackstr[i]-'a';break;}
    }
    read(m);
    for(int i=1;i<=m;i++)
    {
        read(xi),gc(pi),read(yi),gc(qi);
        b[i]=ban(xi,pi-'A',yi,qi-'A');
    }
    for(int s=0;s<(1<<d);s++)
    {
        memclr();
        for(int i=1;i<=d;i++) track[xpos[i]]=((s>>(i-1))&1);
        for(int i=1;i<=m;i++)
        {
            int x=b[i].x,p=b[i].p,y=b[i].y,q=b[i].q;
            if(track[x]==p) continue;
            if(track[y]==q) addline(pt(x,p),op(x,p));
            else addline(pt(x,p),pt(y,q)),addline(op(y,q),op(x,p));
        }
        for(int i=1;i<=n*2;i++)
            if(!dep[i]) tj(i);
        if(check())
        {
            for(int i=1;i<=n;i++)
                if(bl[i]<bl[i+n]) putchar(track[i]==0?'B':'A');
                else putchar(track[i]==2?'B':'C');
            return 0;
        }
    }
    printf("-1");
    return 0;
}

View Code