在建设 OJ（在线评测系统）时，字符串或 0/1 序列题目的数据质量直接决定了能否测出选手的代码鲁棒性。我们需要构造全是 0、全是 1、K=0 以及 $K$ 超过总数等极端数据。

以下是为你编写的数据生成器源码。它集成了标准 $O(N)$ 算法（标程）并自动生成 10 组符合 NOI 规范的测试点。

数据生成器 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <chrono>
#include <algorithm>

using namespace std;

// --- 标程逻辑：用于生成 .out 答案文件 ---
int getStandardOutput(int n, int k, const vector<int>& a) {
    int left = 0, zero_cnt = 0, max_len = 0;
    for (int right = 0; right < n; ++right) {
        if (a[right] == 0) zero_cnt++;
        while (zero_cnt > k) {
            if (a[left] == 0) zero_cnt--;
            left++;
        }
        max_len = max(max_len, right - left + 1);
    }
    return max_len;
}

// --- 数据生成主逻辑 ---
void make_data() {
    // 使用高质量随机数引擎
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    for (int t = 1; t <= 10; ++t) {
        int n, k;
        vector<int> a;

        // --- 针对性构造不同类型的测试点 ---
        if (t == 1) { // 边界：极小规模 n=1, k=0
            n = 1; k = 0;
            a = {0};
        }
        else if (t == 2) { // 边界：n=1, k=1
            n = 1; k = 1;
            a = {0};
        }
        else if (t == 3) { // 边界：K = 0 (不能翻转)
            n = 1000; k = 0;
            for(int i=0; i<n; ++i) a.push_back(rng() % 2);
        }
        else if (t == 4) { // 边界：K 很大 (全部变 1)
            n = 1000; k = 1500;
            for(int i=0; i<n; ++i) a.push_back(rng() % 2);
        }
        else if (t == 5) { // 特殊：全是 0
            n = 5000; k = 100;
            a.assign(n, 0);
        }
        else if (t == 6) { // 特殊：全是 1
            n = 5000; k = 100;
            a.assign(n, 1);
        }
        else if (t == 7) { // 稀疏 0 (1 多 0 少)
            n = 100000; k = 50;
            for(int i=0; i<n; ++i) a.push_back(rng() % 100 < 5 ? 0 : 1);
        }
        else if (t == 8) { // 稠密 0 (0 多 1 少)
            n = 100000; k = 500;
            for(int i=0; i<n; ++i) a.push_back(rng() % 100 < 95 ? 0 : 1);
        }
        else if (t == 9) { // 随机最大规模
            n = 100000; k = rng() % 50000;
            for(int i=0; i<n; ++i) a.push_back(rng() % 2);
        }
        else { // 满额压力：0/1 交替
            n = 100000; k = 25000;
            for(int i=0; i<n; ++i) a.push_back(i % 2);
        }

        // --- 写入 .in 文件 ---
        string in_name = to_string(t) + ".in";
        ofstream fin(in_name);
        fin << n << " " << k << "\n";
        for (int i = 0; i < n; ++i) {
            fin << a[i] << (i == n - 1 ? "" : " ");
        }
        fin << "\n";
        fin.close();

        // --- 调用标程生成 .out 答案文件 ---
        string out_name = to_string(t) + ".out";
        ofstream fout(out_name);
        fout << getStandardOutput(n, k, a) << endl;
        fout.close();

        cout << "Generated Case " << t << ": n=" << n << ", k=" << k << endl;
    }
}

int main() {
    make_data();
    cout << "\nAll 10 test cases (1.in~10.out) generated successfully!" << endl;
    return 0;
}

测试点规划说明 (OJ 建设参考)

生成器设计要点总结

1. 非递归与效率： 所有数据的生成逻辑均为 $O(N)$ 线性循环。在 $N=10^5$ 的规模下，生成全部 10 组数据（共计 $10^6$ 个元素）耗时在 0.1 秒 左右，且不涉及任何函数递归调用，绝无爆栈风险。
2. 随机数种子： 使用了 chrono::steady_clock 配合 mt19937，确保在不同的生成时间点运行程序，产生的数据分布各异，有助于防范选手的“哈希打表”作弊。
3. 内存管理： 生成器使用了 std::vector。由于 vector 的数据存储在堆区，且 $10^5$ 的 int 向量仅占用约 0.4 MB 空间，远低于绝大多数机器的栈限制和物理内存限制。
4. 符合 NOI 规范： 输出格式严格遵循：
   • 第一行 n k。
   • 第二行 $n$ 个数，中间用空格分隔，行末无空格。
   • 文件以换行符结尾。 这保证了评测时不会因为 Special Judge 或行末空格处理问题导致误判。

教练提示：在创建 OJ 数据时，建议将前三个测试点设置得尽可能小且手工可算，方便选手在比赛初期进行调试。后三个测试点则必须拉满到题目约定的 $10^5$ 规模，以确保选手的 $O(N)$ 复杂度是货真价实的。加油！

这是“最大连续 1 的个数 III”问题的标准题解。在 NOI 竞赛中，这道题是考察 滑动窗口（Sliding Window） 算法对区间约束处理的范例。

一、 题解标准代码 (C++14)

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

using namespace std;

/**
 * 核心思路：
 * 题目要求通过翻转最多 K 个 0 得到最长的连续 1。
 * 转换思路：寻找一个最长的子数组 [left, right]，使得该子数组内 0 的个数不超过 K。
 */

int main() {
    // 竞赛优化：提高 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    if (!(cin >> n >> k)) return 0;

    // 使用 vector 存储数组，n=10^5 约占用 400KB，内存非常安全
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int left = 0;      // 窗口左指针
    int zero_cnt = 0;  // 当前窗口内 0 的个数
    int ans = 0;       // 记录最大长度

    // 右指针遍历整个数组
    for (int right = 0; right < n; ++right) {
        // 关键点 1：进窗。如果当前是 0，计数器增加
        if (a[right] == 0) {
            zero_cnt++;
        }

        // 关键点 2：缩窗。如果 0 的个数超过了允许的 K
        // 易错点：这里必须使用 while 而不是 if，直到窗口重新合法
        // 注意：即使 K=0，该逻辑依然适用（即寻找最长纯 1 序列）
        while (zero_cnt > k) {
            if (a[left] == 0) {
                zero_cnt--;
            }
            left++; // 移动左指针，缩小窗口
        }

        // 关键点 3：更新答案
        // 此时窗口 [left, right] 内部的 0 个数必然 <= K
        ans = max(ans, right - left + 1);
    }

    // 输出最终结果
    cout << ans << endl;

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度分析

• 扫描过程：右指针 right 从 $0$ 遍历到 $n-1$，共移动 $n$ 次。
• 指针单调性：左指针 left 同样只会在 while 循环中向右移动，绝不回退。
• 计算开销：每个元素最多被 right 访问一次（进窗），被 left 访问一次（出窗）。
• 结论：总时间复杂度为 $O(N)$。
  • 在 $N = 10^5$ 的规模下，大约执行 $2 \times 10^5$ 次基本操作。在 NOI 1秒限时内（约可执行 $10^8$ 次操作）非常轻松。

2. 空间复杂度分析

• 存储空间：使用了一个 vector<int> 存储输入数据，空间为 $O(N)$。
• 辅助空间：只使用了 left, zero_cnt, ans 等常数个变量，空间为 $O(1)$。
• 结论：总空间复杂度为 $O(N)$。对于 $10^5$ 的 int 数组，占用约 0.38MB，远小于竞赛常规 128MB 或 256MB 的限制。

三、 时间复杂度优化建议

滑动窗口 $O(N)$ 已经是本题在理论上的最优时间复杂度，但在实际竞赛中，有一种**“不收缩窗口”**的奇技淫巧可以进一步减小常数开销：

• 优化思路： 我们并不真正需要“缩小”窗口来寻找结果，只需要维护一个**“历史上最大的合法窗口”**。 当 zero_cnt > k 时，我们让 left 和 right 同步向右移动一步。这样窗口的大小始终保持不变（即保持为目前为止发现的最大长度）。
• 代码微调：

  for (int right = 0; right < n; ++right) {
      if (a[right] == 0) zero_cnt++;
      if (zero_cnt > k) { // 仅仅移动一次 left，不使用 while
          if (a[left] == 0) zero_cnt--;
          left++;
      }
  }
  return n - left; // 整个数组长度减去左指针位置，即为历史最大窗口宽
  

  这种写法将 while 降级为 if，减少了判断次数，代码极其简洁。

四、 总结：避坑指南

1. $K=0$ 的极端情况： 如果 $K=0$，意味着不能翻转任何 0。滑动窗口逻辑必须能正确处理这种情况。上述 while 逻辑在 $K=0$ 时会退化为：只要遇到 0 就疯狂收缩 left 直到越过该 0，这是正确的。
2. 数据范围： $10^5$ 的数据规模下，int 类型存储长度和计数完全足够。不需要使用 long long，除非 $N$ 达到 $2 \times 10^9$。
3. 读题陷阱： 注意是“连续”的长度。如果是“不连续”的，题目就变成了简单的计数。
4. 输入输出优化： NOI 比赛中，处理 $10^5$ 规模及以上的整数读入，务必记得使用 ios::sync_with_stdio(false); 或 scanf，否则 I/O 可能成为性能瓶颈。

教练点评： 滑动窗口的精髓在于 “维护区间的合法性”。只要你能定义清楚“什么时候窗口是不合法的”，并能通过移动 left 恢复合法性，这类题目就迎刃而解了。加油！