[ABC166F] Three Variables Game

Three Variables Game の 传送门

Solution

首先，我们每次操作只会修改两个数。

所以考虑 dfs 枚举操作的顺序，但是这让时间复杂度变为 \(O(2^n)\)，不能接受。

但是，我们可以判断当 a < 0 || b < 0 || c < 0 时，就退出，这样可以减少绝大部分状态。

边界条件：当枚玩 \(n\) 个后，输出用 \(ans\) 数组存下的每次的操作，然后退出程序。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, v[3];
string s[N];
int ans[N];
// v[0] : a
// v[1] : b
// v[2] : c
void dfs(int u) {
	if (v[0] < 0 || v[1] < 0 || v[2] < 0) { return; }
	if (u > n) {
		puts("Yes");
		for (int i = 1; i <= n; ++i) { cout << s[i][ans[i]] << "\n"; }
		exit(0);
	}
	for (int i = 0; i < 2; ++i) {
		ans[u] = i;
		++v[s[u][i] - 'A'];
		--v[s[u][!i] - 'A'];
		dfs(u + 1);
		--v[s[u][i] - 'A'];
		++v[s[u][!i] - 'A'];
	}
	return;
}
int main() {
	cin >> n >> v[0] >> v[1] >> v[2];
	for (int i = 1; i <= n; ++i) { cin >> s[i]; }
	dfs(1);
	puts("No");
	return 0;
}