Luogu P4552 [Poetize6] IncDec Sequence 更好的题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了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$文章来源地址https://www.toymoban.com/news/detail-592565.html

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

到了这里，关于Luogu P4552 [Poetize6] IncDec Sequence 更好的题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！