欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

loj2305 noi2017 游戏

程序员文章站 2022-04-09 08:54:19
思路 既然$x$的数量那么小,我们就可以先把每个$x$搜索一遍。 枚举x的时候不需要把$a,b,c$全枚举一遍,只要枚举其中的两个就可以枚举到当前 ......

思路

既然\(x\)的数量那么小,我们就可以先把每个\(x\)搜索一遍。

枚举x的时候不需要把\(a,b,c\)全枚举一遍,只要枚举其中的两个就可以枚举到当前位置选任何车的情况。

然后就变成了只有\('a','b','c'\)的序列。寻找满足题目要求的方案。

\(2-sat\)模型。

连边的时候注意一些技巧,否则\(if\)写到自闭。。

\(uoj\)上会被卡掉\(3\)分。实在懒得去卡常了233

代码

/*
* @author: wxyww
* @date:   2019-04-29 09:08:01
* @last modified time: 2019-04-30 14:32:38
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 100010; 
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
vector<int>e[n];
char a[n],tmp[n];
int n,d,m;
int opp[n];
#define add(x,y) e[x].push_back(y)
int val[n];

int tot,dfn[n],low[n],vis[n],sta[n],coljs,col[n],top;

void tarjan(int u) {
    int k = e[u].size();
    dfn[u] = low[u] = ++tot;
    sta[++top] = u;vis[u] = 1;
    for(int i = 0;i < k;++i) {
        int v = e[u][i];
        if(!dfn[v]) {
            tarjan(v);low[u] = min(low[u],low[v]);
        }
        else if(vis[v]) low[u] = min(low[u],low[v]);
    }
    if(dfn[u] == low[u]) {
        ++coljs;
        do {
            int x = sta[top--];
            col[x] = coljs;
            vis[x] = 0;
        }while(sta[top + 1] != u);
    }
}


int t1[n],t2[n];
char h1[n],h2[n];

int get_u(int x,char y) {
    if(a[x] == 'a') return y == 'b' ? x : x + n;
    return y == 'a' ? x : x + n;
}

#define ote(x) x > n ? x - n : x + n

void solve() {
    memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    memset(col,0,sizeof(col));
    coljs = 0,tot = 0;top = 0;
    for(int i = 1;i <= n + n;++i) e[i].clear();
    for(int i = 1;i <= m;++i) {
        if(a[t1[i]] == h1[i] - 'a' + 'a') continue;
        int u = get_u(t1[i],h1[i]);
        if(a[t2[i]] == h2[i] - 'a' + 'a') {
            add(u,ote(u));
            continue;
        }
        int v = get_u(t2[i],h2[i]);
        add(u,v);add(ote(v),ote(u));
    }
    for(int i = 1;i <= n + n;++i) if(!dfn[i]) tarjan(i);

    for(int i = 1;i <= n;++i) if(col[i] == col[i + n]) return;

    for(int i = 1;i <= n;++i) {
        if(col[i] < col[i + n]) {
            if(a[i] == 'a') putchar('b');
            else putchar('a');
        }
        else {
            if(a[i] == 'c') putchar('b');
            else putchar('c');
        }
    }
    exit(0);
}

void dfs(int pos) {
    if(pos == n + 1) {
        solve();
        return;
    }
    if(tmp[pos] != 'x') dfs(pos + 1);
    else {
        a[pos] = 'a';
        dfs(pos + 1);
        a[pos] = 'b';
        dfs(pos + 1);
    }
}

int main() {
    // freopen("2305/game3.in","r",stdin);
    n = read(),d = read();
    scanf("%s",tmp + 1);
    memcpy(a + 1,tmp + 1,n);
    m = read();
    for(int i = 1;i <= m;++i) {
        t1[i] = read();h1[i] = getchar();while(h1[i] != 'a' && h1[i] != 'b' && h1[i] != 'c') h1[i] = getchar();
        t2[i] = read();h2[i] = getchar();while(h2[i] != 'a' && h2[i] != 'b' && h2[i] != 'c') h2[i] = getchar();
    }

    dfs(1);
    puts("-1");
    return 0;
}