NOIP2004提高组.虫食算

题目

184. 虫食算

算法标签: $dfs$, 剪枝优化, 高斯消元

思路

因为数据范围很小并且有解, 是一个暴搜问题, 但是直接枚举一定会超时, 时间复杂度是$26!$

因此需要进行剪枝优化, 可以在搜索过程中每枚举一个字母看是否有矛盾
如果右侧所有数字都已经确定, 那么进位$t$确定

可行性剪枝

1. 如果发现$(a+b+t)\mathrm{mod}n\ne c$矛盾
2. 如果当前位是最高位, $a+b+t\ge n$矛盾, 因为最高位不能进位
3. 如果$t$未确定, 那么$t$只能取值$0$或者$1$, 如果$(a+b+0)\mathrm{mod}n\ne c$并且$(a+b+1)\mathrm{mod}n\ne c$, 发现矛盾
4. 如果$t$未确定, 那么$t$只能取值$0$或者$1$, 当前位是最高位, $a+b+0\ge n$矛盾

优化搜索顺序

1. 从右向左枚举, 那么$t$会尽早确定, 会少很多分支情况
2. 对每个字母从大到小枚举, 最高位更容易进位, 搜索空间就会变少

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 30;

int n;
string s[3];
int q[N], w[N];
bool vis[N];

bool check() {
   
	int t = 0;
	for (int i = n - 1; i >= 0; --i) {
   
		int a = s[0][i] - 'A';
		int b = s[1][i] - 'A';
		int c = s[2][i] - 'A';
		a = w[a], b = w[b], c = w[c];

		if (a != -1 && b != -1 && c != -1) {
   
			if (t != -1) {
   
				if ((a + b + t) % n != c) return false;
				if (i == 0 && a + b + t >= n) return false;
				t = (a + b + t) / n;
			}
			// 进位未确定的情况, t可以取0或者1
			else {
   
				if ((a + b) % n != c && (a + b + 1) % n != c) return false;
				if (i == 0 && a + b >= n) return false;
			}
		}
		// 进位未确定
		else t = -1;
	}

	return true;
}

bool dfs(int u) {
   
	if (u == n) return true;

	for (int i = n - 1; i >= 0; --i) {
   
		if (!vis[i]) {
   
			w[q[u]] = i;
			vis[i] = true;
			if (check() && dfs(u + 1)) return true;
			w[q[u]] = -1;
			vis[i] = false;
		}
	}

	return false;
}

int main() {
   
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < 3; ++i) cin >> s[i];

	int k = 0;
	for (int i = n - 1; i >= 0; --i) {
   
		for (int j = 0; j < 3; ++j) {
   
			int c = s[j][i] - 'A';
			if (!vis[c]) {
   
				q[k++] = c;
				vis[c] = true;
			}
		}
	}

	memset(vis, false, sizeof vis);
	memset(w, -1, sizeof w);
	dfs(0);

	for (int i = 0; i < n; ++i) cout << w[i] << " ";
	cout << "\n";

	return 0;
}