AcWing 6138 奶牛体检
题目：选择a的一个区间并反转该区间(可以选择大小为1的区间)，使得a与b恰有0~n个元素相同，有几种不同区间的选择方法
思路：
原本暴力n^2枚举区间，再n统计ab是否相等,总n^3，超时；
优化：枚举中点,从中点向两边扩展,扩展过程中重复利用已经反转过的元素，只需再统计两边是否一样并计算贡献即可
const int N = 7500 + 10,T = 20;
int n;
LL a[N],b[N],cnt[N];//cnt记录0~n头奶牛被检查的不同方案
void solve()
{
cin >> n;
for (int i = 1;i <= n;i ++) cin >> a[i];
for (int i = 1;i <= n;i ++) cin >> b[i];
LL ans = 0;
//统计初始有多少被检查
for (int i = 1;i <= n;i ++)
if (a[i] == b[i])
ans ++;
for (int i = 1;i <= n;i ++)//枚举中点
for (int j = 0;j <= 1;j ++)//枚举奇数长度还是偶数长度
{
LL tmp = ans; //反转前保证初始情况
for (int l = i,r = i + j;l >= 1 && r <= n;l --,r ++)
{
//反转
if (a[l] == b[l]) tmp --;
if (a[r] == b[r]) tmp --;
if (a[l] == b[r]) tmp ++;
if (a[r] == b[l]) tmp ++;
cnt[tmp] ++;
}
}
for (int i = 0;i <= n;i ++) cout << cnt[i] << endl;
}