1 条题解
-
0
40 分纯暴力
#include <bits/stdc++.h> using namespace std; // 0~9 的偏移量 int pos[10] = {4 * 9, 4 * 0, 4 * 1, 4 * 2, 4 * 3, 4 * 4, 4 * 5, 4 * 6, 4 * 7, 4 * 8}; // g[0~4][0~3+偏移量] 即对应数字的 5x4 string g[5] = { "...1222233334..4555566667777888899990000", "...1...2...34..45...6......78..89..90..0", "...122223333444455556666...7888899990..0", "...12......3...4...56..6...78..8...90..0", "...122223333...455556666...7888899990000"}; // 存画完后的内容 int a[5][4]; int ans[10]; // 存每个数字画了几次 // 画画顺序 1234567890 (now==10 对应 0) void dfs(int now) { // 顺利画完了就结束 if (now == 11) { // 看看还有没有没画的位置 bool flag = true; for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) if (a[i][j] > 0) { flag = false; break; } if (flag) { for (int i = 1; i <= 10; i++) cout << ans[i % 10]; exit(0); } return; } // 把 now 画上 t 遍 for (int t = 0; t <= 9; t++) { // 检查每个位置是否画的下 bool flag = true; for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) { // 不用画的位置跳过 if (g[i][j + pos[now % 10]] == '.') continue; // 减去 t 次 a[i][j] -= t; // 检查是否合法，为了方便撤回，哪怕不合法我们也硬减下去 if (a[i][j] < 0) flag = false; } // 做下个数 if (flag) { ans[now % 10] = t; dfs(now + 1); } // 撤回影响 for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) { // 不用画的位置跳过 if (g[i][j + pos[now % 10]] == '.') continue; // 加回来 t 次 a[i][j] += t; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) cin >> a[i][j]; dfs(1); return 0; }优化枚举顺序 40 分
#include <bits/stdc++.h> using namespace std; // 0~9 的偏移量 int pos[10] = {4 * 9, 4 * 0, 4 * 1, 4 * 2, 4 * 3, 4 * 4, 4 * 5, 4 * 6, 4 * 7, 4 * 8}; // g[0~4][0~3+偏移量] 即对应数字的 5x4 string g[5] = { "...1222233334..4555566667777888899990000", "...1...2...34..45...6......78..89..90..0", "...122223333444455556666...7888899990..0", "...12......3...4...56..6...78..8...90..0", "...122223333...455556666...7888899990000"}; // 存画完后的内容 int a[5][4]; int ans[10]; // 存每个数字画了几次 // 画画顺序 2680594137 string id = "2680594137"; // 最佳的 1234567890 出现次数 string best = "9999999999"; string plan = "0000000000"; // now: 0~9 void dfs(int now) { int num = id[now] - '0'; // 顺利画完了就结束 if (now == 10) { // 看看还有没有没画的位置 bool flag = true; for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) if (a[i][j] > 0) { flag = false; break; } if (flag) { for (int i = 0; i <= 9; i++) plan[(i + 9) % 10] = ans[i] + '0'; best = min(best, plan); } return; } // 把 num 画上 t 遍 for (int t = 0; t <= 9; t++) { // 检查每个位置是否画的下 bool flag = true; for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) { // 不用画的位置跳过 if (g[i][j + pos[num % 10]] == '.') continue; // 减去 t 次 a[i][j] -= t; // 检查是否合法，为了方便撤回，哪怕不合法我们也硬减下去 if (a[i][j] < 0) flag = false; } // 做下个数 if (flag) { ans[num % 10] = t; dfs(now + 1); } // 撤回影响 for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) { // 不用画的位置跳过 if (g[i][j + pos[num % 10]] == '.') continue; // 加回来 t 次 a[i][j] += t; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) cin >> a[i][j]; dfs(0); cout << best << "\n"; return 0; }剪枝 100 分
#include <bits/stdc++.h> using namespace std; // 0~9 的偏移量 int pos[10] = {4 * 9, 4 * 0, 4 * 1, 4 * 2, 4 * 3, 4 * 4, 4 * 5, 4 * 6, 4 * 7, 4 * 8}; // g[0~4][0~3+偏移量] 即对应数字的 5x4 string g[5] = { "...1222233334..4555566667777888899990000", "...1...2...34..45...6......78..89..90..0", "...122223333444455556666...7888899990..0", "...12......3...4...56..6...78..8...90..0", "...122223333...455556666...7888899990000"}; // 存画完后的内容 int a[5][4]; int ans[10]; // 存每个数字画了几次 // 画画顺序 2680594137 string id = "2680594137"; // 最佳的 1234567890 出现次数 string best = "9999999999"; string plan = "0000000000"; // now: 0~9 void dfs(int now) { int num = id[now] - '0'; // 顺利画完了就结束 if (now == 10) { // 看看还有没有没画的位置 bool flag = true; for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) if (a[i][j] > 0) { flag = false; break; } if (flag) { for (int i = 0; i <= 9; i++) plan[(i + 9) % 10] = ans[i] + '0'; best = min(best, plan); } return; } // 看看后续的有没有覆盖不到的地方 int b[5][4] = {}; // 把所有能覆盖的位置改为 1 for (int i = now; i <= 9; i++) { int num = id[i] - '0'; for (int j = 0; j <= 4; j++) for (int k = 0; k <= 3; k++) if (g[j][k + pos[num]] != '.') b[j][k] = 1; } for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) if (a[i][j] != 0 && b[i][j] == 0) return; // 把 num 画上 t 遍 for (int t = 0; t <= 9; t++) { // 检查每个位置是否画的下 bool flag = true; for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) { // 不用画的位置跳过 if (g[i][j + pos[num % 10]] == '.') continue; // 减去 t 次 a[i][j] -= t; // 检查是否合法，为了方便撤回，哪怕不合法我们也硬减下去 if (a[i][j] < 0) flag = false; } // 做下个数 if (flag) { ans[num % 10] = t; dfs(now + 1); } // 撤回影响 for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) { // 不用画的位置跳过 if (g[i][j + pos[num % 10]] == '.') continue; // 加回来 t 次 a[i][j] += t; } if (!flag) break; } } int main() { ios::sync_with_stdio(false); cin.tie(0); for (int i = 0; i <= 4; i++) for (int j = 0; j <= 3; j++) cin >> a[i][j]; dfs(0); cout << best << "\n"; return 0; }
- 1