Moe's CF Life

喵哈喽，各位主人！猫猫我今天又来分享一道有趣的算法题解啦，喵~ 这次是来自 Codeforces 的 2069A - Was there an Array?。

这道题就像是在一堆毛线球里找线头，看起来有点乱，但只要找到了那个关键的小疙瘩，问题就迎刃而解啦！让我们一起摇摇尾巴，开始解题吧，喵~

题目大意

题目会给我们一个叫做「相等特征」（equality characteristic）的数组 b，这个数组 b 是从另一个我们不知道的神秘数组 a 生成的。

生成规则是这样哒：

对于数组 a 中除了第一个和最后一个元素之外的每个元素 a[i]，我们都要看看它和它的左邻右舍 a[i-1]、a[i+1] 是不是都长得一模一样。

如果 a[i-1] == a[i] == a[i+1]，那么在 b 数组的对应位置 b[i] 就是 1。
如果不是这种情况（也就是 a[i] 和左边或者右边的邻居至少有一个不一样），那 b[i] 就是 0。

我们的任务是，给你一个数组 b，然后反过来判断一下，到底存不存在一个原始的数组 a，能够生成出这个 b 呢？如果存在，就开心地输出 "YES"，如果不存在，就只能遗憾地说 "NO" 啦，喵~

举个栗子：如果 a = [1, 2, 2, 2, 3, 3, 4, 4, 4, 4]，那么生成的 b 就是 [0, 1, 0, 0, 0, 0, 1, 1]。

题解方法

一开始看到这个问题，猫猫我也有点挠头呢。直接去构造一个数组 a 好像很复杂，因为可能性太多了。但是，我们可以换个思路呀！不去想怎么构造一个 "YES" 的情况，而是去找找什么情况下 "NO" 是必然的。这种方法就叫做“证伪”或者“寻找矛盾”哦！

让我们来仔细分析一下 b 数组里的 0 和 1 到底代表了什么：

b[i] = 1 告诉我们一个非常强的条件：a[i-1] = a[i] = a[i+1]。这三个数必须一模一样，像三只乖乖排队的小猫咪！
b[i] = 0 告诉我们一个比较弱的条件：a[i-1] != a[i] 或者 a[i] != a[i+1]。只要有一个不等就行。

现在，让我们看看 b 数组中连续的几个值会产生什么影响。如果有一段 ...1, 1...，这意味着 a[i-1]=a[i]=a[i+1] 并且 a[i]=a[i+1]=a[i+2]，合起来就是 a[i-1]=a[i]=a[i+1]=a[i+2]，完全没有问题，就是一长串相同的数字嘛。

那什么情况会有问题呢？让我们来试试 b 数组里出现了 1, 0, 1 这样的组合。假设在某个位置，我们有 b[k] = 1, b[k+1] = 0, b[k+2] = 1。

从 b[k] = 1，我们能得到什么信息？喵~？对啦，是 a[k-1] = a[k] = a[k+1]。特别是，我们知道了 a[k] = a[k+1]。
从 b[k+2] = 1，我们又能得到什么？是 a[k+1] = a[k+2] = a[k+3]。特别是，我们知道了 a[k+1] = a[k+2]。
现在看中间的 b[k+1] = 0。它的条件是 a[k] != a[k+1] 或者 a[k+1] != a[k+2]。

现在矛盾来了，主人们请看！

根据第 1 点，我们推断出 a[k] = a[k+1]。
所以，为了让 b[k+1] = 0 成立，就必须满足另一个条件，也就是 a[k+1] != a[k+2]。
但是！根据第 2 点，我们又推断出 a[k+1] = a[k+2]。

看到没有！我们同时要求 a[k+1] 不等于 a[k+2]，又要求它等于 a[k+2]。这就像一只猫猫不能同时在睡觉和在玩毛线球一样，是绝对不可能的！喵！

所以，我们找到了那个导致 "NO" 的罪魁祸首：只要 b 数组中存在连续的 1, 0, 1 子序列，就不可能构造出对应的数组 a。反过来说，只要 b 数组里没有 1, 0, 1 这个模式，我们总能构造出一个合法的 a，所以答案就是 "YES"。

我们的解题策略就变得超级简单啦：遍历一遍 b 数组，看看有没有 1, 0, 1 这个小坏蛋就行了！

题解 (C++)

把上面的思路变成代码，就非常清晰啦，主人们请看，喵~

cpp

#include <iostream>
#include <vector>
#include <string>

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

    bool possible = true;
    // b 数组的大小是 n-2，下标从 0 到 n-3
    // 我们要检查 b[i], b[i+1], b[i+2] 这个组合
    // 为了不让 i+2 超出数组范围，i+2 必须小于 n-2
    // 也就是 i < n-4，所以循环到 n-5 就可以啦
    for (int i = 0; i < n - 4; ++i) {
        if (b[i] == 1 && b[i+1] == 0 && b[i+2] == 1) {
            possible = false; // 找到了坏蛋模式！
            break;          // 赶紧跑，不用再找了
        }
    }

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

int main() {
    // 加速输入输出，让程序跑得像猫猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

代码的逻辑和我们刚才分析的一模一样！

读入 n 和数组 b。
用一个 possible 标志位，先乐观地假设它是 true。
写一个循环，从 i=0 开始，检查 b[i], b[i+1], b[i+2] 是否组成了 1, 0, 1。
循环的边界要小心哦！因为要访问到 b[i+2]，所以 i+2 的最大值必须是 n-3（b数组的最后一个下标），所以 i 的最大值就是 n-5。写成循环条件就是 i <= n-5 或者 i < n-4。
一旦找到这个模式，就把 possible 设为 false，然后 break 掉循环，因为已经可以确定答案是 "NO" 了。
最后根据 possible 的值输出 "YES" 或者 "NO" 就大功告成啦！

知识点介绍

这道题虽然简单，但里面包含了一些很重要的思想哦，喵~

构造性问题的反向思考（寻找矛盾）: 很多题目问你“是否存在...”，“是否可能...”，直接去构造一个肯定的例子可能很复杂。这时候，不妨换个角度，去寻找什么情况下“一定不存在/不可能”。找到了这个矛盾点，问题就解决了。这在数学证明和算法设计里都是非常有用的技巧！
局部约束与全局矛盾: 题目的条件（b[i] 的定义）都是非常局部的，只和 a 数组中相邻的三个元素有关。但是，几个这样的局部约束组合在一起（比如 b[k]=1, b[k+1]=0, b[k+2]=1），就可能导致一个无法解决的全局性（或者说更大范围的）矛盾。从局部性质推导全局性质，是解决很多问题的关键。
注意数组边界: 这是写代码时一个永恒的话题喵！当循环中访问 arr[i], arr[i+1], arr[i+k] 这样的元素时，一定要确保循环的边界条件能保证 i+k 不会超出数组的范围。不然就会遇到“越界访问”这个大魔王，程序可能就会崩溃哦！小心一点，总没错的！

好啦，今天的题解就到这里啦！是不是很简单很有趣呢？只要找到那个小小的矛盾点，问题就迎刃而解了。希望主人们都学会了这种解决问题的思路哦！如果还有什么问题，随时可以来问猫猫我呀！下次见，喵~ >w<

题目大意 ​

题解方法 ​

题解 (C++) ​

知识点介绍 ​

题目大意

题解方法

题解 (C++)

知识点介绍