2 条题解

  • 1
    @ 2023-12-29 17:41:24

    快乐的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";
            }
    

    然后就可以赌一赌规律了

    我跑了 1010 分钟左右,跑到了 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
    

    如果考场机子比较差,可以根据 5 75~7 的情况赌一赌 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
    上传者