傳送門

分析

看了一下題解，正解是高斯消元，然而我不會。。。。。。

于是——搜索！

但直接暴搜的復雜度是 \(O(n!)\) ，肯定會超時，所以需要一些剪枝。

考慮從右向左，從上至下枚舉每個數的值。

1. 搜完時是一定不能有進位的。

2. 可以每次搜索時 \(check\) 一下。

   如果有進位，那么 \(add\) 一定是 \(1\) 。則我們判斷時只需考慮 \(str[1][x]+str[2][x]=str[3][x]\) 與 \(str[1][x]+str[2][x]+1=str[3][x]\) ，這兩個條件滿足其中一個即可，也不需考慮每次的 \(add\) 。

3. 枚舉時如果是最后一排的值，就再判斷是否滿足 \(str[1][x]+str[2][x]+add=str[y][x]\) 。

代碼

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;template <typename T> inline void read(T &x) {T f = 1; x = 0; char c;for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);x *= f;
}int n;
int ans[30];
char str[4][30];
bool used[30];int num(char p) {return p - 'A' + 1;
}bool check(int x) {for (int i = x - 1; i; --i) {int f1 = ans[num(str[1][i])], f2 = ans[num(str[2][i])], f3 = ans[num(str[3][i])];if (f1 == -1 || f2 == -1 || f3 == -1) continue;if ((f1 + f2) % n != f3 && (f1 + f2 + 1) % n != f3) return false;}return true;
}void dfs(int x, int y, int add) {if (!x) {if (!add) {for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);exit(0);}else return;}if (!check(x)) return;if (ans[num(str[y][x])] == -1)if (y != 3) {for (int i = n - 1; i >= 0; --i)if (!used[i]) {used[i] = 1, ans[num(str[y][x])] = i;dfs(x, y + 1, add);used[i] = 0, ans[num(str[y][x])] = -1;}}else {for (int i = n - 1; i >= 0; --i)if (!used[i]) {int sum = ans[num(str[1][x])] + ans[num(str[2][x])] + add;if (sum % n != i) continue;else {used[i] = 1, ans[num(str[y][x])] = i;dfs(x - 1, 1, sum / n);used[i] = 0, ans[num(str[y][x])] = -1;}}}else {if (y != 3) dfs(x, y + 1, add);else {int sum = ans[num(str[1][x])] + ans[num(str[2][x])] + add;if (sum % n != ans[num(str[y][x])]) return;else dfs(x - 1, 1, sum/n);}}
}int main() {memset(ans, -1, sizeof(ans));cin >> n;for (int i = 1; i <= 3; ++i) scanf("%s", str[i] + 1);dfs(n, 1, 0);return 0;
}

轉載于:https://www.cnblogs.com/hlw1/p/11456136.html

總結

以上是生活随笔為你收集整理的洛谷P1092 虫食算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。