1 条题解

  • 0
    @ 2025-5-27 21:51:11

    题解:黑白画作中的8×8棋盘计数(P3364)

    一、题目分析

    本题要求在一个n×m的黑白棋盘图案中,统计右下角为白色的8×8子棋盘的数量。关键在于理解以下两点:

    1. 棋盘结构:相邻方块颜色不同,因此任意8×8子棋盘的右下角颜色由其起始位置决定。
    2. 条件判断:仅统计右下角为白色的子棋盘。

    二、核心思路

    1. 有效区域计算
      对于n×m的画布,能够完整容纳8×8子棋盘的区域为(n-7) × (m-7)。例如,当n=8时,只有1行可以作为起始行;n=9时,有2行可以作为起始行,依此类推。

    2. 奇偶性分析

      • 若有效区域的行数n'=n-7和列数m'=m-7的乘积为偶数,说明黑白子棋盘数量相等,直接返回(n'×m')/2
      • 若乘积为奇数,说明黑白子棋盘数量相差1。此时需根据原画布右下角的颜色(参数c)判断:
        • c=1(原画布右下角为白色),则白色子棋盘多1个,返回(n'×m')/2 +1
        • c=0,则黑色子棋盘多1个,返回(n'×m')/2

    三、代码解析

    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    int main() {
        int n, m, c;
        while (scanf("%d%d%d", &n, &m, &c)) {
            if (n == 0 && m == 0 && c == 0) break;  // 终止条件
            
            n = n - 7;  // 有效行数
            m = m - 7;  // 有效列数
            
            if ((n * m) % 2 == 0) {
                // 乘积为偶数,黑白数量相等
                cout << (n * m) / 2 << endl;
            } else {
                // 乘积为奇数,根据原画布右下角颜色判断
                if (c == 1) cout << (n * m) / 2 + 1 << endl;
                else cout << (n * m) / 2 << endl;
            }
        }
        return 0;
    }
    

    四、步骤详解

    1. 输入处理
      读取n、m和c,当三者均为0时终止程序。

    2. 计算有效区域
      将n和m分别减去7,得到有效区域的行数和列数。

    3. 判断乘积奇偶性

      • 若乘积为偶数,直接输出(n*m)/2
      • 若乘积为奇数:
        • 当c=1时,输出(n*m)/2 +1
        • 当c=0时,输出(n*m)/2

    五、关键点总结

    1. 数学推导

      • 有效区域计算:n' = n-7m' = m-7
      • 奇偶性决定黑白子棋盘数量关系,原画布右下角颜色决定多余的一个子棋盘颜色。
    2. 复杂度分析

      • 时间复杂度:O(1),每次测试用例仅需常数时间计算。
      • 空间复杂度:O(1),仅需存储输入参数和中间结果。
    3. 边界处理

      • 当n或m小于8时,有效区域为非正数,乘积为0,结果正确。

    该解法通过数学分析和奇偶性判断,高效地解决了子棋盘计数问题,确保在题目约束下快速输出结果。

    • 1

    信息

    ID
    2365
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者