深圳网站设计九曲网站建设,制作视频的软件哪个好用,多用户商城源码下载,wordpress cdn插件差分
Codeforces802 D2C C代码详解 差分_哔哩哔哩_bilibili
一维差分
差分与前缀和可以说成减法和加法的关系、除法和乘法的关系、积分和微分的关系#xff08;听不懂吧#xff09;
给定数组A#xff0c;S为A的前缀和数组#xff0c;则A为S的差分数组 差分数组构造
现…差分
Codeforces802 D2C C代码详解 差分_哔哩哔哩_bilibili
一维差分
差分与前缀和可以说成减法和加法的关系、除法和乘法的关系、积分和微分的关系听不懂吧
给定数组AS为A的前缀和数组则A为S的差分数组 差分数组构造
现在有了前缀和数组就要推导差分数组数学上有个递推公式AnSn-S(n-1)。其中A为差分S为前缀和。这个公式只需要记住差分数组是什么就行。
差分数组应用
差分有什么用呢差分可以使一个数组S中一段区间每个元素加上常数C。比如说有任意一个数组S区间[l,r]内每一个元素均加上常数j。若用暴力枚举[l,r]中每一个元素加j时间复杂度为O(n)显然有更快的算法。若用差分假设S的差分数组为A则在A中标记第l个加j第r1个减j这时再把差分数组化成前缀和数组即可得到目标数组时间复杂度O(n)
话不多说让我们写代码八 输入长度为n的整数序列 接下来输入m个操作每个操作包含三个整数 lrc表示将序列中 [ l, r ] 之间的每个数加上c。 输入格式 第一行包含两个整数n和m。 第二行包含n个这个数表示整数序列。 接下来m行每行包括三个整数 lrc表示一个操作 #include iostreamusing namespace std;const int N 1e6 10;int a[N];int b[N];void insert(int l, int r, int c)
{b[l] c;b[r 1] - c;
}int main()
{int n, m;cin n m;for (int i 1; i n; i){cin a[i];}for (int i 1; i n; i){insert(i, i, a[i]);}while (m--){int l, r, c;cin l r c;insert(l, r, c);}for (int i 1; i n; i){b[i] b[i - 1];cout b[i] ;}return 0;
}太戈编程736题
题目描述
你是一只汪星人地球毁灭后你回到了汪星这里每天有n个小时你需要为自己选择正好连续的m小时作为每天睡眠的时间。从凌晨开始第i小时内的睡眠质量为xi请问经过选择后你的睡眠质量总和最大是多少
法1 cinnm;
for(int i1;in;i) cinx[i];
for(int in1;in*2;i) x[i]x[i-n];
s[0]0;
for(int i1;in*2;i) s[i]s[i-1]x[i];
int anss[m];
for(int im1;in*2;i)ansmax(ans,s[i]-s[i-m]);
coutansendl; 法2 cinnm;
for(int i1;in;i) cinx[i];
for(int i1;in;i) s[i]s[i-1]x[i];
int anss[m];
for(int im1;i;i)ansmax(ans,s[i]-s[i-m]);
for(int i1;im-1;i)ansmax(ans,s[i]s[n]-s[n-mi]);
coutansendl; 注意数组下标要仔细分析
太戈编程第650题
思考五分钟……
cinn;
for(int i1;in;i){cinabx;d[a]x;d[b5]-x;
}
for(int i1;iR;i)s[j]s[i-1]d[i];
cout*max_element(s1,sR)endl; 希望这些对大家有用三连必回
