Moe's CF Life

喵~ 主人，今天我们来解决一道关于多米诺骨牌的有趣问题吧！这道题就像逗猫棒一样，看起来简单，但需要我们动动小脑筋才能抓住重点哦。别担心，有本猫娘在，保证让你轻松搞定！

题目：A. Domino (Codeforces 353A)

题目大意

有一个叫瓦莱拉的蓝孩子，他有一排 n 个多米诺骨牌，喵。每个骨牌都分成上下两半，每一半上都有一个从 1 到 6 的数字。

瓦莱拉特别喜欢偶数，所以他希望所有骨牌上半部分数字的总和是偶数，同时下半部分数字的总和也是偶数。

为了达到这个目标，他可以花费 1 秒钟的时间将任意一个多米诺骨牌旋转 180 度。旋转之后，这个骨牌的上下两半数字就会交换位置。

我们的任务就是，帮瓦莱拉计算一下，他最少需要多少秒（也就是最少旋转多少次）才能实现他的愿望。如果无论如何都办不到，就告诉他 -1 喵~

解题思路

这道题的核心在于奇偶性分析，就像猫咪能敏锐地察觉到罐头开罐的声音一样，我们也要对数字的奇偶性敏感起来！

我们来分析一下旋转操作会带来什么影响：

假设我们旋转第 i 个骨牌，它原来的数字是 (xi, yi)（上 xi，下 yi）。旋转后就变成了 (yi, xi)。设旋转前所有上半部分数字总和是 Sum_upper，下半部分是 Sum_lower。旋转后，新的总和会变成：

New_Sum_upper = Sum_upper - xi + yi
New_Sum_lower = Sum_lower - yi + xi

这里有一个超级重要的发现，喵！我们把两个新总和加起来看看： New_Sum_upper + New_Sum_lower = (Sum_upper - xi + yi) + (Sum_lower - yi + xi) = Sum_upper + Sum_lower 看到了吗？无论我们怎么旋转，所有数字的总和 Sum_total = Sum_upper + Sum_lower 是一个不变量！它永远不会改变。

我们的目标是让 Sum_upper 和 Sum_lower 都变成偶数。两个偶数相加，结果肯定还是偶数。这意味着，最终状态的总和一定是偶数。因为总和是不变的，所以如果一开始 Sum_total 就是奇数，那我们永远也无法达到目标了，对吧？

什么时候 Sum_total 是奇数呢？只有当 Sum_upper 和 Sum_lower 一个是奇数、一个是偶数的时候。所以，我们的第一个结论就出来啦：

如果初始的 Sum_upper 和 Sum_lower 奇偶性不同，直接输出 -1。

好，那如果 Sum_total 是偶数呢？这又分两种情况：

Sum_upper 是偶数，Sum_lower 也是偶数。
- 这不就是我们想要的结果嘛！瓦莱拉什么都不用做，开心地撸猫就行了。所以答案是 0。
Sum_upper 是奇数，Sum_lower 也是奇数。
- 现在两个和都是奇数，我们需要把它们都变成偶数。我们需要一个“魔法操作”来同时改变两个和的奇偶性。
- 回顾一下旋转操作：New_Sum_upper = Sum_upper + (yi - xi)。Sum_upper 的奇偶性要想改变，yi - xi 必须是奇数。而 yi - xi 是奇数，当且仅当 xi 和 yi 的奇偶性不同（一个奇数，一个偶数）。
- 如果 xi 和 yi 一个奇一个偶，那么 yi - xi 是奇数，xi - yi 也是奇数。旋转这个骨牌会让 Sum_upper 和 Sum_lower 的奇偶性同时翻转！
- 所以，如果我们能找到至少一个上下两半数字奇偶性不同的骨牌，我们就可以只旋转这一个骨牌（花费 1 秒），把两个奇数和都变成偶数和。完美！答案就是 1。
- 那如果找不到这样的骨牌呢？也就是说，所有骨牌的上下两半要么都是偶数，要么都是奇数。这样一来，yi - xi 永远是偶数，旋转操作就无法改变任何一个和的奇偶性了。那我们就束手无策啦，只能告诉瓦莱拉这是不可能的，输出 -1。

总结一下我们的策略喵：

计算 Sum_upper 和 Sum_lower。
同时检查是否存在 (xi, yi) 奇偶性不同的骨牌。
根据 Sum_upper 和 Sum_lower 的奇偶性以及是否存在可翻转的骨牌，得出结论。

题解代码 (C++)

这是本猫娘为主人准备好的 C++ 代码，思路和上面讲的一模一样哦~

cpp

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    // 使用快速 I/O，让程序跑得像猫一样快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    int sum_upper = 0;
    int sum_lower = 0;
    // 这个标志用来记录是否存在可以改变奇偶性的“魔法骨牌”
    bool can_flip_parity = false; 

    for (int i = 0; i < n; ++i) {
        int x, y;
        std::cin >> x >> y;
        sum_upper += x;
        sum_lower += y;
        
        // 检查这个骨牌的上下两半奇偶性是否不同
        // 只有旋转这样的骨牌，才能改变总和的奇偶性
        if ((x % 2) != (y % 2)) {
            can_flip_parity = true;
        }
    }

    // 判断上下总和是否为偶数
    bool upper_is_even = (sum_upper % 2 == 0);
    bool lower_is_even = (sum_lower % 2 == 0);

    // Case 1: 两个总和都已经是偶数了，什么都不用做
    if (upper_is_even && lower_is_even) {
        std::cout << 0 << std::endl;
    } 
    // Case 2: 两个总和都是奇数
    else if (!upper_is_even && !lower_is_even) {
        // 我们需要改变奇偶性，看看有没有“魔法骨牌”
        if (can_flip_parity) {
            // 找到了！旋转一次就搞定
            std::cout << 1 << std::endl;
        } else {
            // 没有这样的骨牌，没办法改变奇偶性，任务失败
            std::cout << -1 << std::endl;
        }
    } 
    // Case 3: 一个和是偶数，另一个是奇数
    else {
        // 这种情况总和是奇数，根据我们的不变量理论，不可能成功
        std::cout << -1 << std::endl;
    }

    return 0;
}

题目：A. Domino (Codeforces 353A) ​

题目大意 ​

解题思路 ​

题解代码 (C++) ​

相关知识点介绍：奇偶性 (Parity) ​

题目：A. Domino (Codeforces 353A)

题目大意

解题思路

题解代码 (C++)

相关知识点介绍：奇偶性 (Parity)