bzoj 4945 &UOJ 317 [Noi2017]游戏

bzoj 4945 &UOJ 317 [Noi2017]游戏

​​ 题目背景 狂野飙车是小 L 最喜欢的游戏。与其他业余玩家不同的是，小 L 在玩游戏之余，还精于研究游戏的设计，因此他有着与众不同的游戏策略。

题目描述 小 L 计划进行

n

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

小 L 的赛车有三辆，分别用大写字母A、B、C表示。地图一共有四种，分别用小写字母x、a、b、c表示。其中，赛车A不适合在地图a上使用，赛车B不适合在地图b上使用，赛车C不适合在地图c上使用，而地图x则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有d张。

n

n 场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=xaabxcbc表示小 L 计划进行

8

8 场游戏，其中第

1

1 场和第

5

5 场的地图类型是x，适合所有赛车，第

2

2 场和第

3

3 场的地图是a，不适合赛车A，第

4

4 场和第

7

7 场的地图是b，不适合赛车B，第

6

6 场和第

8

8 场的地图是c，不适合赛车C。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组

(i, h_i, j, h_j)

(i,hi,j,hj) 来描述，表示若在第

i

i 场使用型号为

h_i

hi 的车子，则第

j

j 场游戏要使用型号为

h_j

hj 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “-1’’（不含双引号）。

输入输出格式 输入格式：

输入第一行包含两个非负整数

n, d

n,d 。

输入第二行为一个字符串

S

S 。

n, d, S

n,d,S 的含义见题目描述，其中

S

S 包含

n

n 个字符，且其中恰好

d

d 个为小写字母

x

x 。

输入第三行为一个正整数

m

m ，表示有

m

m 条用车规则。接下来

m

m 行，每行包含一个四元组

i, h_i, j, h_j

i,hi,j,hj ，其中

i, j

i,j 为整数，

h_i, h_j

hi,hj 为字符a、b或c，含义见题目描述。

输出格式：

输出一行。

若无解输出 “-1’’（不含双引号）。

若有解，则包含一个长度为

n

n 的仅包含大写字母A、B、C的字符串，表示小 L 在这

n

n 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。

输入输出样例 输入样例#1： 复制

3 1 xcc 1 1 A 2 B 输出样例#1： 复制

ABA s

一开始想3^8枚举 显然时间复杂度不资瓷

那么可以枚举不选哪两个即可做到枚举所有情况并且复杂度是2^8*(n+m)

那么原有的点看成除去不能选的那个 要么选这个要么选那个

限制看成是 x->y y’->x’ 如果我要i,x对应的j,y是不可以选的那么就从i,x连向自己的另一个状态即可表示无论如何也不能选这种状态

剩下就拓扑一下okay

uoj有人卡常 特判一下才搞定

#include#include#include#include#include#includeusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}const int M=1e5+10;const int N=1e5+10;bool flag;struct RL{ int id1,id2;char op1[1],op2[1];}R[M];struct node{ int x,y,next;}data[M<<1];char s[N];bool stackf[N];int h[N],q[N],top,cnt,tot,pos[10],dfn[N],id[N][2],num,low[N],S,col[N],b[N],op[N],n,D,m,d[N];inline void tarjan(int x){ dfn[x]=low[x]=++tot;q[++top]=x;stackf[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);else if(stackf[y]) low[x]=min(low[x],dfn[y]); } if (low[x]==dfn[x]){ int y;++S; do{ y=q[top--];stackf[y]=0;b[y]=S; }while(y!=x); }} inline int tr(int iid,char c){ if (s[iid]=='a') return c>'b';return c>'a';}inline void tr1(int iid,int op1){ if (s[iid]=='a') {op1?putchar('C'):putchar('B');} else if (s[iid]=='b') {op1?putchar('C'):putchar('A');} else op1?putchar('B'):putchar('A');}inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].x=x;}inline void gao(){ memset(h,0,sizeof(h));num=0;memset(dfn,0,sizeof(dfn));S=0;tot=0; for (int i=1;i<=m;++i){ if (R[i].op1[0]==s[R[i].id1]) continue; int x=tr(R[i].id1,R[i].op1[0]),y=tr(R[i].id2,R[i].op2[0]); int id1=R[i].id1,id2=R[i].id2; if (R[i].op2[0]==s[R[i].id2]) insert1(id[id1][x],id[id1][x^1]); else insert1(id[id1][x],id[id2][y]),insert1(id[id2][y^1],id[id1][x^1]); } for (int i=1;i<=cnt;++i) if (!dfn[i]) tarjan(i); for (int i=1;i<=n;++i){ if (b[id[i][0]]==b[id[i][1]]) return; op[b[id[i][0]]]=b[id[i][1]];op[b[id[i][1]]]=b[id[i][0]]; }flag=1;}inline void dfs(int x){ if (x>D){gao();return;} if ((double) clock() / CLOCKS_PER_SEC >= 0.8) { puts("-1"); exit(0); } s[pos[x]]='a';dfs(x+1);if (flag) return; s[pos[x]]='b';dfs(x+1);}int main(){ freopen("bzoj4945.in","r",stdin); n=read();D=read();scanf("%s",s+1);m=read(); for (int i=1;i<=n;++i) for (int j=0;j<2;++j) id[i][j]=++cnt; for (int i=1;i<=n;++i) if (s[i]=='x') pos[++tot]=i; for (int i=1;i<=m;++i){ R[i].id1=read();scanf("%s",R[i].op1);R[i].op1[0]+=32; R[i].id2=read();scanf("%s",R[i].op2);R[i].op2[0]+=32; }dfs(1);if(!flag) {puts("-1");return 0;}int nm=num;num=0;memset(h,0,sizeof(h)); for (int i=1;i<=nm;++i){ int x=data[i].x,y=data[i].y; if (b[x]==b[y]) continue; insert1(b[x],b[y]);++d[b[y]]; }queueq;memset(col,-1,sizeof(col)); for (int i=1;i<=S;++i) if (!d[i]) q.push(i); while(!q.empty()){ int x=q.front();q.pop(); if (col[x]==-1) col[x]=0,col[op[x]]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (!--d[y]) q.push(y); } } for (int i=1;i<=n;++i){ if (col[b[id[i][0]]]) tr1(i,0); else tr1(i,1); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。