「NOI2017」游戏

「NOI2017」游戏

Problem

有ABC三辆赛车，\(n\) 场比赛，每场比赛有不能用的赛车（有的可以用所有的赛车）

有 \(m\) 个约束条件，为 \(i\) 比赛用 \(c_i\) 车则 \(j\) 比赛用 \(c_j\) 车

Solution

观察到每场比赛只能用两种车

而且三种车的比赛非常之少 \(\le8\)

考虑二进制枚举，将其转化为前两种情况 (AB/BC)

为什么不用枚举AC呢？

是因为A or C 已经包含在了 (AB/BC) 中

现在就转化成了模板的2-SAT

难点在于代码实现

Code

 #include <bits/stdc++.h>
using namespace std;
const int N = 5e4 * 2 + 10, M = 1e5 + 10;
int n, d, m, low[N], dfn[N], tot = 0, cnt = 0, scc[N];
stack <int> sta; bool insta[N];
vector <int> e[N];
string s;
int a[N], b[N];
char ha[N], hb[N];
vector <int> x;
void clear() {
	int l = n * 2 + 1;
	memset(low, 0, sizeof(int) * l), memset(dfn, 0, sizeof(int) * l); tot = cnt = 0;
	memset(scc, 0, sizeof(int) * l);
	for (int i = 1; i < l; i++) e[i].clear();
}
void tarjan(int u) {
	low[u] = dfn[u] = ++tot, insta[u] = 1, sta.emplace(u);
	for (auto v : e[u]) 
		if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
		else if (insta[v]) low[u] = min(low[u], dfn[v]);
	if (low[u] == dfn[u]) {
		cnt++; int v = 0;
		do v = sta.top(), sta.pop(), insta[v] = 0, scc[v] = cnt; while (v != u);
	}
}
void put() {
	for (int i = 1; i <= n; i++) if (scc[i] == scc[i + n]) return;
	for (int i = 1; i <= n; i++)
		if (scc[i] < scc[i + n]) cout << (s[i] == 'A' ? 'B' : 'A');
		else cout << (s[i] == 'C' ? 'B' : 'C');
	exit(0);
}
void solve() {
	for (int S = 0; S < 1 << d; S++) {
		clear();
		for (int i = 1; i <= d; i++) s[x[i - 1]] = S >> i - 1 & 1 ? 'A' : 'B';
		for (int i = 1; i <= m; i++) {
			if (ha[i] == s[a[i]]) continue;
			if (hb[i] == s[b[i]]) {
				if (ha[i] == 'C' || (ha[i] == 'B' && s[a[i]] == 'C')) e[a[i] + n].emplace_back(a[i]);
				else e[a[i]].emplace_back(a[i] + n);
			}
			int ada = 0, adb = 0;
			if (ha[i] == 'C' || (ha[i] == 'B' && s[a[i]] == 'C')) ada += n;
			if (hb[i] == 'C' || (hb[i] == 'B' && s[b[i]] == 'C')) adb += n;
			e[a[i] + ada].emplace_back(b[i] + adb);
			ada = n - ada, adb = n - adb;
			e[b[i] + adb].emplace_back(a[i] + ada);
		}
		for (int i = 1; i <= n * 2; i++) if (!dfn[i]) tarjan(i);
		put();
	}
}
int main() {
	cin.tie(nullptr) -> ios::sync_with_stdio(0);
	cin >> n >> d >> s >> m; s = ' ' + s;
	for (int i = 1; i <= n; i++) s[i] -= 32, s[i] == 'X' ? x.emplace_back(i) : 0;
	for (int i = 1; i <= m; i++) cin >> a[i] >> ha[i] >> b[i] >> hb[i];
	solve();
	cout << "-1";
	return 0;
}