「BalticOI 2018」火星人的 DNA 题解

问题分析

我们需要在长度为 n 的字符串中，找到一个最短的连续子串，使得：

1. 对于给定的 R 个要求，每个字符 B 在子串中至少出现 Q 次
2. 如果没有这样的子串，输出 "impossible"

算法思路

核心思想：滑动窗口/双指针

我们可以使用滑动窗口算法来高效地解决这个问题：

1. 初始化两个指针：left 和 right，都指向字符串开头
2. 扩展右指针：向右移动 right，扩大窗口，直到窗口满足所有要求
3. 收缩左指针：在满足要求的情况下，尝试向右移动 left，缩小窗口，寻找更短的子串
4. 记录最短长度：每次找到满足要求的窗口时，更新最小长度
5. 继续搜索：移动左指针，然后重复步骤2-4

关键数据结构

int yq[200005];    // 要求：yq[字符] = 需要的最小次数
int nw[200005];    // 当前窗口内每个字符的出现次数
int hg;            // 已经满足要求的字符数量

代码详解

1. 输入处理

cin >> n >> k >> q;
for (int i = 1; i <= n; i++) cin >> a[i];  // 读入字符串

for (int i = 1; i <= q; i++) {
    int op, kl;
    cin >> op >> kl;
    yq[op] = kl;  // 记录每个字符的要求
}

2. 滑动窗口主循环

for (int i = 1, j = 0; i <= n && j <= n; i++) {
    // 扩展右指针，直到满足所有要求
    while (hg < q && j < n) {
        j++;
        
        if (yq[a[j]] == 0) continue;  // 不是要求的字符
        
        nw[a[j]]++;  // 增加当前字符计数
        
        // 如果刚好达到要求数量，增加满足要求的字符计数
        if (nw[a[j]] == yq[a[j]]) hg++;
    }
    
    // 如果满足所有要求，更新答案
    if (hg == q) {
        ans = min(ans, j - i + 1);
    }
    
    // 收缩左指针
    nw[a[i]]--;  // 移除左边字符
    
    // 如果移除后不再满足要求，减少满足要求的字符计数
    if (yq[a[i]] != 0 && nw[a[i]] == yq[a[i]] - 1) {
        hg--;
    }
}

3. 输出结果

if (ans <= 0 || ans == 1000000000) {
    cout << "impossible\n";
} else {
    cout << ans << "\n";
}

算法复杂度分析

• 时间复杂度：O(n)

  • 每个字符最多被右指针访问一次，被左指针访问一次
  • 总操作次数为 O(2n) = O(n)

• 空间复杂度：O(k + n)

  • a[] 数组：O(n)
  • yq[] 和 nw[] 数组：O(k)
  • 总体：O(n + k)

正确性证明

1. 滑动窗口的正确性

• 单调性：右指针 j 只会向右移动，不会向左移动
• 完整性：当 hg == q 时，窗口一定满足所有要求
• 最小性：每次找到满足要求的窗口后，会尝试收缩左指针，寻找更小的窗口

2. 特殊情况处理

• 字符不在要求中：yq[a[j]] == 0 时直接跳过
• 窗口收缩：当移除一个字符后，如果刚好不满足要求，需要更新 hg
• 边界情况：处理空窗口、单个字符等情况

示例分析

示例1：

输入：
5 2 2
0 1 1 0 1
0 1  // 字符0至少出现1次
1 1  // 字符1至少出现1次

处理过程：
初始：i=1, j=0, hg=0
1. 扩展窗口：j=1, a[1]=0, nw[0]=1, 满足字符0要求，hg=1
   j=2, a[2]=1, nw[1]=1, 满足字符1要求，hg=2
   窗口[1,2]满足要求，长度=2
2. 收缩窗口：i=2, 移除a[1]=0, nw[0]=0, hg=1
   扩展窗口：j=3, a[3]=1, nw[1]=2, hg=2
   窗口[2,3]满足要求，长度=2
   ...
最终答案：2

示例3：

输入：
5 3 1
1 2 0 1 2
0 2  // 字符0至少出现2次

处理过程：
整个字符串只有1个字符0，无法满足要求
最终输出：impossible

算法优化与改进

1. 初始检查

可以先统计整个字符串中每个字符的出现次数，如果某个要求的字符总出现次数不足 Q，可以直接输出 "impossible"。

2. 更清晰的变量命名

// 建议的变量名
int requirement[MAXK];      // 代替 yq
int windowCount[MAXK];      // 代替 nw
int satisfiedCount = 0;     // 代替 hg
int left = 0, right = 0;    // 代替 i, j

3. 改进的代码结构

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int MAXK = 200005;
const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k, r;
    cin >> n >> k >> r;
    
    vector<int> dna(n);
    for (int i = 0; i < n; i++) {
        cin >> dna[i];
    }
    
    vector<int> requirement(k, 0);  // 要求次数
    vector<int> totalCount(k, 0);   // 总出现次数
    
    // 统计总次数
    for (int i = 0; i < n; i++) {
        totalCount[dna[i]]++;
    }
    
    // 读取要求
    for (int i = 0; i < r; i++) {
        int b, q;
        cin >> b >> q;
        requirement[b] = q;
        
        // 提前检查：如果总次数不足，直接不可能
        if (totalCount[b] < q) {
            cout << "impossible\n";
            return 0;
        }
    }
    
    vector<int> windowCount(k, 0);
    int satisfied = 0;
    int minLen = INF;
    int left = 0;
    
    for (int right = 0; right < n; right++) {
        int ch = dna[right];
        
        // 如果是要求的字符
        if (requirement[ch] > 0) {
            windowCount[ch]++;
            if (windowCount[ch] == requirement[ch]) {
                satisfied++;
            }
        }
        
        // 尝试收缩窗口
        while (left <= right && satisfied == r) {
            minLen = min(minLen, right - left + 1);
            
            int leftCh = dna[left];
            if (requirement[leftCh] > 0) {
                windowCount[leftCh]--;
                if (windowCount[leftCh] == requirement[leftCh] - 1) {
                    satisfied--;
                }
            }
            left++;
        }
    }
    
    if (minLen == INF) {
        cout << "impossible\n";
    } else {
        cout << minLen << "\n";
    }
    
    return 0;
}

常见错误与调试

1. 边界条件错误

• j 从0开始，所以窗口长度是 j - i + 1
• 需要检查 j <= n 防止越界

2. 逻辑错误

• 当 yq[a[i]] == 0 时，不应该影响 hg
• 收缩窗口时，只有当计数刚好从要求值减少到要求值-1时，才减少 hg

3. 初始化错误

• ans 初始化为一个很大的数（如1e9）
• hg 初始化为0

总结

本题的滑动窗口解法是典型的最优解法：

1. 高效：O(n)时间复杂度
2. 简洁：代码逻辑清晰
3. 通用：可以解决类似的最小覆盖子串问题

关键点在于：

• 使用双指针维护一个满足要求的窗口
• 动态更新窗口内字符的计数
• 记录已经满足要求的字符数量
• 在满足要求时尝试收缩窗口寻找更优解