UOJ#317. 【NOI2017】游戏
? 解题记录 ? ? UOJ ? ? 2-SAT ?    2018-08-13 11:56:01    557    0    0

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

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

nn 场游戏的地图可以用一个小写字母组成的字符串描述。例如:S=xaabxcbc−−−−−−−−−−−S=xaabxcbc_ 表示小 L 计划进行 8 场游戏,其中第 1 场和第 5 场的地图类型是 x,适合所有赛车,第 2 场和第 3 场的地图是 a,不适合赛车 A,第 4 场和第 7 场的地图是 b,不适合赛车 B,第 6 场和第 8 场的地图是 c,不适合赛车 C。

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

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

输入格式

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

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

n,d,Sn,d,S 的含义见题目描述,其中 SS 包含 nn 个字符,且其中恰好 dd 个为小写字母 xx

输入第三行为一个正整数 mm ,表示有 mm 条用车规则。接下来 mm 行,每行包含一个四元组 i,hi,j,hji,hi,j,hj ,其中 i,ji,j 为整数,hi,hjhi,hj 为字符 A 、B 或 C,含义见题目描述。

输出格式

输出一行。

若无解,输出 “-1”(不含双引号)。

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

样例一

input

3 1
xcc
1
1 A 2 B

output

ABA

explanation

小 L 计划进行 3 场游戏,其中第 1 场的地图类型是 x,适合所有赛车,第 2 场和第 3 场的地图是 c,不适合赛车 C。

小 L 希望:若第 1 场游戏使用赛车 A,则第 2 场游戏使用赛车 B。

那么为这 3 场游戏分别安排赛车 A、B、A 可以满足所有条件。

若依次为 3 场游戏安排赛车为 BBB 或 BAA 时,也可以满足所有条件,也被视为正确答案。但依次安排赛车为 AAB 或 ABC 时,因为不能满足所有条件,所以不被视为正确答案。

样例二

见下载文件中的 ex_game2.in 与 ex_game2.ans

限制与约定

测试点编号nnddmm其他性质
12≤2004≤4
2n≤n
35≤50010≤10
4n≤n
510≤100020≤20
68≤8
720≤200040≤40S中只包含c
8
98≤8S中只包含x或c
10
11100≤10000200≤200S中只包含c
12
138≤8S中只包含x或c
14
155000≤50000010000≤10000
168≤8S中只包含x或c
17
1850000≤5000000100000≤100000
198≤8S中只包含x或c
20

时间限制:1s1s

空间限制:512MB

2-SAT的模板题,有8个可以用三个车的赛道,只需要2^8枚举就可以了。

注意到其实我们只需要枚举8个赛道中的每一个可以选AB或AC。因为这样就涵盖了8个赛道可以允许ABC的所有情况。

数据贼强,判无解使用ctime优化。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<stack>
#include<cstring>
#include<ctime>
#define L(x) ((x) << 1)
#define R(x) (((x) << 1) + 1)
using namespace std;
const int maxn = 1e5 + 5;
struct edge {
	int v, next;
}e[maxn << 2];
char s[maxn];
int head[maxn << 1], cnt, st;
int xpos[15], isx[maxn], n, m;
int a[maxn], c[maxn], ans[maxn];
char b[maxn][2], d[maxn][2];
void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}

stack<int > stk;
int vis[maxn << 1], dfn[maxn << 1], low[maxn << 1], dcnt, bcnt, blk[maxn << 1];
int tarjan(int u) {
	dfn[u] = low[u] = ++dcnt;
	stk.push(u), vis[u] = 1;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(dfn[v]) {if(vis[v]) low[u] = min(low[u], low[v]);}
		else low[u] = min(low[u], tarjan(v));
	}
	if(low[u] == dfn[u]) {
		int v = 0; ++bcnt;
		do {
			v = stk.top();
			stk.pop(), vis[v] = 0;
			blk[v] = bcnt;
		} while(v != u);
	}
	return low[u];
}

int tmp;
inline int GetP(int x, char C) {
	tmp = C - 'A';
	if(s[x] - 'a' == tmp) return -1;
	if(tmp > s[x] - 'a') --tmp;
	return (x << 1) + tmp;
}
inline int GetN(int x, int now) {
	tmp = now - L(x);
	if(s[x] - 'a' <= tmp) ++tmp;
	return tmp;
}

bool _2SAT() {
	memset(dfn, 0, sizeof(int) * (R(n) + 5));
	//memset(low, 0, sizeof(int) * (R(n) + 5));
	bcnt = dcnt = 0;
	for(register int i = L(1); i <= R(n); ++i) 
		if(!dfn[i]) tarjan(i);
	for(register int i = 1; i <= n; ++i) {
		if(blk[L(i)] == blk[R(i)]) return false;
		if(blk[L(i)] < blk[R(i)]) ans[i] = GetN(i, L(i));
		else ans[i] = GetN(i, R(i));
	}
	return true;
}

void work(int a, char A, int b, char B) {
	int pa = GetP(a, A), pb = GetP(b, B);
	if(pa == -1) return ;
	if(pb == -1) return adde(pa, pa ^ 1), void();
	adde(pa, pb), adde(pb ^ 1, pa ^ 1);
}

void ADDE() {
	memset(head, 0, sizeof(int) * (R(n) + 5)), cnt = 0;
	for(register int i = 1; i <= m; ++i) {
		work(a[i], b[i][0], c[i], d[i][0]);
	}
}

void dfs(int step) {
	if(step == *xpos + 1) {
		if(clock() - st > 800000) printf("-1"), exit(0);
		ADDE();
		if(_2SAT()) {
			for(register int i = 1; i <= n; ++i)
				printf("%c", ans[i] + 'A');
			exit(0);
		}
		return ;
	}
	for(register int i = 0; i < 2; ++i) {
		s[xpos[step]] = 'a' + i;
		dfs(step + 1);
	}
}

int main() {
	st = clock();
	scanf("%d%d", &n, &m);
	scanf("%s", s + 1);
	for(register int i = 1; i <= n; ++i)
		if(s[i] == 'x') xpos[++(*xpos)] = i, isx[i] = 1;
	scanf("%d", &m);
	for(register int i = 1; i <= m; ++i) {
		scanf("%d%s%d%s", &a[i], b[i], &c[i], d[i]);
	}
	dfs(1);
	printf("-1");
	return 0;
}

上一篇: COGS 2396. [HZOI 2015]有标号的强连通图计数 I

下一篇: BZOJ4659:Lcm

557 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航