AcWing 6135. 奶牛体检

将l ~ r之间的数翻转，求l ~ r 的所有可能，统计l ~ r 之间满足条件的数的数量，

每次从i为中心往两边拓展两个数，统计这两个数的影响，可以省去一重循环（统计符合要求的数量）

0 ~ 1表示的是奇数和偶数，比如说0 2 4 6 8 和1 3 5 7 9 这样每次加二也可以枚举所有的区间数

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 7510;int n, a[N], b[N];
int ans[N];int main()
{cin >> n;for(int i = 0;i < n;i ++ ) cin >> a[i];for(int i = 0;i < n;i ++ ) cin >> b[i];int cnt = 0;for(int i = 0;i < n;i ++ )if(a[i] == b[i])cnt ++ ;for(int i = 0;i < n;i ++ )for(int j = 0;j < 2;j ++ )//奇偶两种可能{int sum = cnt;for(int l = i, r = i + j;l >= 0 && r < n;l --, r ++ ){if(a[l] == b[l]) sum --;//没有被翻转if(a[r] == b[r]) sum --;if(a[l] == b[r]) sum ++;//翻转之后if(a[r] == b[l]) sum ++;ans[sum] ++;}}for(int i = 0;i <= n;i ++ )printf("%d\n", ans[i]);return 0;
}