2 条题解
-
1
快乐的70分暴力搜索
#include <bits/stdc++.h> using namespace std; const int MAXN = 10; const int MAXM = 10; int n, m, ans; int cntAns[MAXN * MAXM + 5]; int cnt[MAXN + 5][MAXM + 5]; // 每个位置被几只马踩了 int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1}; void dfs(int x, int y, int now) { // 棋盘看完了 if (x > n + 1) { ans = max(ans, now); cntAns[now]++; return; } int xx, yy; // 下一个位置 yy = y + 1; if (yy > m + 1) xx = x + 1, yy = 2; else xx = x; // 当前位置不放马 dfs(xx, yy, now); // 当前位置能放马的话就试试看放个马 if (!cnt[x][y]) { for (int i = 0; i < 8; i++) cnt[x + dx[i]][y + dy[i]]++; dfs(xx, yy, now + 1); for (int i = 0; i < 8; i++) cnt[x + dx[i]][y + dy[i]]--; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; // 棋盘从 (2,2) ~ (n+1,m+1) // 用到了 (0,0) ~ (n+3,m+3) dfs(2, 2, 0); cout << ans << " " << cntAns[ans] << "\n"; return 0; }
由此可以改的快乐打表程序
for (n = 1; n <= 10; n++) for (m = n; m <= 10; m++) { ans = 0; memset(cntAns, 0, sizeof(cntAns)); // 棋盘从 (2,2) ~ (n+1,m+1) // 用到了 (0,0) ~ (n+3,m+3) dfs(2, 2, 0); cout << n << " " << m << " " << ans << " " << cntAns[ans] << "\n"; }
然后就可以赌一赌规律了
我跑了 分钟左右,跑到了
7 8 28 2
的位置。... 4 4 8 6 4 5 10 3 4 6 12 3 4 7 14 3 4 8 16 3 4 9 18 3 4 10 20 3 5 5 13 1 5 6 15 2 5 7 18 1 5 8 20 2 5 9 23 1 5 10 25 2 6 6 18 2 6 7 21 2 6 8 24 2 6 9 27 2 6 10 30 2 7 7 25 1 7 8 28 2
如果考场机子比较差,可以根据 的情况赌一赌 qx 说的那个规律。
cin >> n >> m; if (n > m) swap(n, m); if (n < 5) { // 棋盘从 (2,2) ~ (n+1,m+1) // 用到了 (0,0) ~ (n+3,m+3) dfs(2, 2, 0); cout << ans << " " << cntAns[ans] << "\n"; } else { if (n % 2 == 1 && m % 2 == 1) cout << n * m / 2 + 1 << " " << 1 << "\n"; else cout << n * m / 2 << " " << 2 << "\n"; }
qx 说的第二种做法那个减枝非常妙!
信息
- ID
- 1382
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 459
- 已通过
- 10
- 上传者