双指针好题。

Solution

初次见到这道题，我的第一想法就是枚举左右端点，用一个数组 $ans$ 记录答案，加上判断后就很成功的超时了，代码如下：

#include <bits/stdc++.h>
using namespace std;
int n,a[7505],b[7505],ans[7505],cnt;
int main(){
    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]) cnt++;
    for(int l = 1;l<=n;l++){
        for(int r = l;r<=n;r++){
            int tmp=cnt;
            for(int i = l;i<=r;i++){
                if(a[i]==b[i]) tmp--;
                if(a[i]==b[r-(i-l)]) tmp++;
            }
            ans[tmp]++;
        }
    }
    for(int i = 0;i<=n;i++) cout<<ans[i]<<'\n';
}

评测结果
接下来我们考虑优化。
我们可以考虑省掉判断的时间，具体怎么省呢？我们可以选定一个中间点，让 $l$ 和 $r$ 在中间点两边向外移动，这样在枚举 $l$ 和 $r$ 的同时也就可以判断，用一个 $tmp$ 变量存当前的被检查奶牛数，就省下判断的时间了！
当左端点为 $l$，右端点为 $r$ 时的判断：

$$tmp=\left\{ \begin{array}{rcl} tmp-1 & & {a_l=b_l\land a_l\neq b_r}\\ tmp-1 & & {a_r=b_r\land a_r\neq b_l}\\ tmp+1 & & {a_l\neq b_l\land a_l=b_r}\\ tmp+1 & & {a_r\neq b_r\land a_r=b_l}\\ \end{array}\right.$$

这一部分算是比较好理解的。
最后就能解决此题。

AC code

#include <bits/stdc++.h>
using namespace std;
int n,a[7505],b[7505],ans[7505],cnt,l,r;
int main(){
    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]) cnt++;
    for(int i = 1;i<=n;i++){
        int tmp=cnt;
        l=i,r=i;
        while(l>=1&&r<=n){
            if(a[l]==b[l]&&a[l]!=b[r]) tmp--;
            if(a[r]==b[r]&&a[r]!=b[l]) tmp--;
            if(a[l]!=b[l]&&a[l]==b[r]) tmp++;
            if(a[r]!=b[r]&&a[r]==b[l]) tmp++;
            ans[tmp]++;
            l--,r++;
        }
        if(i==n) continue;
        l=i,r=i+1;
        tmp=cnt;
        while(l>=1&&r<=n){//这里进行两次的区别是：一次是枚举长度为奇数的区间，一次是枚举长度为偶数的区间
            if(a[l]==b[l]&&a[l]!=b[r]) tmp--;
            if(a[r]==b[r]&&a[r]!=b[l]) tmp--;
            if(a[l]!=b[l]&&a[l]==b[r]) tmp++;
            if(a[r]!=b[r]&&a[r]==b[l]) tmp++;
            ans[tmp]++;
            l--,r++;
        }
    }
    for(int i = 0;i<=n;i++) cout<<ans[i]<<'\n';
}

最后也是跑得飞快，评测记录。

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
 
    vector<int> A(n), B(n);
 
    for (int &i : A)
        cin >> i;
    for (int &i : B)
        cin >> i;
    
    int alreadySame = 0;
    vector<int> ans(n + 1, 0);
 
    for (int i = 0; i < n; i++)
        alreadySame += (A[i] == B[i]);
 
    auto expand = [&](int l, int r){
        int match = alreadySame;
 
        for (; l >= 0 and r < n; l--, r++){
            match += ((A[l] == B[r]) + (A[r] == B[l])) - ((A[l] == B[l]) + (A[r] == B[r]));
            ans[match]++;
        }
    };
    for (int mid = 0; mid < n; mid++){
        expand(mid, mid);
        expand(mid, mid + 1);
    }
    for (int i : ans)
        cout << i << "\n";
}