CF568C New Language

· · 题解

UPD on 2020/11/7

完善了部分叙述,通过了hack数据

首先要注意题面不能读错,我一开始看错了题就郁闷半天...

他是已经给出了每个字母的划分方案,我们只需要构造

其次我们看向题目中给出的限制条件,应该非常眼熟吧,就是2-SAT题里面给出的限制条件啊...所以这题和2-SAT一定有关系,具体地:

  1. 我们每个位置要么属于V要么属于C,这个说明每个变量有2个取值

  2. 我们每个限制只是关于两个变量

所以这个是2-SAT-2啦,也就是说,如果我们能建立一个图的话,就能够判断一个串是否满足题目限制

先考虑怎么建出图...如果有一个第i个选V第j个就选C我们就这样连边

然后我们显然对于一个固定串,他的集合都已经定好了,而2-SAT跑出来的合法性判定不合法的话,说明这个串不符合要求

在考虑构造...好像没啥很快的做法?看一眼数据范围n<=200,我们直接枚举哪一位比他大吧!

也就是说枚举哪一位刚好比s大,那之后的是任意位置,只要满足2-SAT的合法性判定每个位置放的尽可能小(不难发现就是每个集合的第一个字符qwq),那之前的和S相同即可

这样子我们好像就可以构建出一个串了?又因为我们从最后向前枚举哪一位比题目要求的大,所以构造出来的第一个串一定是最小的!

这个题也就做完了!复杂度..由于m是n^2级别,所以O(n^3)

最后要感谢xht37神仙提供灵感

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;

const int MAXN = 207, L = 33, MAXM = 3e5;
int n, m, k, a[L], b[L][2], vis[MAXN << 1];
char s[MAXN];
int home[MAXM], nxt[MAXM], to[MAXM], ccnt;

inline void ct(int x, int y) {
    ccnt++;
    nxt[ccnt] = home[x];
    home[x] = ccnt;
    to[ccnt] = y;
}

int st[MAXM], tp;

bool dfs(int x) {
    if(vis[x > n ? x - n : x + n])return 0;
    //如果他已经有v了
    vis[x] = 1;
    st[++tp] = x;
    for(int i = home[x]; i; i = nxt[i]) {
        int v = to[i];
        if(!vis[v] && !dfs(v))return 0;
    }
    return 1;
}

inline bool pd(int C) {
    for(int i = 1; i <= n << 1; ++i)vis[i] = 0;
    for(int i = 1; i <= C; ++i) {
        if(!dfs(i + a[s[i] - 'a' + 1]*n))return 0;
        //之前已经填好的
    }
    for(int i = C + 1; i <= n; ++i) {
        if(vis[i])s[i] = b[1][0] + 'a' - 1;
        else if(vis[i + n])s[i] = b[1][1] + 'a' - 1;
        //这一部分是处理后面任意的填的部分
        else {
            int x = min(b[1][0], b[1][1]), y = max(b[1][0], b[1][1]);
            tp = 0;
            if(dfs(i + a[x]*n))s[i] = x + 'a' - 1;
            else {
                while(tp)vis[st[tp--]] = 0;//要清空....
                if(dfs(i + a[y]*n))s[i] = y + 'a' - 1;
                else return 0;
            }  //不行了,这个位置放啥都不行
        }
    }
    return 1;
}

map<char, int> p;
int main() {
    scanf("%s", s + 1);
    k = strlen(s + 1);
    p['V'] = 0, p['C'] = 1;//真,假
    b[k + 1][0] = b[k + 1][1] = k + 1;
    for(int i = k, t[2] = {k + 1, k + 1}; i; i--) {
        t[a[i] = p[s[i]]] = i;
        b[i][0] = t[0];
        b[i][1] = t[1];
    }//预处理每个位置靠后能放的第一个不同集合字符
    scanf("%d%d", &n, &m);
    for(int i = 1, x, y, s1, t1, s2, t2; i <= m; ++i) {
        scanf("%d", &x);
        scanf("%s", s + 1);
        y = strlen(s + 1);
        s1 = x + p[s[y]] * n;
        s2 = s1 > n ? s1 - n : s1 + n;
        scanf("%d", &x);
        scanf("%s", s + 1);
        y = strlen(s + 1);
        t1 = x + p[s[y]] * n;
        t2 = t1 > n ? t1 - n : t1 + n;
        //这个是2-SAT建图,s2t2只是转化到另一个点
        ct(s1, t1);
        ct(t2, s2);

    }
    scanf("%s", s + 1);
    n = strlen(s + 1);
    if(pd(n))return printf("%s\n", s + 1), 0;
    else if(b[1][0] == k + 1 || b[1][1] == k + 1)return puts("-1"), 0;
    for(int i = n; i; --i) {
        int c = s[i] - 'a' + 2, x = min(b[c][0], b[c][1]), y = max(b[c][0], b[c][1]);
        //c刚好填比他大的
        if(x != k + 1) {
            s[i] = x + 'a' - 1;
            if(pd(i))return printf("%s\n", s + 1), 0;
        }
        if(y != k + 1) {
            s[i] = y + 'a' - 1;
            if(pd(i))return printf("%s\n", s + 1), 0;
        }
    }
    puts("-1");
    return 0;
}

像2-SAT这样的神仙算法就是支持边填边构造方案啊

EX : 被hack原因是我们在尝试去填每个集合的最小字符后,没有及时清空..