自动搬运

查看原文

来自洛谷，原作者为

	yedalong 注意力不够？刷题来凑！

搬运于2025-08-24 23:09:19，当前版本为作者最后更新于2025-02-04 20:31:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

双指针好题。

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';
}

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