• 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。因此,问题转化为:给定一个差分数