#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分 暴力