Cow Checkups

题意

给定两个长度为 $N$ 的数组 a 和 b。

必须恰好选择一个区间 [l,r]，把 a[l..r] 反转一次。反转后，如果某个位置满足 a[i] == b[i]，这头奶牛就能被体检。

对每个 $c=0,1,\ldots,N$ ，求有多少个反转操作 (l,r) 会让恰好 $c$ 头奶牛被体检。

思路

先看一个直接模拟的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:26
 * update_at: 2026-07-11 15:29
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
int a[MAXN], b[MAXN];
long long ans[MAXN]; // ans[c] 表示恰好 c 头奶牛能体检的反转方案数。

int count_match_after_reverse(int l, int r) {
    int cnt = 0;

    for (int i = 1; i <= n; i++) {
        int value = a[i];
        if (l <= i && i <= r) {
            value = a[l + r - i];
        }

        if (value == b[i]) cnt++;
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    // 小数据暴力：直接枚举所有反转区间，再完整计算体检数量。
    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            int cnt = count_match_after_reverse(l, r);
            ans[cnt]++;
        }
    }

    for (int c = 0; c <= n; c++) {
        cout << ans[c] << '\n';
    }

    return 0;
}

这个暴力枚举每个区间 [l,r]，再完整计算反转后的匹配数量。它很直观，但复杂度是 $O(N^3)$ 。

先计算不反转时的匹配数量，记为 base_match。

反转一个区间时，区间外的位置不变。区间内的反转，可以看成左右端点不断交换：

text

1
2
3l 与 r 交换
l+1 与 r-1 交换
...

所以我们按中心向外扩展区间。

当区间从 [l+1,r-1] 扩展成 [l,r] 时，只有端点 l 和 r 的贡献发生变化：

text

1
2原贡献： (a[l] == b[l]) + (a[r] == b[r])
新贡献： (a[l] == b[r]) + (a[r] == b[l])

把原贡献减掉，把新贡献加上，就能 $O(1)$ 得到当前区间反转后的匹配数。

所有区间分为两类中心：

奇数长度：从 (mid, mid) 向外扩展。
偶数长度：从 (mid, mid+1) 向外扩展。

每个反转区间都有唯一中心，因此会被恰好统计一次。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:26
 * update_at: 2026-07-11 15:29
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 7505;

int n;
int a[MAXN], b[MAXN];
long long ans[MAXN]; // ans[c] 表示恰好 c 头奶牛能体检的反转方案数。
int base_match;

void expand_center(int l, int r) {
    int match = base_match;

    while (l >= 1 && r <= n) {
        // 反转区间继续向外扩一层，相当于交换 a[l] 和 a[r]。
        match -= (a[l] == b[l]);
        match -= (a[r] == b[r]);
        match += (a[l] == b[r]);
        match += (a[r] == b[l]);

        ans[match]++;

        l--;
        r++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) base_match++;
    }

    for (int mid = 1; mid <= n; mid++) {
        expand_center(mid, mid);       // 奇数长度区间。
        expand_center(mid, mid + 1);   // 偶数长度区间。
    }

    for (int c = 0; c <= n; c++) {
        cout << ans[c] << '\n';
    }

    return 0;
}

复杂度

所有反转区间共有 $O(N^2)$ 个，每个区间只做 $O(1)$ 更新。

时间复杂度为 $O(N^2)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是不要每次重新反转并完整统计，而是把反转看成从中心向外的一系列交换。

扩展一层只影响两个端点，匹配数可以常数时间更新。

目录

题意

思路

代码

复杂度

总结