BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 18 题

第三题

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 5000 + 5;
int n, a[MAXN], d[MAXN];
int check(int k) {
    memset(d, 0, sizeof(d));
    int res = 0;
    for (int i = 1, s = 0; i <= n; i++) {
        s += d[i];
        if ((a[i] + s) % 2 == 1)
            continue;
        if (i + k > n + 1)
            return 1e9;
        d[i]++, s++, res++;
        d[i + k]--;
    }
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int ans = 1e9;
    for (int k = 1; k <= n; k++) {
        int tmp = check(k);
        if (tmp < ans)
            ans = tmp;
    }
    printf("%d\n", ans);
    return 0;
}

假设输入的 $n$ 是不超过 $5000$ 的正整数，数组元素 $a[1], a[2], \dots, a[n]$ 均是不超过 $1$ 的非负整数，完成下面的判断题和单选题。

判断题

1. 若将第 009 行的 for 循环执行条件改为 i + k - 1 <= n，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ） 2. 若将第 015 行的代码改为

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是读懂 check 函数里那段看似绕弯的循环：用差分数组 d 维护区间加 1 的效果，通过 s 累加 d 来实时知道当前下标 i 被覆盖了多少次。只要 a[i]+s 是奇数就跳过，否则执行一次区间加（d[i]++、d[i+k]--）并计数。理解这个滑动窗口式的差分技巧，后面五个判断和两个计算题就迎刃而解。

最容易栽跟头的是把 d 数组当成普通前缀和数组，以为每步都要重新算一遍覆盖次数，那样时间复杂度直接爆炸；还有人看到 i+k>n+1 就以为 k 不能太大，其实那是检查区间是否越界的写法，和循环条件 i<=n 配合正好保证不会访问越界。另外判断题里“去掉 d[i]++ 输出不变”这种反直觉结论，很多学生会凭直觉打叉，却忘了 s 本身已经记录了覆盖次数，d 数组只是用来快速更新 s 的辅助工具，去掉它只要 s 更新逻辑对，结果确实不变。还有时间复杂度那题，有人会被外层 k 循环迷惑，以为要算 O(n^2 log n)，其实内层检查是 O(1)，整体就是 O(n^2)。

这道题考什么

本题考查的是对差分数组、前缀和思想以及循环边界控制的综合理解，同时也考查对算法时间复杂度的直观判断。命题人把一段看似复杂的代码放在 check 函数里，然后用五个判断题和一个单选题来拆解其中的逻辑。

核心概念：差分数组与 s 的作用

在代码里，d 是一个差分数组。d[i]++ 表示从位置 i 开始往后所有位置的值都要加 1，而 d[i+k]-- 表示从位置 i+k 开始往后所有位置的值要减 1。这样，当我们用 s 累加 d 时（s += d[i]），s 就实时反映了当前下标 i 被覆盖了多少次（即有多少个以 i 为起点的区间包含了 i）。

为什么需要 s？因为如果每次都要重新算覆盖次数，复杂度会很高。用差分数组配合前缀和，可以在 O(1) 时间内更新覆盖次数。

命题视角：为什么这么考？

命题人喜欢在这种题里挖坑： 1. 循环条件：i + k > n + 1 这个判断看起来有点奇怪，其实是为了确保区间 [i, i+k-1] 不会超出数组范围。如果改成 i + k - 1 <= n，逻辑是一样的，但代码风格变了，容易让人误以为会越界。 2. d 数组的作用：很多人以为 d 是必须的，其实只要 s 更新正确，去掉 d[i]++ 也不会影响结果，因为 s 已经记录了覆盖次数。 3. s 的变化：s++ 是因为每次成功执行一次区间加，覆盖次数就增加 1。如果改成 s--，那覆盖次数就减少了，显然不对。 4. 输出结果：res 记录的是成功执行的次数，可能为 0（比如所有 a[i] 都是奇数，或者 n 很小），也可能等于 n（比如所有 a[i] 都是偶数且 k 足够大）。所以“输出结果必然小于 n”是错的。 5. 时间复杂度：外层循环 k 从 1 到 n，内层循环 i 从 1 到 n，每次 check 是 O(n)，总共 O(n^2)。有人会被 i + k > n + 1 这个条件迷惑，以为要算对数，其实它是 O(1) 判断。

思考心法：拿到题先想什么？

• 先看 check 函数的逻辑：它遍历一遍数组，遇到 a[i] + s 是奇数就跳过，否则执行一次区间加并计数。
• 再看循环条件：i + k > n + 1 是边界检查，确保区间不越界。
• 再看 d 数组和 s 的关系：d 是差分，s 是前缀和，两者配合实现 O(1) 更新覆盖次数。
• 最后看主函数：枚举所有可能的 k，取最小的 res 作为答案。

逐题推演

判断题 1：循环条件改为 i + k - 1 <= n

原条件 i + k > n + 1 等价于 i + k - 1 > n，即区间 [i, i+k-1] 超出右边界。改成 i + k - 1 <= n 后，逻辑完全一样，只是写法不同。程序仍能正常执行，输出结果不变。答案：正确。