B题题解

题意分析

目标是找出一个长度为 m 的子数组，使得通过最少的修改使其变成“奇偶交替数组”。

由于题目是要得到固定长度的奇偶交替性数组，那么可以知道这样的数组只有两种可能。

奇数开头、奇偶交替 or 偶数开头、奇偶交替

我们可以执行的操作是:给任意一个数加上1，也就是改变奇偶性。

那么，因为我们只关心它的奇偶，这里可以做一个状态压缩。用0表示偶数、1表示奇数

思路

奇偶映射： 先将输入整数数组按奇偶映射为 0/1，即：
```
a[i] = (x & 1);  // 1 表示奇数，0 表示偶数
```
构造两种交替模板数组：
- p1[i] = i & 1：形如 1, 0, 1, 0, ...
- p2[i] = (i + 1) & 1：形如 0, 1, 0, 1, ...
这两个模板分别表示“奇偶奇偶…”和“偶奇偶奇…”两个目标序列。
滑动窗口检查：
- 初始化前 m 个数字与两个模板的不同之处 diff1, diff2。
- 然后从第 2 个子数组（下标从 2 到 n - m + 1）滑动窗口，每次通过：
  - 减去离开的左端点的影响；
  - 加上新进入的右端点的影响；
- 由于模板和窗口在滑动时会发生“偏移”，因此在每次滑动时通过奇偶切换判断应该与哪个模板比对。
不断取最小修改次数：
```
ans = min(ans, min(diff1, diff2));
```
复杂度O(n+m)，可以AC。

完整代码

#include <bits/stdc++.h>
#define vi vector<int>
using namespace std;

const int N = 100010;
int n, m;
int a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a[i] = (x & 1);
    }
    vi p1(m + 1), p2(m + 1);
    for (int i = 1; i <= m; i++) {
        p1[i] = i & 1;
        p2[i] = (i + 1) & 1;
    }
    int diff1 = 0, diff2 = 0;
    for (int i = 1; i <= m; i++) {
        if (a[i] != p1[i]) diff1++;
        if (a[i] != p2[i]) diff2++;
    }
    int ans = min(diff1, diff2);
    int count = 1;

    for (int l = 2; m - 1 + l <= n; l++) {
        int r = l + m - 1;
        if(++count % 2==0){
            if(p1[1]!=a[l-1]) diff1--;
            if(p2[1]!=a[l-1]) diff2--;
            
            if(a[r]!=p2[m]) diff1++;
            if(a[r]!=p1[m]) diff2++;

        }else{
            if(p1[1]!=a[l-1]) diff2--;
            if(p2[1]!=a[l-1]) diff1--;
            
            if(a[r]!=p2[m]) diff2++;
            if(a[r]!=p1[m]) diff1++;
        }
        ans = min(ans, min(diff1, diff2));
    }

    cout << ans;
    return 0;
}

题解 | #小柒的交替数组#

B题题解

题意分析

思路

完整代码