【算法基础复习1】差分
创始人
2024-02-21 09:42:05

 目录

一、差分简介

一维差分结论

Acwing.797 差分

P4552 [Poetize6] IncDec Sequence - 差分思维玄学题

一、差分简介

  • 规定a数组下标从1开始  a[0]=0
  • b数组下标从1开始
  • 定义一个数组b，使 \large b\left [ i \right ]=a\left [ i \right ]-a\left [ i-1 \right ]
  • 对于a数组              \large a=\left \{ 4,8,6,5,10,7 \right \}
  • 其差分数组b为       \large b=\left \{ 4,4,-2,-1,5,-3 \right \}
  • a是b的前缀和数组  \large \large a\left [ i \right ]=b[1]+b[2]+...+b[i]=a[i-1]+b[i]
  • 比如  a[2] = b[1]+b[2] = 4+4= 8
  • 比如  a[4] = b[1]+b[2]+b[3]+b[4] = 4+4-2-1 = 5
  •  如果我们要给a数组【l , r】区间都+c   即 a[l]+c , a[l+1]+c …… a[r]+c

  • 首先给 b[l]+c 则    \large a[l]+c , a[l+1]+c, ...,a[r]+c

  • 然后给 b[r+1] - c 则   \large a[r+1]-c , a[r+2]-c,..., a[n]-c

先给b[l]+c 则a数组的红色区域都会+c

再给b[r+1]-c 则a数组的绿色区域都会-c

从而达到只给区间 [l,r]+c 的目的

一维差分结论

给a数组 [l,r] 区间的每个数+c，只需要给其差分数组b做如下操作即可

b[l]+=c;
b[r+1]-=c;

Acwing.797 差分

 活动 - AcWing

import java.util.*;public class Main
{static int N=(int)1e5+10;public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),k=sc.nextInt();int[] a=new int[N];int[] b=new int[N];for(int i=1;i<=n;i++){a[i]=sc.nextInt();b[i]=a[i]-a[i-1]; //构造差分数组}int l,r,c;while(k-->0){l=sc.nextInt();r=sc.nextInt();c=sc.nextInt();b[l]+=c;b[r+1]-=c;}for(int i=1;i<=n;i++){a[i]=a[i-1]+b[i]; //b的前缀和是aSystem.out.print(a[i]+" ");}}
}

P4552 [Poetize6] IncDec Sequence - 差分思维玄学题

[Poetize6] IncDec Sequence - 洛谷

思路：

这题可以转化为求出原数列的差分数组b，最后使得 \large b[2]\sim b[n]=0

题目中对数组a的操作，相当于每次能选出 \large b_{1},b_{2},...,b_{n} 中任意两个数，一个+1，一个-1

  • x= b中所有正数之和
  • y= b中所有负数之和的绝对值
  • 我们需要先正负抵消，这时剩下最后一个数，再单独把这个数消成0
  • 所以操作数就是 max(x,y)

  • 求方案数 也就是求\large b_{i}的可能数
  • 完成以上操作后得到的b差分数组就是 \large b=\left \{ b_{1},0,...,x-y \right \}
  • 要把 x-y 消0，需要 \large \left | x-y \right | 步
  • 所以b[1]会有 \large \left | x-y \right |+1 种方案
#include 
using namespace std;const int N=1e5+10;
long long a[N],zheng,fu;int main()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=2;i<=n;i++){int x=a[i]-a[i-1];if(x>0) zheng+=x;else fu+=abs(x);}cout<

上一篇：信息传递“上豫洛阳麻将开挂教程步骤‘!详细开挂教程-知乎

下一篇：教程讲解银河VG到底能开挂吗,详细开挂教程-知乎

相关内容

热门资讯

【看表情包学Linux】进程地...   🤣 爆笑教程 👉 《看表情包学Linux》👈 猛...
吉字五行及吉凶 吉字五行中代表... 五行解析在文化中，五行是非常重要的概念之一，在这里解析一下五行对于人们生活的影响。首先，金属代表的是...
月老姻缘灵签内容详解大全 月老... 月老灵签 姻缘签44签 求解签君尔目下之人。本是可心满意足之人。焉知后来之人。一个比一个更美好。就此...
六爻排盘蛇 六爻排盘预测绝招 ... 六爻排盘结果怎么看纳甲六爻在线排盘姓名：出生年:1981性别：男占事：起卦方式：手动摇卦公历时间：2...
吉凶由情绪决定 每日吉凶 每月... 情绪的力量情绪是我们生活中一个重要的组成部分。我们每天都会通过不同的方式感受到情绪的存在，而情绪的质...
吉凶悔吝的解释是什么 风水形势... 吉凶悔吝的解释是什么从古至今，人们对于吉凶悔吝都有着不同的看法。所谓吉，是指好的运气，让人们沾沾自喜...
如何看每日生肖运势 每日生肖运... 背景说明每个人都希望自己的运势越来越好，而对于人来说，生肖运势是一个参考价值很高的判断标准。按照传统...
最准观音灵签21签解签 观音灵... 观音灵签21签解签-遵医嘱，健康长寿观音精神签证是中国民间宗教信仰的重要形式，也是一种广泛流传的祈祷...
梦见红裤子被水冲走 梦见河里洗... 梦见红裤子被水冲走红裤子是一种比较鲜艳的颜色，在梦中出现可能代表着某种情绪或状态。而被水冲走则更加具...
十二星座对象配对 12星座最佳... 12星座配偶标准白羊座：温柔善良的人乐观单纯的白羊座在恋爱时喜欢另一半无条件的宠爱自己，另一半对自己...
带水又带土的名字女孩名字有哪些... 含水和土的字有哪些含水的字：淦、澜、浸、泼、滴、没、汪、沸、鸿、沔、浩、渣、溢、潺江、注、漭、淬、澧...
六爻失物卦 在线占卜失物 六爻... 六爻占卜 寻找失物公历起卦时间:2012年12月24日9时44分(按公历时间起卦)农历：仁辰年十一月...
天网今日生肖运势 每日特吉生肖... 天网今日生肖运势天网今日，十二生肖依旧是重要的关键词之一。根据传统文化和民间信仰，每个人都属于一个生...
六爻代表书籍 六爻预测好的书籍... 学六爻的书籍那些比较经典,最好适合初学者的。从古至今六爻类的书流传于世的非常少，六爻类最经典的几本书...
十二星座女生专属花卉 小葩画1... 狮子座的女生喜欢什么样的花1.狮子座的女生喜欢鲜艳、华丽、高贵的花。2.狮子座的女生通常有着自信、热...
客厅风水禁忌及化解 客厅推拉门... 客厅风水禁忌及解决方案客厅是家庭中最重要的空间之一，也是最容易受到风水影响的空间之一。在客厅里，我们...
吉凶参半牛兔在含义 牛兔相冲到... 吉凶参半牛兔在啥意思吉凶参半牛兔在是指属牛的和属兔的结婚以后生活吉凶各一半。丑牛与子鼠六合，因此最宜...
各生肖属相的车牌号码吉凶对照表... 十二生肖与车牌号的佳搭配 十二生肖车牌号吉凶对照表通常每个人的黄道十二宫都会影响车牌号码的运行模式，...
客厅西部尖角的风水 客厅有棱角... 客厅西南角最好的风水是什么？客厅西南角最好的风水是什么？客厅西南角最好的风水是什么？房子的方形风水是...
带昶字的女孩名字 带滢的女孩名... 长字命名的寓意及意义长字命名的寓意和意义是正直、坚强、努力、阳光、前途似景、忠诚。长是一个通用词。长...
六壬怎么算命 六壬掐指神算金口... 什么是六仁？刘仁是中国古代的算命方法，起源于汉代，是中国道教学派的经典之一。刘仁包括六个神：天乙、天...
四月二十九生肖运势 十二生肖鸡... 女1993农历四月二十九早上十点生辰八字是什么如何出生时间：公历 1993年 6月 18日 10点本...
带心字的游戏女孩名字大全集 游... 2020男孩怎么起名有内涵 带心字的男孩名字大全心繁体：心起名五行：金姓名学笔画：4画简体笔画：4画...
八字鬼谷子算命 鬼谷子精髓50... 什么是八字鬼谷子算命？八字鬼谷子算命，又称李静算命，是中国传统的民间算命方式。八字鬼谷子算命起源于六...
十二星座下个月的运势女生 十二... 白羊座下个月的运势女生白羊座女生本身就充满了无限活力和热情，下个月的运势也不会让你失望。职业上可能会...
号令天下手机吉凶预测 号令天下... 手机号怎么算吉凶？用最后四个手机号码除以80，然后减去整数部分(只留小数)，再乘以80，就会得到一个...
命理十二生肖今年运势 明天运势... 命理十二生肖今年运势今年每年都有不同的转瞬即逝的岁月。对于不同的黄道十二宫来说，它每年都有自己独特的...
八字长生好吗 八字中帝旺到长生... 八字日坐长生一定富吗丁火曰元生于未月,余气通根,年支丙火也能助身,但于上两透旺食,生财耗身过甚,故命...
带日的名字女孩名字大全 起名带... 日字旁边的女孩名字大全日字旁边的女孩名字推荐1、诗晗、慧曦、Xi、仲晴2、小芸、小娟、会晴、若昕、敏...
号令天下固话号码测吉凶 查电话... 周易81测手机号码吉凶,号令天下手机号码测吉凶提起周易81测手机号码吉凶，大家都知道，有人问天下手机...