第三部分：题目分析与标准代码

1. 算法分析

• 暴力法瓶颈：枚举所有区间起点和终点是 $O(N^2)$，再检查区间内容是 $O(N)$，总复杂度 $O(N^3)$。即使优化检查，对于 $N=10^6$ 的数据也无法在 1 秒内完成。
• 最优解法：滑动窗口 (Sliding Window)：
  • 维护一个窗口 [left, right]。
  • 右移扩张：不断增加 right，直到窗口内包含了所有 $M$ 个目标字符。
  • 左移收缩：一旦满足条件，尝试增加 left 来缩短窗口长度，直到窗口不再满足条件为止。在此过程中更新最小长度。
  • 每个元素最多进窗一次、出窗一次，时间复杂度 $O(N)$，完美解决问题。

2. 标准代码 (C++14)

/**
 * 题目：毕昇的字架
 * 难度：GESP 6级
 * 算法：双指针 / 滑动窗口
 * 时间复杂度：O(N)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAX_ID = 2005; // 汉字编号最大 2000
int cnt[MAX_ID];         // 当前窗口内各字符的数量
bool is_target[MAX_ID];  // 标记是否是目标字符

int main() {
    fast_io();

    int N, M;
    if (!(cin >> N >> M)) return 0;

    // 读入字架序列
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // 读入目标字符集
    for (int i = 0; i < M; ++i) {
        int t;
        cin >> t;
        is_target[t] = true;
    }

    int left = 0;
    int valid_type_count = 0; // 当前窗口内已集齐的目标字符种类数
    int min_len = N + 1;      // 初始化为一个不可能的大值

    // 右指针 right 遍历整个序列
    for (int right = 0; right < N; ++right) {
        int char_in = A[right];

        // 进窗逻辑：如果是目标字符
        if (is_target[char_in]) {
            if (cnt[char_in] == 0) {
                valid_type_count++; // 这是一个新收集到的种类
            }
            cnt[char_in]++;
        }

        // 满足条件时，尝试收缩左边界
        while (valid_type_count == M) {
            // 1. 更新答案
            int current_len = right - left + 1;
            if (current_len < min_len) {
                min_len = current_len;
            }

            // 2. 尝试移出左边的字符
            int char_out = A[left];
            if (is_target[char_out]) {
                cnt[char_out]--;
                if (cnt[char_out] == 0) {
                    valid_type_count--; // 这种字符数量归零，窗口不再合法
                }
            }
            left++; // 左边界右移
        }
    }

    if (min_len > N) {
        cout << "Impossible" << endl;
    } else {
        cout << min_len << endl;
    }

    return 0;
}

第四部分：数据生成器

这是一个功能完备的数据生成器，生成的 10 个测试点覆盖了样例、无解、全覆盖、稀疏、密集以及大规模随机等各种情况。

/**
 * GESP 6级 [毕昇的字架] - 数据生成器
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <set>
#include <string>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
string solve(int N, int M, const vector<int>& A, const set<int>& targets) {
    vector<int> cnt(2005, 0);
    int left = 0;
    int valid_count = 0;
    int min_len = N + 1;

    for (int right = 0; right < N; ++right) {
        int c = A[right];
        if (targets.count(c)) {
            if (cnt[c] == 0) valid_count++;
            cnt[c]++;
        }

        while (valid_count == targets.size()) {
            min_len = min(min_len, right - left + 1);
            int out = A[left];
            if (targets.count(out)) {
                cnt[out]--;
                if (cnt[out] == 0) valid_count--;
            }
            left++;
        }
    }

    if (min_len > N) return "Impossible";
    return to_string(min_len);
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<int> A;
        set<int> T_set;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 10; M = 3;
            A = {1,2,3,5,4,2,1,5,3,6};
            T_set = {1,3,5};
        }
        else if (i == 2) {
            // 样例2 (无解)
            N = 5; M = 3;
            A = {1,2,1,2,1};
            T_set = {1,2,3};
        }
        else if (i == 3) {
            // 满数据全覆盖 (序列就是 1..N，Target也是 1..N) -> 答案 N
            N = 100; M = 100;
            for(int k=1; k<=N; k++) { A.push_back(k); T_set.insert(k); }
        }
        else if (i == 4) {
            // Target 只有 1 个 -> 答案 1
            N = 1000; M = 1;
            for(int k=0; k<N; k++) A.push_back(randRange(1, 10));
            T_set.insert(A[N/2]); // 确保有解
        }
        else if (i == 5) {
            // 密集出现
            N = 1000; M = 5;
            for(int k=0; k<N; k++) A.push_back(randRange(1, 10));
            for(int k=1; k<=M; k++) T_set.insert(k);
        }
        else if (i == 6) {
            // 稀疏出现 (Target分布很开) -> 答案很大
            N = 1000; M = 3;
            A.assign(N, 0); // 0是无效干扰字
            A[10] = 1; A[500] = 2; A[990] = 3;
            T_set = {1, 2, 3};
        }
        else {
            // 大规模随机 (N=10^6)
            N = 1000000; 
            // 调整M大小
            if(i==7) M = 10;
            else if(i==8) M = 100;
            else M = 500; // Case 9, 10

            // 生成 Target
            while(T_set.size() < M) T_set.insert(randRange(1, 1000));
            
            // 生成 A，增加解的可能性
            for(int k=0; k<N; k++) A.push_back(randRange(1, 1200)); 
        }

        // 写入输入
        fin << N << " " << T_set.size() << endl;
        for(int k=0; k<N; k++) fin << A[k] << (k==N-1?"":" ");
        fin << endl;
        bool first = true;
        for(int t : T_set) {
            if(!first) fin << " ";
            fin << t;
            first = false;
        }
        fin << endl;

        // 写入输出
        fout << solve(N, T_set.size(), A, T_set) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}