题解：P11669 [USACO25JAN] Cow Checkups B

· · 题解

P11669 [USACO25JAN] Cow Checkups B题解

思路：

  1. 快读。
  2. 预处理出符合条件的牛数。
  3. 在一次 BFS 中处理出 [ x , y ] 的正逆序匹配数（ [ x , y ] 扩展至 [ x-1 , y+1 ]），同时叠加 c 数组。

    代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int n,a[7502],b[7502],c[7502],t;
queue<pair<int,int>> qu,qu1;
pair<int,int> pa,pa1;
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++)
        b[i]=read();
    for(int i=1;i<=n;i++) if(a[i]==b[i]) t++;
    for(int i=1;i<=n;i++){ 
        qu.push({i,i});
        qu1.push({a[i]==b[i],a[i]==b[i]});
    }
    for(int i=1;i<n;i++){
        qu1.push({(a[i]==b[i+1])+(b[i]==a[i+1]),(a[i]==b[i])+(b[i+1]==a[i+1])});
        qu.push({i,i+1});
    }
    while(!qu.empty()){
        pa=qu.front();
        qu.pop();
        pa1=qu1.front();
        qu1.pop();
        c[t+pa1.first-pa1.second]++;
        if(pa.first==1 || pa.second==n) continue;
        qu.push({pa.first-1,pa.second+1});
        qu1.push({pa1.first+(a[pa.first-1]==b[pa.second+1])+(b[pa.first-1]==a[pa.second+1]),pa1.second+(a[pa.second+1]==b[pa.second+1])+(a[pa.first-1]==b[pa.first-1])});
    }
    for(int i=0;i<=n;i++)
        printf("%d\n",c[i]);

    return 0;
}

码风不好，还请见谅。