首页 > 其他分享 >【P4552】IncDec Sequence

【P4552】IncDec Sequence

时间:2024-09-10 20:38:42浏览次数:1  
标签:Sequence P4552 long 差分 序列 IncDec

因为前缀和/差分学习的时候就不熟,所以特选本题作为训练

作为一道差分题,本题的思路也是特别的绕,首先进行基础知识的复习

【差分】

简单来说就是两个数的差,b[i]=a[i]-a[i-1]

把序列a的区间 [l,r]+d 的话,差分序列b则进行以下变化:

   b[l]+d,b[r+1]-d

前置知识大概就这些,下面进行题目分析:

要让序列中的数全部相等,也就是让其之间的差都为0,我们可以让差分后的正数和和负数和取最小,然后加上剩余的部分,这是第一问

第二问是差分后的正数和和负数和的差,具体证明为选择一个个的加/一个个减

 

警钟长鸣:不开long long 直接爆

标签:Sequence,P4552,long,差分,序列,IncDec
From: https://www.cnblogs.com/Jucex/p/18407118

相关文章

  • CF1621G Weighted Increasing Subsequences 题解
    题目链接点击打开链接题目解法这种题就感觉每一步都不难想,但串在一起就不会显然考虑位置\(x\)作为\(lis\)的一部分,合法的\(lis\)的个数合法的约束是:令\(lis\)的最后一个位置为\(last\),满足\(\max\{a_{last+1},...,a_n\}>a_x\)不难发现,合法的\(last\)是一段区间......
  • 浙大数据结构:02-线性结构4 Pop Sequence
    这道题我们采用数组来模拟堆栈和队列。简单说一下大致思路,我们用栈来存1234.....,队列来存输入的一组数据,栈与队列进行匹配,相同就pop1、条件准备stk是栈,que是队列。tt指向的是栈中下标,front指向队头,rear指向队尾。初始化栈顶为0,队头为0,队尾为-1#include<iostream>usingn......
  • [ABC221G] Jumping sequence
    MyBlogs[ABC221G]Jumpingsequence做法有点深刻,优化方式非常深刻。首先是哈密顿距离和切比雪夫距离的转化:把坐标系旋转四十五度,变成每次向左上,右上,左下,右下走\(\sqrt2a_i\)的距离,要求最后走到\((A+B,A-B)\)。然后这样可以对于横纵坐标分开做了(非常神奇)。问题转化成了询......
  • 浙大数据结构:01-复杂度2 Maximum Subsequence Sum
    数据结构MOOCPTA习题01-复杂度2MaximumSubsequenceSum#include<iostream>usingnamespacestd;constintM=100005;inta[M];intmain(){ intk; cin>>k; intf=1; for(inti=0;i<k;i++) { cin>>a[i]; if(a[i]>=0)//如......
  • CF 2001 D. Longest Max Min Subsequence(*1900) 思维
    CF2001D.LongestMaxMinSubsequence(*1900)思维题目链接题意:给你一个长度为\(n\)的序列\(a\),设\(S\)是\(a\)的所有可能的非空子序列的集合,且没有重复的元素。你的目标是找出\(S\)中最长的序列。如果有多个序列,请找出将奇数位置上的项乘以\(−1\)后,使词序最小......
  • 题解:CF916B Jamie and Binary Sequence (changed after round)
    题意把一个数分解成恰好\(k\)个\(2^{a_i}\)次方的和,可以重复,要求保证最大的\(a_i\)要尽可能的小时,\(a\)的字典序尽可能大,输出序列\(a\)。分析首先我们借助二进制拆出一个满足\(n=\sum2^{a_i}\)序列\(a\),满足\(a\)的长度最小。若此时\(a\)的长度大于\(k\),显......
  • Strings, Subsequences, Reversed Subsequences, Prefixes
    题目大意给定两个字符串s和t,求出在s里面有多少个本质不同的子序列,使得该序列的前缀包含t,且该序列的反串也包含t即s的子序列=t+x+反t‘首先要确定是否有,就是判断我的S字符串中有没有包含T字符串for(l=0;l<n;l++){ if(s[l]==t[num])num++; if(num==m)bre......
  • 题解:AT_abc367_c [ABC367C] Enumerate Sequences
    大致题意让你按照字典序输出一些长\(n\)的序列,序列中的数字有范围,且序列和需要为\(k\)。分析直接深搜。搜索的时候对从第一个元素开始,每个元素从小到大枚举所有可能的值,这样就保证答案按照字典序升序排列。用一个vector存储序列,到达边界之后计算一遍和,判断是否满足条件,然......
  • Atcoder [ABC367C] Enumerate Sequences 题解
    简要题意给定\(n,k\)和\(R_i\),你需要输出所有满足下列条件的整数序列:长度为\(n\)。第\(i\)个元素的范围为\([1,R_i]\)。一个序列的所有元素的总和为\(k\)的倍数。输出请按照按照从左至右按位从小到大的顺序输出。题解注意到数据范围很小,我们可以直接爆搜,这里用......
  • Padding Mask;Sequence Mask;为什么如果没有适当的掩码机制,解码器在生成某个位置的输出
    目录掩码Mask PaddingMask SequenceMask为什么需要SequenceMask?SequenceMask是如何工作的?具体实现为什么如果没有适当的掩码机制,解码器在生成某个位置的输出时,可能会“看到”并错误地利用该位置之后的信息自回归性质一、定义二、性质三、应用限制掩码Mask......