1 条题解
-
0
题解:黑白画作中的8×8棋盘计数(P3364)
一、题目分析
本题要求在一个n×m的黑白棋盘图案中,统计右下角为白色的8×8子棋盘的数量。关键在于理解以下两点:
- 棋盘结构:相邻方块颜色不同,因此任意8×8子棋盘的右下角颜色由其起始位置决定。
- 条件判断:仅统计右下角为白色的子棋盘。
二、核心思路
-
有效区域计算:
对于n×m的画布,能够完整容纳8×8子棋盘的区域为(n-7) × (m-7)
。例如,当n=8时,只有1行可以作为起始行;n=9时,有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; }
四、步骤详解
-
输入处理:
读取n、m和c,当三者均为0时终止程序。 -
计算有效区域:
将n和m分别减去7,得到有效区域的行数和列数。 -
判断乘积奇偶性:
- 若乘积为偶数,直接输出
(n*m)/2
。 - 若乘积为奇数:
- 当c=1时,输出
(n*m)/2 +1
。 - 当c=0时,输出
(n*m)/2
。
- 当c=1时,输出
- 若乘积为偶数,直接输出
五、关键点总结
-
数学推导:
- 有效区域计算:
n' = n-7
,m' = m-7
。 - 奇偶性决定黑白子棋盘数量关系,原画布右下角颜色决定多余的一个子棋盘颜色。
- 有效区域计算:
-
复杂度分析:
- 时间复杂度:O(1),每次测试用例仅需常数时间计算。
- 空间复杂度:O(1),仅需存储输入参数和中间结果。
-
边界处理:
- 当n或m小于8时,有效区域为非正数,乘积为0,结果正确。
该解法通过数学分析和奇偶性判断,高效地解决了子棋盘计数问题,确保在题目约束下快速输出结果。
- 1
信息
- ID
- 2365
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者