洛谷P3825/LOJ2305/UOJ317/BZOJ4945[NOI2017]游戏（2-SAT）

2024-03-18 11:49:34

没有x地图的话是一个比较明显的2-SAT。对于$(i,h_i,j,h_j)$，若$h_i$不能用，则无视掉；若$h_j$不能用，则连边$(i,i')$，表示选$i$就要选$i'$，那么按照2-SAT的定义，$i$肯定不会出现在答案中；否则连边$(i,j),(j',i')$（若$j$不选$h_j$，则$i$必定不选$h_i$）。

而对于x地图，最简单的想法是$O(3^d)$枚举，肯定TLE，但是我们发现若禁掉A，可选B、C；禁掉B，可选A、C。这样已经把A、B、C都考虑了一遍，也就是说枚举只用$O(2^d)$，总共$O(2^d(n+m))$，可过。

洛谷P3825/LOJ2305/UOJ317/BZOJ4945[NOI2017]游戏（2-SAT）
#include<cstdio>
#include<cctype>
#include<cstring>
const int N=50005;
const int M=100050;
char rB[1<<21],*rS,*rT;
inline char gc(){return rS==rT&&(rT=(rS=rB)+fread(rB,1,1<<21,stdin),rS==rT)?EOF:*rS++;}
inline char rdc(){
    char c=gc();
    while(!isalpha(c))c=gc();
    return c;
}
inline int rdi(){
    char c=gc();
    while(!isdigit(c))c=gc();
    int x=c&15;
    for(c=gc();isdigit(c);c=gc())x=(x<<3)+(x<<1)+(c&15);
    return x;
}
int a[M],b[M],G[N<<1],to[M<<1],nxt[M<<1],sz=0,dfn[N<<1],col[N<<1],dfsc,st[N<<1],sl=-1,cnt,idx[10],idc=0,n;
char ban[N],x[M],y[M],ans[N];
inline void adde(int u,int v){
    to[++sz]=v;nxt[sz]=G[u];G[u]=sz;
}
inline int getid(int x,char c){
    if(ban[x]!='C')return x+n*(c=='C');
    return x+n*(c=='B');
}
inline int gotid(int x){  //已知x求x'
    return x>n?x-n:x+n;
}
int dfs(int u){
    int i,v,lowu=dfn[u]=++dfsc,lowv;
    st[++sl]=u;
    for(i=G[u];i;i=nxt[i])if(!dfn[v=to[i]]){
        lowv=dfs(v);
        if(lowv<lowu)lowu=lowv;
    }else if(!col[v=to[i]]&&dfn[v]<lowu)lowu=dfn[v];
    if(lowu==dfn[u]){
        ++cnt;
        do{
            v=st[sl--];
            col[v]=cnt;
        }while(v!=u);
    }
    return lowu;
}
inline bool check(){
    int i;
    memset(dfn,0,sizeof(dfn));
    memset(col,0,sizeof(col));dfsc=cnt=0;
    for(i=1;i<=(n<<1);++i)if(!dfn[i])dfs(i);
    for(i=1;i<=n;++i){
        if(col[i]==col[i+n])return 0;
        if(col[i]<col[i+n])ans[i]=ban[i]=='A'?'B':'A';
        else ans[i]=ban[i]=='C'?'B':'C';
    }
    for(i=1;i<=n;++i)putchar(ans[i]);
    return 1;
}
int main(){
    int m,i,u,v,S;
    char c;
    n=rdi();rdi();
    for(i=1;i<=n;++i)if((c=toupper(rdc()))=='X')idx[idc++]=i;
    else ban[i]=c;
    m=rdi();
    for(i=0;i<m;++i){a[i]=rdi();x[i]=rdc();b[i]=rdi();y[i]=rdc();}
    for(S=0;S<(1<<idc);++S){
        memset(G,0,sizeof(G));sz=0;
        for(i=0;i<idc;++i)ban[idx[i]]=(S&(1<<i))?'A':'B';
        for(i=0;i<m;++i)if(ban[a[i]]!=x[i]){
            if(ban[b[i]]==y[i]){
                u=getid(a[i],x[i]);
                adde(u,gotid(u));
            }else{
                u=getid(a[i],x[i]);v=getid(b[i],y[i]);
                adde(u,v);adde(gotid(v),gotid(u));
            }
        }
        if(check())return 0;
    }
    putchar('-');putchar('1');
    return 0;
}
View Code

但是在UOJ上又神仙出了毒瘤数据，把$O(2^d(n+m))$卡满了，导致卡常也过不去，这时就需要随机化乱搞了，把$0$到$2^d-1$扔进数组里，random_shuffle一下（事实证明手写的没STL的好），然后在时限里面尽可能的多跑几组数据，时限快到了就输出-1（我卡到1.983s，1.98sWA，1.985sTLE）

洛谷P3825/LOJ2305/UOJ317/BZOJ4945[NOI2017]游戏（2-SAT）
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
//玄学优化
#include<cstdio>
#include<cctype>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
const int N=50005;
const int M=100050;
char rB[1<<21],*rS,*rT;
inline char gc(){return rS==rT&&(rT=(rS=rB)+fread(rB,1,1<<21,stdin),rS==rT)?EOF:*rS++;}
inline char rdc(){
    char c=gc();
    while(!isalpha(c))c=gc();
    return c;
}
inline int rdi(){
    char c=gc();
    while(!isdigit(c))c=gc();
    int x=c&15;
    for(c=gc();isdigit(c);c=gc())x=(x<<3)+(x<<1)+(c&15);
    return x;
}
int a[M],b[M],G[N<<1],to[M<<1],nxt[M<<1],sz=0,dfn[N<<1],col[N<<1],dfsc,st[N<<1],sl=-1,cnt,idx[10],idc=0,n,S[270];
char ban[N],x[M],y[M],ans[N];
inline void Swap(int &a,int &b){int t=a;a=b;b=t;}
inline void adde(int u,int v){
    to[++sz]=v;nxt[sz]=G[u];G[u]=sz;
}
inline int getid(int x,char c){
    if(ban[x]!='C')return x+n*(c=='C');
    return x+n*(c=='B');
}
inline int gotid(int x){
    return x>n?x-n:x+n;
}
int dfs(int u){
    int i,v,lowu=dfn[u]=++dfsc,lowv;
    st[++sl]=u;
    for(i=G[u];i;i=nxt[i])if(!dfn[v=to[i]]){
        lowv=dfs(v);
        if(lowv<lowu)lowu=lowv;
    }else if(!col[v=to[i]]&&dfn[v]<lowu)lowu=dfn[v];
    if(lowu==dfn[u]){
        ++cnt;
        do{
            v=st[sl--];
            col[v]=cnt;
        }while(v!=u);
    }
    return lowu;
}
inline bool check(){
    int i;
    memset(dfn,0,sizeof(dfn));
    memset(col,0,sizeof(col));dfsc=cnt=0;
    for(i=1;i<=(n<<1);++i)if(!dfn[i])dfs(i);
    for(i=1;i<=n;++i){
        if(col[i]==col[i+n])return 0;
        if(col[i]<col[i+n])ans[i]=ban[i]=='A'?'B':'A';
        else ans[i]=ban[i]=='C'?'B':'C';
    }
    for(i=1;i<=n;++i)putchar(ans[i]);
    return 1;
}
int main(){
    int m,i,k,u,v;
    char c;
    n=rdi();rdi();
    for(i=1;i<=n;++i)if((c=toupper(rdc()))=='X')idx[idc++]=i;
    else ban[i]=c;
    m=rdi();
    for(i=0;i<m;++i){a[i]=rdi();x[i]=rdc();b[i]=rdi();y[i]=rdc();}
    for(i=0;i<(1<<idc);++i)S[i]=i;
    srand(time(NULL));
    random_shuffle(S,S+(1<<idc));
    for(k=0;k<(1<<idc)&&clock()<1.983*CLOCKS_PER_SEC;++k){
        memset(G,0,sizeof(G));sz=0;
        for(i=0;i<idc;++i)ban[idx[i]]=(S[k]&(1<<i))?'A':'B';
        for(i=0;i<m;++i)if(ban[a[i]]!=x[i]){
            if(ban[b[i]]==y[i]){
                u=getid(a[i],x[i]);
                adde(u,gotid(u));
            }else{
                u=getid(a[i],x[i]);v=getid(b[i],y[i]);
                adde(u,v);adde(gotid(v),gotid(u));
            }
        }
        if(check())return 0;
    }
    putchar('-');putchar('1');
    return 0;
}
View Code

最后提供一个判断解可行性的spj（-1要手工检查一下）：

洛谷P3825/LOJ2305/UOJ317/BZOJ4945[NOI2017]游戏（2-SAT）
#include<cstdio>
#include<cctype>
#include<cstring>
char s[50005],ans[50005];
int main(){
    FILE *fin=fopen("game.in","rb"),*ftest=fopen("game.out","rb");
    int n,m,i,u,v;
    char x,y;
    fscanf(fin,"%d%d%s",&n,&m,s+1);
    for(i=1;i<=n;++i)s[i]=toupper(s[i]);
    fscanf(ftest,"%s",ans+1);
    if(strlen(ans+1)!=n){
        puts("Too long or too short.");
        return 0;
    }
    for(i=1;i<=n;++i)if(s[i]==ans[i]){
        printf("Running the car %d which is banned.\n",i);
        return 0;
    }
    fscanf(fin,"%d",&m);
    for(i=1;i<=m;++i){
        fscanf(fin,"%d %c %d %c",&u,&x,&v,&y);
        if(ans[u]==x&&ans[v]!=y){
            printf("Do not follow rule %d.\n",i);
            return 0;
        }
    }
    puts("Accepted.");
    return 0;
}
View Code

 

上一篇：Java Object-Oriented：day11 【 红包案例】


下一篇：【JZOJ6273】欠钱