猫娘教你铺骨牌！Codeforces 50A Domino piling 解题喵~

哈咯，各位主人，你们好呀！咱是乃爱的猫娘，今天又要带大家来攻克一道算法题啦，喵~ 这次我们要看的是一道非常经典又可爱的入门题，Codeforces 上的 50A - Domino piling。别看它简单，里面可藏着一些有趣的小知识呢！

---

题目大意（是什么问题喵？）

想象一下，我们有一块 M × N 大小的矩形棋盘，就像一块大大的巧克力，喵~ 然后我们有无限多个 2 × 1 大小的多米诺骨牌。

我们的任务是，把尽可能多的骨牌放到这块棋盘上。放置的时候要遵守几个规矩哦：

1. 每一块骨牌必须不多不少，正好盖住两个相邻的方格。
2. 骨牌之间不能重叠，不可以打架！
3. 所有骨牌都必须乖乖地待在棋盘内部，不能跑到外面去。

那么问题来了，我们最多能放下多少块骨牌呢？

举个栗子：

• 如果棋盘是 2 × 4 的，我们可以完美地放下 4 块骨牌。
• 如果棋盘是 3 × 3 的，我们可以放下 4 块骨牌，会剩下一个孤零零的格子。

是不是很简单易懂呢，喵？

---

解题思路（猫猫的思考时间！）

拿到这个问题，咱的猫猫头脑开始转动啦！(ฅ'ω'ฅ)

首先，我们来算算棋盘一共有多大。一个 M × N 的棋盘，总共就有 M * N 个小方格。 然后，每一块多米诺骨牌，它的大小是 2 × 1，也就是说，它会占用 2 个小方格。

我们想让放下的骨牌数量最多，其实就是想让骨牌覆盖的总面积最大。

那么，一个面积为 M * N 的地方，最多能塞进多少个面积为 2 的小东西呢？ 直觉告诉我们，应该是总面积除以单个面积，也就是 (M * N) / 2，对吧？

让我们用爪爪来验证一下这个想法：

情况一：当总面积 M * N 是偶数时

如果 M 或者 N 中至少有一个是偶数，那么总面积 M * N 就一定是偶数。 这意味着，理论上整个棋盘的面积可以被 2 整除，我们有可能用骨牌完美地铺满整个棋盘！ 比如说，如果 M 是偶数，我们可以把棋盘看成 M/2 行，每行都用 N 个横着放的 1×2 骨牌铺满。这样，总共就能放下 (M/2) * N = (M * N) / 2 个骨牌。 同理，如果 N 是偶数也一样。 所以，当总面积是偶数时，答案就是 (M * N) / 2。

情况二：当总面积 M * N 是奇数时

这种情况只会在 M 和 N 都是奇数的时候发生。 总面积是奇数，但每个骨牌都占 2 个格子（偶数）。无论我们放多少个骨牌，它们覆盖的总面积永远是偶数。 所以，奇数面积的棋盘是不可能被完美铺满的，喵呜~ 至少会有一个小格子被孤单地剩下来。 那么，我们能覆盖的最大面积就是 M * N - 1，这是一个偶数。 因此，最多能放下的骨牌数量就是 (M * N - 1) / 2。

奇妙的整合！

我们分析了两种情况，难道要写 if-else 来判断吗？ 其实不用那么麻烦哦！计算机编程里有一个非常方便的东西叫做“整型除法”。 当我们计算 (M * N) / 2 并且 M 和 N 都是整数时：

• 如果 M * N 是偶数，比如 8，那么 8 / 2 的结果就是 4。
• 如果 M * N 是奇数，比如 9，那么 9 / 2 在数学上是 4.5，但在整型除法里，小数部分会被无情地丢掉，结果也是 4！这正好就等于 (9 - 1) / 2。

所以，不管总面积是奇数还是偶数，我们都可以用同一个简单的公式 (M * N) / 2 来得到答案！是不是超级方便，喵~

---

题解代码（看咱的代码喵！）

想通了之后，代码就变得非常简单啦！

#include <iostream>

int main() {
    // 为了让输入输出快一点点，虽然这题数据很小用不上，但养成好习惯嘛~
    std::ios_base::sync_with_stdio(false);
    std.cin.tie(NULL);

    int m, n;
    
    // 喵~ 读取棋盘的长和宽
    std::cin >> m >> n;

    // 总面积就是 M * N 啦
    int total_squares = m * n;

    // 每个骨牌占两格，所以直接用总面积除以2就好啦~
    // C++ 的整型除法会自动向下取整，正好解决了奇数面积的问题，超方便的喵！
    int max_dominoes = total_squares / 2;

    // 把答案告诉大家
    std::cout << max_dominoes << std::endl;

    return 0;
}

---

知识点介绍（来学习新知识啦！）

这道题虽然简单，但它巧妙地利用了一个核心的编程概念：

整型除法 (Integer Division)

在 C++、Java、Python（使用 // 运算符）等许多编程语言中，当两个整数相除时，结果也会是一个整数。这个过程不是四舍五入，而是直接截断小数部分（向零取整）。

举个栗子喵：

• 10 / 2 结果是 5
• 9 / 2 在数学中是 4.5，但在整型除法中，.5 被丢弃，结果是 4
• -9 / 2 在数学中是 -4.5，结果是 -4

它在本题中的妙用： 正是因为这个特性，我们不需要去写额外的逻辑来判断 M * N 的奇偶性。

• 当 M * N 为偶数时， (M * N) / 2 正常计算。
• 当 M * N 为奇数时， (M * N) / 2 的结果会自动向下取整，恰好等于 (M * N - 1) / 2 的值。

这个小技巧在算法竞赛中非常常用，可以简化代码，减少出错的可能。记住它，以后解决类似问题就能更快更准啦！

好啦，今天的解题教室就到这里结束了。希望这篇文章能帮到你哦，喵~ 下次再见！(>^ω^<)