Luogu P4552 [Poetize6] IncDec Sequence 更好的题解
第一步对于学过差分的人应该不难想
定义差分数组 $dis \quad s.t. \quad dis[i] = a[i] - a[i-1] $
那么不难发现问题一只要让 \(dis[2] ... dis[n]\)中全部为 \(0\) 即可
区间\([l,r]\)加一操作在差分数组中意味着\(dis[l]=dis[l]+1,dis[r+1]=dis[r+1]-1\)
即在差分数组中每次选取\((x,y),dis[x]=dis[x]+1,dis[y]=dis[y]-1\)
注意这里\(x,y\)可以选取\(1...n+1\)
减一同理
最后要使\(dis[2] ... dis[n]\)全为0,首先在\(dis[2] ... dis[n]\)选取一个正数和一个负数是他们配对加一或减一,直到最后只剩下一个数,不难发现这个数就是\(dis[2] ... dis[n]\)中正数的和\(sum^+\)和负数的和的绝对值\(|sum^-|\)的差,让他与dis[1]或dis[n+1]配对即可
最后整理可得:\(min(sum^+,sum^-)+|sum^+-|sum^-||\),即\(max(sum^+,|sum^-|)\)就是第一小问答案
对于第二小问,不难注意答案序列的不同只和在第一小问中最后剩下的那个数\(k = sum^+-|sum^-|+1\)有关
我们这里不妨设\(k > 0\),那么它可以和1或n+1配对,这里两个操作就代表了原数组\(a[1,k-1]\)全部加一和原数组\(a[k,n]\)全部减一,也就产生了两种不同的序列
那么这两种操作进行的次数的和必然是\(k\),那么就产生了k+1中不同的选法(第一个操作进行\(0...k\)次)
对于\(k < 0\)的情况可以同样地进行讨论
那么第二问答案就是\(k+1=|sum^+-|sum^-||+1\)
//c++AC代码
#include <bits/stdc++.h>
using namespace std;
int n,a[(int)1e5+5],dis[(int)1e5+5];
long long sum_z,sum_f,rest;
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i)
{
scanf("%d",a+i);
}
for(int i = 1;i <= n;++i)
{
dis[i]=a[i]-a[i-1];
}
for(int i = 2;i <= n;++i)
{
if(dis[i] > 0)
sum_z+=dis[i];
else
sum_f+=dis[i];
}
rest=sum_z+sum_f;
printf("%lld\n",max(sum_z,std::abs(sum_f)));
printf("%lld",(long long)std::abs(sum_z-std::abs(sum_f))+1);
return 0;
}