题解：P11669 [USACO25JAN] Cow Checkups B

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