K-Bag - 题解

标签与难度

标签: 滑动窗口, 数组处理, 前缀性质, 思维, 实现 难度: 1900

题目大意喵~

主人你好呀~ 这道题是关于一种叫做 "k-bag" 的序列的喵。

一个序列如果能由若干个 {1, 2, ..., k} 的排列拼接而成，那它就是一个 k-bag 序列。比如说，k=3 时，(1,2,3), (3,1,2), (2,3,1) 都是 {1,2,3} 的排列，把它们拼起来 (1,2,3,3,1,2,2,3,1) 就是一个 3-bag 序列。

而 part-k-bag 呢，就是 k-bag 序列的一个 连续子序列（也就是其中的一小段）。

我们的任务是，给定一个长度为 n 的序列和一个整数 k，判断这个序列是不是一个 part-k-bag 序列，然后回答 "YES" 或者 "NO"，喵~

举个栗子： 输入 n=9, k=3，序列 A = {1, 2, 3, 2, 1, 3, 3, 2, 1}。 这个序列本身就是一个 3-bag（由 (1,2,3), (2,1,3), (3,2,1) 拼接而成），所以它当然也是一个 part-k-bag 啦。

再举个栗子： 输入 n=4, k=3，序列 A = {2, 3, 3, 1}。 一个可能的 3-bag 序列可以是 ... (1,2,3), (3,1,2), ...。我们可以发现 A 正好是这个 3-bag 序列中的 (2,3) 的后半部分和 (3,1) 的前半部分拼起来的，也就是 ...1,2,3,3,1,2...。所以 A 是一个 part-k-bag。

解题思路分析

这道题看起来有点复杂，但别怕，让我带你一步步解开它的谜团，喵~

首先，一个最基本的条件是，如果一个序列是 part-k-bag，那么它里面的所有数字都必须在 1 到 k 的范围内。如果出现了比 k 大或者比 1 小的数字，那肯定就不是啦，可以直接说 "NO"。

接下来，我们来分析 part-k-bag 的结构。一个 part-k-bag 是从某个无限长的 k-bag 序列中切下来的一段。这个 "切" 的位置很关键。 它可以恰好从一个排列的开头切，也可以从中间切。

这启发我们，一个 part-k-bag 序列 A 的结构，可以看成是： A = (一个排列的后缀) + (若干个完整的排列) + (一个排列的前缀)

比如说，A 的长度是 n，k 是 3。 A 可能是 (3, 1, 2, 3, 2)。 它可以看成是 (3) (某个排列的后缀) + (1,2,3) (一个完整排列) + (2) (某个排列的前缀)。

这里的关键性质是什么呢？喵~ 是 不重复！ 在一个 {1, ..., k} 的排列中，所有数字都是独一无二的。所以：

1. 上面提到的 (一个排列的后缀)，里面的元素必须互不相同。
2. (一个排列的前缀)，里面的元素也必须互不相同。
3. (一个完整的排列)，里面的元素不仅要互不相同，而且必须恰好是 {1, ..., k} 这 k 个数。

我们可以枚举这个 "切割点" 的位置。换句话说，我们可以枚举我们给定的序列 A 的第一个元素 A[0] 在它所属的那个 k 元排列中是第几个。 假设 A 的开头部分是一个长度为 p_len 的前缀块 (0 <= p_len < k)，那么整个序列 A 就可以被划分为： A[0 ... p_len-1], A[p_len ... p_len+k-1], A[p_len+k ... p_len+2k-1], ...

对于这样的一个划分，要成为一个合法的 part-k-bag，需要满足：

1. 第一个块 A[0 ... p_len-1] (前缀) 里的元素必须互不相同。
2. 中间的每个完整块 A[j ... j+k-1] (主体) 里的元素必须是 {1, ..., k} 的一个排列。
3. 最后一个块 (后缀) 里的元素必须互不相同。

我们可以尝试所有可能的 p_len (从 0 到 k-1)，只要有一种划分满足条件，答案就是 "YES"。但如果对每个 p_len 都去检查一遍，总复杂度会是 O(n*k)，太慢了，会超时的说！

我们需要一个更快的办法来检查“元素互不相同”这个性质。 这时候，一个强大的工具就派上用场啦：滑动窗口！

我们可以预处理一个辅助数组，叫 distinct_len 吧。distinct_len[i] 表示从下标 i 开始，最长的连续不重复子序列的长度是多少。 例如，A = {1, 2, 3, 2, 1}, k=3distinct_len[0] = 3 (因为 {1, 2, 3} 不重复) distinct_len[1] = 2 (因为 {2, 3} 不重复) distinct_len[2] = 2 (因为 {3, 2} 不重复) distinct_len[3] = 2 (因为 {2, 1} 不重复) distinct_len[4] = 1 (因为 {1} 不重复)

这个 distinct_len 数组可以用滑动窗口（双指针）在 $O(N)$ 的时间内计算出来。我们维护一个窗口，不断向右扩大右指针 r，如果遇到重复数字，就收缩左指针 l，直到窗口内没有重复为止。在每次移动 l 之前，我们就确定了 distinct_len[l] 的值。

有了 distinct_len 数组，检查就快多啦！ 对于一个从 j 开始，长度为 m 的块，它内部元素互不相同的充要条件是 distinct_len[j] >= m。

现在，我们再来审视一下我们的划分条件：

1. 前缀块 A[0 ... p_len-1]：需要 distinct_len[0] >= p_len。这意味着我们只需要尝试 p_len 从 0 到 min(k-1, distinct_len[0]-1) 就够了。
2. 主体块 A[j ... j+k-1]：需要它是 {1,...,k} 的排列。
   • 首先，元素必须互不相同，即 distinct_len[j] >= k。
   • 其次，元素必须是 {1,...,k}。但这里有个小技巧！因为我们已经提前检查了所有数都在 [1, k] 范围内，一个长度为 k 的序列，如果元素都在 [1, k] 且互不相同，那它必然是 {1,...,k} 的一个排列！
   • 还有一个更重要的观察：distinct_len[j] 的值最大也只能是 k，因为它能取到的不同数字最多就 k 种。所以，distinct_len[j] >= k 其实等价于 distinct_len[j] == k！
3. 后缀块 A[j_s ... n-1]：需要 distinct_len[j_s] >= n - j_s。根据 distinct_len 的定义，这个条件是永远满足的。所以我们根本不用担心最后一个块！

好啦，最终的算法出炉了，喵~

1. 预检查：遍历一遍数组，确保所有数都在 [1, k] 之间。如果有任何一个不在，直接输出 "NO"。
2. 预处理：使用滑动窗口（双指针）方法，在 $O(N)$ 时间内计算出 distinct_len 数组。
3. 主循环：遍历所有可能的前缀长度 p_len，从 0 到 min(k-1, distinct_len[0]-1)。
4. 检查链条：对于每个 p_len，我们检查从 j = p_len 开始，然后是 j = p_len+k, j = p_len+2k, ... 的所有主体块。
   • 对于每个块的起始位置 j，只要它不是最后一个块，我们就检查 distinct_len[j] >= k (也就是 distinct_len[j] == k) 是否成立。
   • 如果所有主体块都通过了检查，那就说明我们找到了一个合法的划分！马上输出 "YES" 并结束程序。
   • 为了优化，我们可以从 j = p_len 开始，用一个 while 循环跳过所有连续满足 distinct_len[j] == k 的块。
5. 最终结果：如果主循环结束后，还没有找到任何一个合法的 p_len，那就说明不存在这样的划分，输出 "NO"。

这个算法的总时间复杂度是 $O(N)$（预处理）+ $O(k \times \frac{N}{k})$（检查）= $O(N)$，空间复杂度是 $O(N)$（存distinct_len数组），非常高效，可以通过本题！

代码实现

这是我根据上面的思路，精心为你准备的代码哦~ 喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <unordered_set>

// 使用一个函数来封装每次测试的逻辑，让代码更清晰喵~
void solve() {
    int n;
    long long k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    bool basic_check_ok = true;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] < 1 || a[i] > k) {
            basic_check_ok = false;
        }
    }

    // 如果有数字不在 [1, k] 范围内，或者 n=0 这种特殊情况，直接判否
    if (!basic_check_ok) {
        // 即使检查失败，也要读完剩下的输入，防止影响下一组测试用例
        // (虽然本题的实现方式不会，但这是个好习惯)
        std::cout << "NO\n";
        return;
    }
    if (n == 0) {
        std::cout << "YES\n"; // 空序列是任何序列的子序列
        return;
    }

    // 步骤2: 计算 distinct_len 数组
    // distinct_len[i] 表示从 a[i] 开始的最长不重复子序列的长度
    std::vector<int> distinct_len(n);
    std::unordered_set<int> window;
    int right = 0;
    for (int left = 0; left < n; ++left) {
        // 扩大窗口直到遇到重复或到达末尾
        while (right < n && window.find(a[right]) == window.end()) {
            window.insert(a[right]);
            right++;
        }
        // a[left...right-1] 是从 left 开始的最长不重复子序列
        distinct_len[left] = right - left;
        // 左指针向右移动，将 a[left] 移出窗口
        window.erase(a[left]);
    }

    // 步骤3: 检查所有可能的前缀长度
    // 前缀长度 p_len 可以从 0 到 min(k-1, n-1)
    // 并且必须满足 distinct_len[0] >= p_len
    int max_prefix_len = std::min((long long)n - 1, k - 1);
    if (distinct_len[0] - 1 < max_prefix_len) {
        max_prefix_len = distinct_len[0] - 1;
    }

    for (int p_len = 0; p_len <= max_prefix_len; ++p_len) {
        bool current_path_valid = true;
        int current_pos = p_len;
        
        // 我们只需要检查到倒数第二个块，因为最后一个块总是合法的
        while (current_pos + k < n) {
            // 对于一个完整的块，不重复长度必须大于等于k
            // 由于数字范围是[1,k]，所以其实是等于k
            if (distinct_len[current_pos] < k) {
                current_path_valid = false;
                break;
            }
            current_pos += k;
        }

        if (current_path_valid) {
            std::cout << "YES\n";
            return;
        }
    }

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

复杂度分析

• 时间复杂度: $O(N)$

  • 读取输入和基础检查是 $O(N)$。
  • 使用滑动窗口计算 distinct_len 数组，左右指针都最多移动 N 次，所以是 $O(N)$。
  • 最后的检查循环，外层循环最多 k 次（从 p_len = 0 到 k-1）。内层 while 循环的步长是 k。对于每一个 p_len，内层循环最多执行 $\frac{N}{k}$ 次。总的检查次数近似于 $\sum_{p_len=0}^{k-1} \frac{N-p_len}{k} \approx k \times \frac{N}{k} = N$。所以检查部分的总复杂度也是 $O(N)$。
  • 综上，总时间复杂度是 $O(N)$。

• 空间复杂度: $O(N)$

  • 我们需要一个大小为 N 的数组 a 来存储输入序列。
  • 我们还需要一个大小为 N 的 distinct_len 数组来存储预处理结果。
  • 滑动窗口使用的 unordered_set 最多存储 k 个元素。
  • 所以，总空间复杂度是 $O(N)$。

知识点总结

这道题真有趣，不是吗？它把几个核心思想巧妙地结合在了一起，喵~

1. 问题分解: 解决复杂问题的关键一步是把它分解成更小的、更容易处理的部分。我们将 "part-k-bag" 的结构分解为 "前缀 + 主体 + 后缀" 的模式，这让问题清晰了很多。
2. 滑动窗口/双指针: 这是处理数组/字符串中与“连续子串/子数组”性质相关问题的超级利器！在这里，我们用它在 $O(N)$ 时间内高效地计算出了每个位置开始的最长不重复子序列长度。
3. 性质的等价转换: 题目中 "是 {1...k} 的排列" 这个条件，在 "所有数都在 [1,k] 范围" 和 "长度为 k" 的前提下，被我们成功转换为了 "元素互不相同"。而 "元素互不相同" 又被 distinct_len[j] >= k 所刻画。最后，通过观察 distinct_len[j] 的值域，我们又得到了 distinct_len[j] == k 的最终简化条件。这一系列的转换是解题的精髓所在！
4. 预处理思想: 先花一些时间计算一个辅助数据结构（比如这里的 distinct_len 数组），然后在后续的查询/检查中重复利用它，从而大大降低总体时间复杂度。

希望这篇题解能帮到你，主人！如果还有其他问题，随时可以再来找我玩哦，喵~