题解 P11669 [USACO25JAN] Cow Checkups B
cjh20090318
·
·
题解
题意
给定两个 N 个数的数列 a,b。
设 d 表示将 a 的 [l,r] 区间翻转后的数列，f(l,r) = \sum\limits_{i=1}^N[d_i = b_i]。
求对于每个 c \in [0,N] \cap \mathbb{N}，有多少对不同的 (l,r)\ (1 \le l \le r \le N) 满足 f(l,r) = c。
分析
对于一个当前已知答案区间 $[l,r]$，可以迅速推广到区间 $[l-1,r+1]$。因为他们的对称轴是相同的，所以新区间内 $[l,r]$ 的关系不会变，计算答案只需要考虑 $l-1$ 和 $r+1$ 对应的关系即可。
时间复杂度 $O(N^2)$。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
using namespace std;
int n;
int a[7505],b[7505];
int ans[7505];
int main(){
scanf("%d",&n);
int org=0,sum=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]),org+=a[i]==b[i];//初始有多少个已经对应相等。
for(int i=1;i<=n;i++){
sum=org;
for(int l=i,r=i+1;l>0&&r<=n;--l,++r)
++ans[sum+=(a[l]==b[r])+(a[r]==b[l])-(a[l]==b[l])-(a[r]==b[r])];//对称轴在 i 和 i+1 之间，加上两端新出现的答案，减去原来的答案。
sum=org;
for(int l=i,r=i;l>0&&r<=n;--l,++r)
++ans[sum+=(a[l]==b[r])+(a[r]==b[l])-(a[l]==b[l])-(a[r]==b[r])];//对称轴为 i，同上。
}
for(int i=0;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
```