#2305. 「NOI2017」游戏

题目描述

小 L 计划进行 nnn 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 AAA、BBB、CCC 表示。地图一共有四种，分别用小写字母 xxx、aaa、bbb、ccc 表示。

其中，赛车 AAA 不适合在地图 aaa 上使用，赛车 BBB 不适合在地图 bbb 上使用，赛车 CCC 不适合在地图 ccc 上使用，而地图 xxx 则适合所有赛车参加。

适合所有赛车参加的地图并不多见，最多只会有 ddd 张。

nnn 场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=xaabxcbc 表示小L计划进行 888 场游戏，其中第 111 场和第 555 场的地图类型是 xxx，适合所有赛车，第 222场和第 333场的地图是 aaa，不适合赛车 AAA，第 444 场和第 777 场的地图是 bbb，不适合赛车 BBB，第 666 场和第 888 场的地图是 ccc，不适合赛车 CCC。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 (i,hi,j,hj) (i, h_i, j, h_j)(i,hi,j,hj) 来描述，表示若在第 iii 场使用型号为 hih_ihi 的车子，则第 jjj 场游戏要使用型号为 hjh_jhj 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。

如果无解，输出 -1。

输入格式

输入第一行包含两个非负整数 nnn, ddd。

输入第二行为一个字符串 SSS。

nnn, ddd, SSS 的含义见题目描述，其中 SSS 包含 nnn 个字符，且其中恰好 ddd 个为小写字母 xxx。

输入第三行为一个正整数 mmm ，表示有 mmm 条用车规则。

接下来 mmm 行，每行包含一个四元组 i,hi,j,hji,h_i,j,h_ji,hi,j,hj ，其中 i,ji,ji,j 为整数，hi,hjh_i,h_jhi,hj 为字符 AAA 、BBB 或 CCC，含义见题目描述。

输出格式

输出一行。

若无解输出 -1。

样例

样例输入

3 1

xcc

1

1 A 2 B

样例输出

ABA

小 LLL 计划进行 333 场游戏，其中第 111 场的地图类型是 xxx，适合所有赛车，第 222 场和第 333 场的地图是 ccc，不适合赛车 CCC。

小 LLL 希望：若第 111 场游戏使用赛车 AAA，则第 222 场游戏使用赛车 BBB。

那么为这 333 场游戏分别安排赛车 AAA、BBB、AAA 可以满足所有条件。

若依次为 333 场游戏安排赛车为 BBBBBBBBB 或 BAABAABAA 时，也可以满足所有条件，也被视为正确答案。

但依次安排赛车为 AABAABAAB 或 ABCABCABC 时，因为不能满足所有条件，所以不被视为正确答案。

数据范围与提示

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#define maxn 50010

using namespace std;

char s[maxn],ch1[],ch2[];

int n,d,q,w[maxn];

bool flag,mark[maxn];

struct node{

    int a,b,c,d;

    bool operator < (const node &k)const{

        return a<k.a;

    }

}op[maxn];

int findl(int x){

    int l=,r=q,res=;

    while(l<=r){

        int mid=(l+r)>>;

        if(op[mid].a>=x)res=mid,r=mid-;

        else l=mid+;

    }

    return res;

}

int findr(int x){

    int l=,r=q,res=;

    while(l<=r){

        int mid=(l+r)>>;

        if(op[mid].a<=x)res=mid,l=mid+;

        else r=mid-;

    }

    return res;

}

bool check(){

    for(int i=;i<=n;i++){

        if(s[i]=='a'&&w[i]==)return ;

        if(s[i]=='b'&&w[i]==)return ;

        if(s[i]=='c'&&w[i]==)return ;

        if(mark[i]){

            int l=findl(i),r=findr(i);

            for(int j=l;j<=r;j++){

                if(w[i]!=op[j].b)continue;

                if(w[op[j].c]!=op[j].d)return ;

            }

        }

    }

    return ;

}

void dfs(int pos){

    if(flag)return;

    if(pos==n+){

        flag=check();

        if(flag){

            for(int i=;i<=n;i++){

                if(w[i]==)putchar('A');

                else if(w[i]==)putchar('B');

                else putchar('C');

            }

            exit();

        }

        return;

    }

    if(flag)return;

    for(int i=;i<;i++){

        if(flag)return;

        w[pos]=i;

        dfs(pos+);

    }

}

void work1(){

    scanf("%d",&q);

    for(int i=;i<=q;i++){

        scanf("%d%s%d%s",&op[i].a,&ch1,&op[i].c,&ch2);

        mark[op[i].a]=;

        op[i].b=ch1[]-'A';

        op[i].d=ch2[]-'A';

    }

    sort(op+,op+q+);

    dfs();

}

int main(){

    scanf("%d%d",&n,&d);

    scanf("%s",s+);

    if(n<=){work1();return ;}

    else {puts("-1");return ;}

}

35分暴力

巴特西

loj #2305. 「NOI2017」游戏