题解：P11669 [USACO25JAN] Cow Checkups B

· · 题解

双指针好题。

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 时的判断：

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

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