Moe's CF Life

喵哈喽~！各位算法爱好者们，今天由我，你们的小助手猫娘，来为大家解析一道非常有趣的入门级贪心算法题，Codeforces 上的 1777A - Everybody Likes Good Arrays! 喵~ 这道题就像整理一团乱糟糟的毛线球，只要找到线头，一下子就能理顺啦！

题目大意

这道题是说，我们有一个数组，如果这个数组里所有相邻的两个数字的奇偶性都不同（比如一奇一偶，或者一偶一奇），那我们称它为一个“好数组”（Good Array）。大小为 1 的数组天然就是“好数组”哦。

我们有一种特殊操作：可以选择数组中任意一对奇偶性相同的相邻元素，把它们删掉，然后在原来的位置插入它们的乘积。

我们的任务就是，对于给定的一个数组，计算出最少需要多少次这样的操作，才能把它变成一个“好数组”，喵~

举个栗子🌰：对于数组 [1, 7, 11, 2, 13]：

7 和 11 都是奇数，相邻且奇偶性相同。我们对它们操作，数组变成 [1, 7*11, 2, 13]，也就是 [1, 77, 2, 13]。
现在 1 和 77 都是奇数，又可以操作啦！数组变成 [77, 2, 13]。
现在数组里相邻元素的奇偶性分别是 (奇, 偶) 和 (偶, 奇)，都不同了。它已经是个“好数组”了！

我们总共用了 2 次操作，这就是最少的次数啦。

解题思路

这道题的关键在于理解操作的本质，喵~ 让我们来分析一下操作对数字奇偶性的影响：

奇数 × 奇数 = 奇数
偶数 × 偶数 = 偶数

发现了吗？两个奇偶性相同的数相乘，得到的乘积的奇偶性，和原来那两个数是一样的！

这意味着，如果有一串连续的、奇偶性都相同的数字（比如 [1, 7, 11] 都是奇数），无论我们怎么在内部进行合并操作，最终都会得到一个和它们奇偶性相同的数字。比如 [1, 7, 11] -> [1, 77] -> [77]，结果 77 还是个奇数。

一个“好数组”不允许有任何相邻的、奇偶性相同的元素。所以，任何一长串奇偶性相同的连续块，都必须被我们用操作合并成一个数字。

比如说，我们有一个块 [a, b, c, d]，它们的奇偶性都相同。为了让它不和旁边的元素产生冲突，我们必须把它变成一个数。 [a, b, c, d] -> [a*b, c, d] (1次操作) -> [a*b*c, d] (2次操作) -> [a*b*c*d] (3次操作)。把一个长度为 k 的同奇偶性块合并成一个数，需要 k-1 次操作。

那么问题就变得非常简单了！我们只需要数一数，原始数组里有多少对相邻的、奇偶性相同的元素。每一对这样的元素，都意味着存在一个需要被合并的“坏邻居”关系。我们每进行一次操作，就能消除一对这样的“坏邻居”。

所以，最少的操作次数，就等于原始数组中相邻且奇偶性相同的元素对的数量！

我们只需要从头到尾遍历一遍数组，检查 a[i] 和 a[i-1] 的奇偶性是否相同，如果相同，计数器就加一。最后得到的总数就是答案啦，是不是超级简单，喵！

题解代码

这是 C++ 的实现代码，加上了猫娘的思路注释哦~

cpp

#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];
    }

    // 我们的目标是让数组变成“好数组”，也就是相邻元素的奇偶性都不同。
    // 操作是合并两个相邻的、奇偶性相同的元素。
    
    // 就像我们分析的，操作不会改变一个同奇偶性块的整体奇偶性。
    // 奇 * 奇 = 奇
    // 偶 * 偶 = 偶
    //
    // 所以，要把一个由 k 个同奇偶性元素组成的连续块变成一个元素，需要 k-1 次操作。
    // 这等价于，我们只需要数一数有多少对相邻的元素 (a[i], a[i+1]) 它们的奇偶性是相同的。
    // 每有一对这样的元素，就意味着我们需要一次操作来“修复”它们的关系。
    
    int operations = 0; // 用来计数的变量，初始化为0
    // 从数组的第二个元素开始遍历 (i=1)，这样方便和前一个元素 a[i-1] 比较
    for (int i = 1; i < n; ++i) {
        // 检查当前元素 a[i] 和前一个元素 a[i-1] 的奇偶性是否相同
        // a[i] % 2 的结果是 0 (偶数) 或 1 (奇数)
        if ((a[i] % 2) == (a[i - 1] % 2)) {
            // 如果奇偶性相同，说明这里需要一次操作来合并它们
            operations++;
        }
    }

    // 最后把需要的操作总数打印出来就大功告成啦！
    std::cout << operations << std::endl;
}

int main() {
    // 这是一个在编程竞赛中常用的技巧，让输入输出更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t; // 测试用例的数量
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

题目大意

解题思路

题解代码

相关知识点介绍

1. 奇偶性 (Parity)

2. 贪心算法 (Greedy Algorithm)

题目大意 ​

解题思路 ​

题解代码 ​

相关知识点介绍 ​

1. 奇偶性 (Parity) ​

2. 贪心算法 (Greedy Algorithm) ​

题目大意

解题思路

题解代码

相关知识点介绍

1. 奇偶性 (Parity)

2. 贪心算法 (Greedy Algorithm)