NOI2017 [NOI2017]游戏【2-sat】

题目

题目背景

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

题目描述

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

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

nn 场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=xaabxcbc表示小 L 计划进行88 场游戏，其中第11 场和第55 场的地图类型是x，适合所有赛车，第22 场和第33 场的地图是a，不适合赛车A，第44 场和第77 场的地图是b，不适合赛车B，第66 场和第88 场的地图是c，不适合赛车C。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 (i, h_i, j, h_j)(i,h

i

,j,h

j

) 来描述，表示若在第ii 场使用型号为h_ih

i

的车子，则第jj 场游戏要使用型号为h_jh

j

的车子。

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

输入格式

输入第一行包含两个非负整数n, dn,d 。

输入第二行为一个字符串SS 。n, d, Sn,d,S 的含义见题目描述，其中SS 包含nn 个字符，且其中恰好dd 个为小写字母xx 。

输入第三行为一个正整数mm ，表示有mm 条用车规则。接下来mm 行，每行包含一个四元组i, h_i, j, h_ji,h

i

,j,h

j

，其中i, ji,j 为整数，h_i, h_jh

i

,h

j

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

输出格式

输出一行。

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

若有解，则包含一个长度为nn 的仅包含大写字母A、B、C的字符串，表示小 L 在这nn 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。

输入样例

3 1

xcc

1

1 A 2 B

输出样例

ABA

提示

【样例1解释】

小 L 计划进行33 场游戏，其中第11 场的地图类型是x，适合所有赛车，第22 场和第33 场的地图是c，不适合赛车C。

小 L 希望：若第11 场游戏使用赛车A，则第22 场游戏使用赛车B。那么为这33 场游戏分别安排赛车A、B、A可以满足所有条件。若依次为33 场游戏安排赛车为BBB或BAA时，也可以满足所有条件，也被视为正确答案。但依次安排赛车为AAB或ABC时，因为不能满足所有条件，所以不被视为正确答案。

题解

其实是比较裸的一道2-sat，主要思维难点在于处理"x"

我们先这样想，如果没有x，会是怎样？

每场比赛不能用三种车中以一种，就只有两种选择，选且只选一个

每场比赛之间会有影响

这就可以2-sat建模了

每场比赛的两种车分别作为两个对立的点

对于m个限制：

①如果\(h_i\)本身就是\(i\)不能使用的车，\(i\)肯定不会选，直接忽视

②若\(h_j\)是\(j\)不能选的车，那么\(i\)就不能选\(h_i\)，由\(h_i\)对立点\(h_i'\)连有向边

③否则\(h_i\)连向\(h_j\)，\(h_j'\)连向\(h_i'\)

跑tarjan缩点判断即可，输出方案按拓扑逆序【其实就是Scc编号正序】

撒花~~

等等......

好像还忘了x

题目中x最多为8，可以直接枚举所有x的限制

但\(3^d\)会T

我们只枚举x为a或者b，这样子每个x点三种车都有机会选到，如果这样情况下仍然无解，那么肯定就无解了

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define cls(s) memset(s,0,sizeof(s))

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

using namespace std;

const int maxn = 100005,maxm = 200005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}

	return out * flag;

}

int h[maxn],ne = 1;

struct EDGE{int to,nxt;}ed[maxm];

inline void build(int u,int v){ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;}

const char alpha[] = {"abc"};

char s[maxn],P[maxn],A[maxn],B[maxn];

int pos[20],n,d,m,p1[maxn],p2[maxn];

int Scc[maxn],dfn[maxn],low[maxn],st[maxn],top,cnt,scci;

inline int id(int u,char c){

	if (c == 'a') return u;

	if (c == 'b' && P[u] == 'a') return u;

	return u + n;

}

inline char Get(int u,int v){

	if (P[u] == 'a') return v ? 'B' : 'C';

	if (P[u] == 'b') return v ? 'A' : 'C';

	return v ? 'A' : 'B';

}

void dfs(int u){

	dfn[u] = low[u] = ++cnt;

	st[++top] = u;

	Redge(u){

		if (!dfn[to = ed[k].to]){

			dfs(to);

			low[u] = min(low[u],low[to]);

		}else if (!Scc[to]) low[u] = min(low[u],dfn[to]);

	}

	if (dfn[u] == low[u]){

		scci++;

		do{

			Scc[st[top]] = scci;

		}while (st[top--] != u);

	}

}

bool solve(){

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

		h[i] = Scc[i] = dfn[i] = low[i] = 0;

	top = cnt = scci = 0; ne = 1;

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

		int a = p1[i],b = p2[i];

		int x = id(a,A[i]),y = id(b,B[i]);

		int x1 = x > n ? x - n : x + n,y1 = y > n ? y - n : y + n;

		if (A[i] == P[a]) continue;

		if (B[i] == P[b]) build(x,x1);

		else build(x,y),build(y1,x1);

	}

	for (int i = 1; i <= (n << 1); i++) if (!dfn[i]) dfs(i);

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

	/*puts("");

	for (int i = 1; i <= (n << 1); i++) printf("%d:%d\n",i,Scc[i]); puts("");*/

	for (int i = 1; i <= n; i++) putchar(Get(i,Scc[i] < Scc[i + n]));

	return true;

}

bool Dfs(int u){

	if (u > d) return solve();

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

		P[pos[u]] = alpha[i];

		if (Dfs(u + 1)) return true;

	}

	return false;

}

int main(){

	n = read(); d = read(); d = 0;

	scanf("%s",s + 1);

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

		if (s[i] == 'x') pos[++d] = i;

		else P[i] = s[i];

	m = read();

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

		scanf("%d %c %d %c",&p1[i],&A[i],&p2[i],&B[i]);

		A[i] += 'a' - 'A'; B[i] += 'a' - 'A';

	}

	if (!Dfs(1)) puts("-1");

	return 0;

}

巴特西

NOI2017 [NOI2017]游戏【2-sat】

题目

输入格式

输出格式

输入样例

输出样例

提示

题解

最新文章

热门文章

巴特西

NOI2017 [NOI2017]游戏 【2-sat】

题目

输入格式

输出格式

输入样例

输出样例

提示

题解

最新文章

热门文章

NOI2017 [NOI2017]游戏【2-sat】