网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P4552
2024-09-10
【P4552】IncDec Sequence
因为前缀和/差分学习的时候就不熟,所以特选本题作为训练作为一道差分题,本题的思路也是特别的绕,首先进行基础知识的复习【差分】简单来说就是两个数的差,b[i]=a[i]-a[i-1]把序列a的区间[l,r]+d的话,差分序列b则进行以下变化: b[l]+d,b[r+1]-d前置知识大概就这些,下面进行题
2024-08-01
洛谷题单指南-前缀和差分与离散化-P4552 [Poetize6] IncDec Sequence
原题链接:https://www.luogu.com.cn/problem/P4552题意解读:对一组数字序列,进行若干次区间+1或者-1操作,最终使得所有数字一样,计算最少的操作次数,以及能得到多少种不同序列。解题思路:要使得序列每一个数字都相同,则其差分除了第一项之外其余项都是0。因此,问题转化为:给定一个差分数