喵~ C. Odd/Even Increments 奇偶增量问题详解喵~

哈喽，各位程序员哥哥姐姐们好喵~ 今天咱要一起看的是一道非常有趣的逻辑题哦，Codeforces 上的 1669C - Odd/Even Increments。别看它只是个 C 题，里面可藏着一些可爱的小心思呢，一起来看看吧！

---

题目大意

这道题是这样子滴：

给你一个长度为 n 的正整数数组 a。咱可以对这个数组施展两种魔法，而且想用多少次都可以哦！

1. 奇数位魔法：给所有奇数位置（第1、3、5...个）的元素都加上 1。
2. 偶数位魔法：给所有偶数位置（第2、4、6...个）的元素都加上 1。

问题就是：我们能不能通过任意次数的这两种魔法，让数组里所有的数都变成奇数，或者都变成偶数呢？如果可以的话，就输出 "YES"，不然就输出 "NO" 啦，喵~

举个栗子：

• 如果数组是 [1, 2, 1]，我们可以对偶数位置（也就是 a[2]）施法一次，数组就变成 [1, 3, 1]，所有数都是奇数了，所以是 "YES" 喵。
• 如果数组是 [2, 2, 2, 3]，就没办法让所有数的奇偶性都一样了，所以是 "NO" 呢。

---

题解方法

这个问题呀，看起来好像要考虑好多好多次操作，但其实有个小秘密的喵！我们来仔细看看这两种魔法~

• 奇数位魔法只会改变 a[1], a[3], a[5], ... 这些位置的数字。
• 偶数位魔法只会改变 a[2], a[4], a[6], ... 这些位置的数字。

你发现了嘛？这两种魔法是完全独立、互不干扰的！对奇数位置施法，跟偶数位置的数字一点关系都没有哦！反过来也一样喵。

这带来了什么重要的结论呢？

我们来想想奇数位置上的那些数字。当我们对它们施法时，它们的数值都 +1，奇偶性都会同时翻转（奇数变偶数，偶数变奇数）。这意味着，所有奇数位置的数字，它们的奇偶性是'捆绑'在一起的。如果 a[1] 和 a[3] 一开始的奇偶性就不一样（比如一个奇数一个偶数），那不管我们怎么施展奇数位魔法，它们俩的奇偶性永远都会不一样！一个翻转成偶数，另一个就翻转成奇数，永远无法统一，呜...

同样的道理也适用于所有偶数位置的数字。它们也是一个“命运共同体”，要变一起变。

所以呀，咱的目标是让整个数组的奇偶性统一。这只有在奇数位群体和偶数位群体内部的奇偶性都已经统一的情况下才有可能实现。

结论就出来啦！我们只需要检查两件事：

1. 所有奇数位置的数字，它们本身的奇偶性是不是都一样？（比如，a[1], a[3], a[5], ... 是不是都是奇数，或者都是偶数）
2. 所有偶数位置的数字，它们本身的奇偶性是不是都一样？（比如，a[2], a[4], a[6], ... 是不是都是奇数，或者都是偶数）

如果这两个条件同时满足，那我们肯定能成功！比如说，如果奇数位都是奇数，偶数位都是偶数，咱只要对偶数位施法一次，就能让所有数都变成奇数了。反之，只要有一个条件不满足，那就永远无法成功。

所以，这道题就变成了一个简单的检查题啦，是不是很简单对不对喵？

---

题解

下面是 C++ 的代码实现，咱来一步步看懂它喵~

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 检查所有奇数位置 (1-based)，对应数组下标 0, 2, 4, ...
    bool ok_odd_pos = true;
    int parity_odd_pos = a[0] % 2; // 记下第一个奇数位元素的奇偶性
    for (int i = 2; i < n; i += 2) {
        if (a[i] % 2 != parity_odd_pos) {
            ok_odd_pos = false; // 发现一个不一样的，就说明不行啦
            break;
        }
    }

    // 检查所有偶数位置 (1-based)，对应数组下标 1, 3, 5, ...
    bool ok_even_pos = true;
    int parity_even_pos = a[1] % 2; // 记下第一个偶数位元素的奇偶性
    for (int i = 3; i < n; i += 2) {
        if (a[i] % 2 != parity_even_pos) {
            ok_even_pos = false; // 同样，发现不一样的就标记
            break;
        }
    }

    if (ok_odd_pos && ok_even_pos) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

代码解说：

1. solve() 函数是解决每个测试用例的核心函数喵~
2. std::cin >> n; 和随后的循环是读入数组 a。
3. bool ok_odd_pos = true;：咱先立一个 flag，假定奇数位置的数是满足条件的。
4. int parity_odd_pos = a[0] % 2;：这里咱要特别注意！题目的“奇数位置”是 1-based 的，也就是第 1, 3, 5... 个元素。在 C++ 的 0-based 数组里，它们对应的下标是 0, 2, 4, ...。咱先用 a[0] 的奇偶性作为基准。
5. for (int i = 2; i < n; i += 2)：这个循环遍历了所有剩下的奇数位置（下标 2, 4, ...）。
6. if (a[i] % 2 != parity_odd_pos)：如果发现某个元素的奇偶性和基准 parity_odd_pos 不一样，说明奇数位群体内部不统一，就把 ok_odd_pos 设为 false，然后 break 掉，因为已经没必要再检查下去了。
7. 接下来的一段代码对偶数位置（下标 1, 3, 5, ...）做了完全相同的事情。
8. if (ok_odd_pos && ok_even_pos)：最后，如果两个 flag ok_odd_pos 和 ok_even_pos 都还是 true，那就说明两边的数字内部奇偶性都统一，咱就可以成功，输出 "YES"！否则只要有一个是 false，就输出 "NO" 啦。

---

知识点介绍

这道题虽然简单，但涉及了几个很基础但重要的知识点哦！

• 奇偶性 (Parity) 奇偶性就是指一个整数是奇数还是偶数。在计算机里判断这个超简单的，只要看它除以 2 的余数是不是 0 就行啦。这个操作叫“取模”(Modulo)，在 C++ 里写作 x % 2。

  • 如果 x % 2 == 0，它就是偶数。
  • 如果 x % 2 != 0 (或 == 1)，它就是奇数。 这是处理数字问题时非常有用的一个性质，要记住喵！

• 数组下标 (Array Indexing) 这是一个新手很容易踩进去的小坑！题目描述通常是基于人类习惯的 1-based 计数（第1个，第2个...），但绝大多数编程语言（包括 C++）的数组下标都是 0-based 的（从0开始）。

  • 题目的 奇数 位置 1, 3, 5, ... -> 代码中的下标 0, 2, 4, ...
  • 题目的 偶数 位置 2, 4, 6, ... -> 代码中的下标 1, 3, 5, ... 写代码的时候一定要转换过来，不然猫猫爪子会按错键盘的！

• 逻辑独立性 (Logical Independence) 这道题最核心的思维闪光点，就是发现了奇数位操作和偶数位操作是互不干扰的。这让我们可以把一个看似复杂的问题（要不要操作？操作几次？）分解成两个独立的、简单的小问题来分别解决。这种**“分而治之”**的思想是解决算法题的一个非常重要的思路哦，要记住喵~

好啦，这次的题解就到这里啦~ 希望能帮到大家喵！下次再见！(ฅ'ω'ฅ)