【题解】LOJ 2305 「NOI2017」游戏

Problem

有三种车 $A,B,C$ ,四种地图 $a,b,c,x$
$A$ 不适合 $a$, $B$ 不适合 $b$ , $C$ 不适合 $c$ ,而 $x$ 最多只有 $d$ 个

接下该给出比赛地图列表,如 $S=xaabxcbc$ ,和一些要求如 $(i,h_i,j,h_j)$ 表示在第 $i$ 场选了 $h_i$ 就必须在第 $j$ 场选 $h_j$

求满足所有要求的方案

Thought

貌似枚举能过 $50pt$ (雾

显然,如果 $d=0$ ,这就是一个裸的 $2-SAT$ 问题,按照限制连边后算强联通分量即可

若 $d\neq 0$ ,则会有能够选择三个点的情况,显然不能用 $3-SAT$
但是由于 $d$ 较小,我们可以尝试强行将其变为 $2-SAT$ 的情况,只要其包含了 $3-SAT$ 的所有解即可

那么每个点只需要枚举两次不适合的点即可将所有状态枚举出来(第一次 $AB$ ,第二次 $AC$ ,即可包括 $ABC$ 所有可能)

时间复杂度 $O(2^d(n+m))$

一定要注意的是, $2-SAT$ 需要将所有关系全部连出来,比如说 $X\to Y$ 那么 $Y'\to X'$

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 50010;
const int M = 100010;

int dfn[N << 2], low[N << 2], DFN;
int sta[N << 2], top;
bool vis[N << 2];
int id[N << 2], cnt;

char S[N];

int cho[N][2];

struct Edge {
    int t, n;
}e[(M << 1) + (N << 2)];
int head[N << 2], Etot;
struct Rule {
    int a, ha, b, hb;
}rul[M];
int n, d, m;
int xPos[10], xCnt;

void addedge(int u, int v) {
    e[++ Etot] = {v, head[u]};
    head[u] = Etot;
}

void dfs(int x) {
    dfn[x] = low[x] = ++ DFN;
    sta[++ top] = x; vis[x] = 1;
    for(int i = head[x]; i; i = e[i].n) {
        int t = e[i].t;
        if(!dfn[t]) {
            dfs(t);
            low[x] = min(low[x], low[t]);
        }
        else if(vis[t])
            low[x] = min(low[x], dfn[t]);
    }
    if(low[x] == dfn[x]) {
        ++ cnt;
        while(sta[top] != x) {
            id[sta[top]] = cnt;
            vis[sta[top]] = 0;
            sta[top --] = 0;
        }
        id[sta[top]] = cnt;
        vis[sta[top]] = 0;
        sta[top --] = 0;
    }
}

void tarjan() {
    for(int i = 1; i <= 4 * n; ++ i)
        if(!dfn[i])
            dfs(i);
    for(int i = 1; i <= n; ++ i)
        if(id[i] == id[2 * n + i] || id[n + i] == id[3 * n + i])
            return;
    for(int i = 1; i <= n; ++ i)
        if(id[i] < id[2 * n + i])
            printf("%c", cho[i][0] + 'A' - 1);
        else
            printf("%c", cho[i][1] + 'A' - 1);
    puts("");
    exit(0);
}

void preWork() {
    n = read(); d = read();
    scanf("%s", S + 1);
    for(int i = 1; i <= n; ++ i) {
        if(S[i] == 'a') {
            cho[i][0] = 2;
            cho[i][1] = 3;
        }
        else if(S[i] == 'b') {
            cho[i][0] = 1;
            cho[i][1] = 3;
        }
        else if(S[i] == 'c') {
            cho[i][0] = 1;
            cho[i][1] = 2;
        }
        else
            xPos[++ xCnt] = i;
    }
    m = read();
    for(int i = 1; i <= m; ++ i) {
        rul[i].a = read();
        scanf("%s", S);
        rul[i].ha = S[0] - 'A' + 1;

        rul[i].b = read();
        scanf("%s", S);
        rul[i].hb = S[0] - 'A' + 1;
    }
}
int getRev(int x) {
    return x > 2 * n ? x - 2 * n : x + 2 * n;
}
void edgeBuild() {
    memset(head, 0, sizeof(head));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(id, 0, sizeof(id));
    DFN = cnt = Etot = 0;
    for(int i = 1; i <= n; ++ i) {
        addedge(i, 3 * n + i);
        addedge(3 * n + i, i);
        addedge(1 * n + i, 2 * n + i);
        addedge(2 * n + i, 1 * n + i);
    }
    for(int i = 1; i <= m; ++ i) {
        int X = 0, Y = 0;
        if(cho[rul[i].a][0] == rul[i].ha) X = rul[i].a;
        if(cho[rul[i].a][1] == rul[i].ha) X = n + rul[i].a;
        if(!X) continue;
        if(cho[rul[i].b][0] == rul[i].hb) Y = rul[i].b;
        if(cho[rul[i].b][1] == rul[i].hb) Y = n + rul[i].b;
        if(!Y)
            addedge(X, getRev(X));
        else {
            addedge(X, Y);
            addedge(getRev(Y), getRev(X));
        }
    }
}
int main() {
    preWork();
    for(int i = 0; i < (1 << d); ++ i) {
        for(int j = 1; j <= d; ++ j) {
            if(i & (1 << (j - 1))) {
                cho[xPos[j]][0] = 2;
                cho[xPos[j]][1] = 3;
            }
            else {
                cho[xPos[j]][0] = 1;
                cho[xPos[j]][1] = 3;
            }
        }
        edgeBuild();
        tarjan();
    }
    puts("-1");
    return 0;
}
Comments

添加新评论