【Codeforces 568C】New Language | Mrsrz's blog

2-SAT。

题目大意：

将小写英文字母分成 V 和 C 两个集合。

给定长度为 $n$ 的字符串 $s$ 和 $m$ 条限制，每条限制形如 $u\ \ t_1\ \ v\ \ t_2$ 表示若 $u$ 位置的字符在集合 $t_1$ 中，则 $v$ 位置的集合必须在集合 $t_2$ 中。

要求找到一个长度为 $n$ 的字符串满足所有限制且字典序不小于 $s$。要求输出字典序最小的方案。

题解：

观察限制的形式，显然是个 2-SAT 问题。

这里还要考虑字典序的限制。我们考虑逐位确定。

可以使用类似数位 DP 的方式，记录一个 tag 表示前面考虑的几位是否和 $s$ 的前面几位一样。如果已经不一样了，后面可以随便选，否则需要考虑字典序的问题。

我们通过搜索来确定，考虑到第 $i$ 位时，若 tag 为 $1$ 则需要考虑三种情况：和 $s_i$ 相等、比 $s_i$ 大的最小的 V 集合中的字符、比 $s_i$ 大的最小的 C 集合中的字符。若 tag 为 $0$ 则只需考虑两个集合中最小的字符。

我们通过 2-SAT 来确定这位填 V 和 C 中的元素分别是否可行。就强制这一位选 $1$ 或 $0$ 即可。

由于我们每次往下一层搜索时，都保证当前存在可行方案，所以总共执行 2-SAT 的次数为 $O(n)$ 次。

时间复杂度 $O(n^2+nm)$。

Code：

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=433;
char VC[N],S[N],ans[N];
int n,m,dfn[N],low[N],sta[N],top,bel[N],SCC,idx;
bool vis[N];
vector<int>G[N];
inline void addedge(int u,int v){G[u].push_back(v);}
void dfs(int now){
    low[now]=dfn[now]=++idx;
    sta[++top]=now;
    vis[now]=1;
    for(int to:G[now])
    if(!dfn[to]){
        dfs(to);
        low[now]=min(low[now],low[to]);
    }else if(vis[to])low[now]=min(low[now],dfn[to]);
    if(low[now]==dfn[now]){
        ++SCC;
        int v;
        do{
            v=sta[top--];
            vis[v]=0;
            bel[v]=SCC;
        }while(v!=now);
    }
}
bool doit(int u,bool vs){
    addedge(u+(!vs)*n,u+vs*n);
    idx=SCC=0;
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(bel,0,sizeof bel);
    for(int i=1;i<=2*n;++i)
    if(!dfn[i])dfs(i);
    G[u+(!vs)*n].pop_back();
    for(int i=1;i<=n;++i)
    if(bel[i]==bel[i+n])return 0;
    return 1;
}
void solve(int now,bool tag){
    if(now>n){
        puts(ans+1);
        exit(0);
    }
    bool _0=doit(now,0),_1=doit(now,1);
    if(tag)if((VC[S[now]-'a']=='V'&&_1)||(VC[S[now]-'a']=='C'&&_0)){
        addedge(now+!(VC[S[now]-'a']=='V')*n,now+(VC[S[now]-'a']=='V')*n);
        ans[now]=S[now],solve(now+1,1);
        G[now+!(VC[S[now]-'a']=='V')*n].pop_back();
    }
    int _V=0,_C=0;
    for(int i=tag?(S[now]-'a'+1):0;VC[i]&&!_V;++i)if(VC[i]=='V')_V=i+'a';
    for(int i=tag?(S[now]-'a'+1):0;VC[i]&&!_C;++i)if(VC[i]=='C')_C=i+'a';
    if(_V<_C){
        if(_1&&_V){
            G[now].push_back(now+n);
            ans[now]=_V;
            solve(now+1,0);
            G[now].pop_back();
        }
        if(_0&&_C){
            G[now+n].push_back(now);
            ans[now]=_C;
            solve(now+1,0);
            G[now+n].pop_back();
        }
    }else{
        if(_0&&_C){
            G[now+n].push_back(now);
            ans[now]=_C;
            solve(now+1,0);
            G[now+n].pop_back();
        }
        if(_1&&_V){
            G[now].push_back(now+n);
            ans[now]=_V;
            solve(now+1,0);
            G[now].pop_back();
        }
    }
}
int main(){
    scanf("%s%d%d",VC,&n,&m);
    while(m--){
        int u,v;
        char X[5],Y[5];
        scanf("%d%s%d%s",&u,X,&v,Y);
        int b1=*X=='V',b2=*Y=='V';
        addedge(u+b1*n,v+b2*n);
        addedge(v+!b2*n,u+!b1*n);
    }
    scanf("%s",S+1);
    solve(1,1);
    puts("-1");
    return 0;
}