题解：B4181 [厦门小学生 C++ 2024] 有趣子序列

· · 题解

问题描述

我们有一个长度为 n 的 01 字符串 S（下标从 1 开始）。

现在有 Q 次询问，每次询问给出一个子区间 [l,r]。我们需要判断是否存在一个"有趣子序列"，满足：

如果存在这样的"有趣子序列"，输出 Yes，否则输出 No。

具体思路

最简单的方法肯定就是枚举，但这样时间会超时。

我们来想象一下，因为要找到的字符串与原字符序列相同，所以，设原字符长度为 n，我们可以使用在原字符串中的 n-1 个连续的字符，再在剩余的字符串 S 中，找到与另一个字符相同的字符，就可以构成与原字符序列相同的不为子区间的子序列。

综上所述："有趣子序列"存在的充要条件是：S_{l} 在 [1, l-1] 中出现，或 S_{r} 在 [r+1, n] 中出现。（如图）

但是，要注意一下。

如果区间长度为 1，那么它不管怎么取，都是一个子区间，应直接输出 No。

代码

#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;

int t; 
int l, r; 
int n, q; 
char c[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> t; 
    while (t--) { 
        cin >> n >> q; 
        memset(c, 0, sizeof(c)); 
        for (int i = 1; i <= n; ++i) cin >> c[i];

        // f_zero: 第一个 '0' 出现的位置
        // f_one: 第一个 '1' 出现的位置
        // l_zero: 最后一个 '0' 出现的位置
        // l_one: 最后一个 '1' 出现的位置
        int f_zero = 0, f_one = 0;
        int l_zero = 0, l_one = 0;

        for (int i = 1; i <= n; ++i) {
            if (c[i] == '0' && (!f_zero)) f_zero = i; // 记录第一个 '0' 的位置
            if (c[i] == '1' && (!f_one)) f_one = i; // 记录第一个 '1' 的位置

            if (c[i] == '0') l_zero = max(l_zero, i); // 更新最后一个 '0' 的位置
            if (c[i] == '1') l_one = max(l_one, i); // 更新最后一个 '1' 的位置
        }

        while (q--) {
            cin >> l >> r; // 读取查询区间 [l, r]
            if (l == r) { // 如果区间长度为 1，那么它不管怎么取，都是一个连续的子区间，直接输出 "No"
                cout << "No\n";
                continue;
            }

            char a = c[l], b = c[r]; // a 是区间左端字符，b 是区间右端字符

            // 判断是否存在 "有趣子序列"：
            // 1. 如果左端字符 '0' 在 [1, l-1] 中出现（即 f_zero < l）
            // 2. 如果左端字符 '1' 在 [1, l-1] 中出现（即 f_one < l）
            // 3. 如果右端字符 '0' 在 [r+1, n] 中出现（即 l_zero > r）
            // 4. 如果右端字符 '1' 在 [r+1, n] 中出现（即 l_one > r）
            // 满足任意一条即可输出 "Yes"，否则输出 "No"
            if ((a == '0' && f_zero < l) || (a == '1' && f_one < l) || (b == '0' && l_zero > r) || (b == '1' && l_one > r)) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    return 0;
}

总结

一道思维题。