长春专业网站建设公司,网站建设 素材,包头建网站公司哪家强,春雨app直播免费版下载本篇包含6道序列差分练习题及题解#xff0c;难度由模板到提高
语文成绩
题目背景
语文考试结束了#xff0c;成绩还是一如既往地有问题。
题目描述
语文老师总是写错成绩#xff0c;所以当她修改成绩的时候#xff0c;总是累得不行。她总是要一遍遍地给某些同学增加分…本篇包含6道序列差分练习题及题解难度由模板到提高
语文成绩
题目背景
语文考试结束了成绩还是一如既往地有问题。
题目描述
语文老师总是写错成绩所以当她修改成绩的时候总是累得不行。她总是要一遍遍地给某些同学增加分数又要注意最低分是多少。你能帮帮她吗
输入格式
第一行有两个整数 nnnppp代表学生数与增加分数的次数。
第二行有 nnn 个数a1∼ana_1 \sim a_na1∼an代表各个学生的初始成绩。
接下来 ppp 行每行有三个数xxxyyyzzz代表给第 xxx 个到第 yyy 个学生每人增加 zzz 分。
输出格式
输出仅一行代表更改分数后全班的最低分。
样例 #1
样例输入 #1
3 2
1 1 1
1 2 1
2 3 1样例输出 #1
2提示
对于 40%40\%40% 的数据有 n≤103n \le 10^3n≤103。
对于 60%60\%60% 的数据有 n≤104n \le 10^4n≤104。
对于 80%80\%80% 的数据有 n≤105n \le 10^5n≤105。
对于 100%100\%100% 的数据有 n≤5×106n \le 5\times 10^6n≤5×106p≤np \le np≤n学生初始成绩 $ \le 100z \le 100$。 差分入门模板题
#include bits/stdc.h
using namespace std;const int N 5000005;int n, p, ans;
int a[N],b[N];int main()
{cin n p;for(int i 1; i n; i ) {cin a[i];b[i] a[i] - a[i - 1];}while(p --){int x, y, z;cin x y z;b[x] z;b[y 1] - z;}ans 100;for(int i 1; i n; i ) {a[i] a[i - 1] b[i];ans min(ans, a[i]);}cout ans;return 0;
}海底高铁
题目描述
该铁路经过 NNN 个城市每个城市都有一个站。不过由于各个城市之间不能协调好于是乘车每经过两个相邻的城市之间方向不限必须单独购买这一小段的车票。第 iii 段铁路连接了城市 iii 和城市 i1(1≤iN)i1(1\leq iN)i1(1≤iN)。如果搭乘的比较远需要购买多张车票。第 iii 段铁路购买纸质单程票需要 AiA_iAi 博艾元。
虽然一些事情没有协调好各段铁路公司也为了方便乘客推出了 IC 卡。对于第 iii 段铁路需要花 CiC_iCi 博艾元的工本费购买一张 IC 卡然后乘坐这段铁路一次就只要扣 Bi(BiAi)B_i(B_iA_i)Bi(BiAi) 元。IC 卡可以提前购买有钱就可以从网上买得到而不需要亲自去对应的城市购买。工本费不能退也不能购买车票。每张卡都可以充值任意数额。对于第 iii 段铁路的 IC 卡无法乘坐别的铁路的车。
Uim 现在需要出差要去 MMM 个城市从城市 P1P_1P1 出发分别按照 P1,P2,P3,⋯,PMP_1,P_2,P_3,\cdots,P_MP1,P2,P3,⋯,PM 的顺序访问各个城市可能会多次访问一个城市且相邻访问的城市位置不一定相邻而且不会是同一个城市。
现在他希望知道出差结束后至少会花掉多少的钱包括购买纸质车票、买卡和充值的总费用。
输入格式
第一行两个整数N,MN,MN,M。
接下来一行MMM 个数字表示 PiP_iPi。
接下来 N−1N-1N−1 行表示第 iii 段铁路的 Ai,Bi,CiA_i,B_i,C_iAi,Bi,Ci。
输出格式
一个整数表示最少花费
样例 #1
样例输入 #1
9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10样例输出 #1
6394提示
222 到 333 以及 888 到 999 买票其余买卡。
对于 30%30\%30% 数据 M2M2M2。
对于另外 30%30\%30% 数据 N≤1000M≤1000N\leq1000M\leq1000N≤1000M≤1000。
对于 100%100\%100% 的数据 M,N≤105Ai,Bi,Ci≤105M,N\leq 10^5A_i,B_i,C_i\le10^5M,N≤105Ai,Bi,Ci≤105。
#include bits/stdc.h
using namespace std;
/*
在读入p数组的时候
给两个目的地之间做好标记
用差分来标记!
这样最后再求一遍前缀和
就会出来每条路线走过的次数
对每条路线单独判定方案即可这题卡常了。。
忘记了以后还是别偷懒了
*/
typedef long long LL;
const int N 100005, M 100005;LL n, m, sum;
int p[M];
LL a[N], b[N], c[N];
LL s1[N]; //差分数组
LL cnt[N]; //记录每个线路经过几次LL ponder(int t) //t号线的最佳方案
{return min(a[t] * cnt[t], c[t] b[t] * cnt[t]);
}int main()
{//第i段铁路连接 i 和 i 1cin n m;cin p[1];for(int i 2; i m; i ) {cin p[i];int a min(p[i], p[i - 1]);int b max(p[i], p[i - 1]);s1[a] 1;s1[b] - 1; //这里不是b 1哦....}for(int i 1; i n; i ) {cin a[i] b[i] c[i];cnt[i] cnt[i - 1] s1[i]; //顺便求前缀和}for(int i 1; i n; i ) {sum ponder(i); //斟酌一下对于这条路哪个方案更好}cout sum;return 0;
}。。。。。。。。。。。。。。。。。。。。。。 上面算是入门级难度接下来的几题是差分套差分的一些经典例子
Lycanthropy
题目背景
小正方形亲眼看见了自己昔日的朋友被卷进了黑暗的深渊然而它无力阻止……
现在它的朋友已经向它发起了攻击因此小正方形不得不抵抗。
题目描述
我们把山顶上的湖泊看作一条长度为 mmm 的直线一开始水深都在水平线上我们视作此时的水深为 ‘0’
接下来在一瞬间小正方形的朋友们跳起并扎入水中导致在入水点的水降低而远离入水点的水升高注意两个 “朋友” 可能在同一地点入水。
小正方形的每个朋友有一个体积数值 vvv当体积为 vvv 的一个朋友跳入水中我们设入水点为 iii将会导致 i−v1i - v 1i−v1 到 iii 的水位依次降低 1,2,⋯,v1,2,\cdots,v1,2,⋯,v
同样地第 iii 到 iv−1i v - 1iv−1 的水位会依次降低 v,v−1,⋯,1v,v - 1,\cdots,1v,v−1,⋯,1.
相对应地i−vi - vi−v 的水位不变 i−v−1i - v - 1i−v−1 到 i−2∗vi - 2 * vi−2∗v 水位依次增加 1,2,⋯,v1,2,\cdots,v1,2,⋯,v i−2∗vi - 2 * vi−2∗v 到 i−3∗v1i - 3 * v 1i−3∗v1 水位依次增加 v,v−1,⋯,1v,v - 1,\cdots,1v,v−1,⋯,1
同样ivi viv 水位不变iv1i v 1iv1 到 i2∗vi 2 * vi2∗v 水位增加 1,2,⋯,v1,2,\cdots,v1,2,⋯,vi2∗vi 2 * vi2∗v 到 i3∗v−1i 3 * v - 1i3∗v−1 水位依次增加 v,v−1,⋯,1v,v - 1,\cdots,1v,v−1,⋯,1
现在小正方形想要穿过这个湖他想要知道在这 nnn 个朋友跳入水中后湖上每个节点的水位你能帮帮它吗
输入格式
第一行为两个整数 nnn,mmm表示朋友的数目与湖泊的宽度。
接下来 nnn 行一行两个整数 v,xv,xv,x表示第 i1i 1i1 个朋友的体积与入水点。
输出格式
一行 mmm 个整数第 iii 个整数表示 iii 号位的水深。
样例 #1
样例输入 #1
1 10
1 5样例输出 #1
0 0 1 0 -1 0 1 0 0 0样例 #2
样例输入 #2
2 10
2 6
3 1样例输出 #2
-2 0 0 0 0 0 2 2 2 2提示
对于 30%30\%30% 的数据n50,m500n 50,m 500n50,m500
对于 70%70\%70% 的数据n105,m105n 10^5,m 10^5n105,m105
对于 100%100\%100% 的数据n106,m106,1v10000,1xmn 10^6,m 10^6,1 v 10000,1 x mn106,m106,1v10000,1xm
#include bits/stdc.h
using namespace std;
/*
差分套差分
求两遍前缀和
*/const int N 1000005, M 2000005, dif 50000;
//dif为偏移量避免REint n, m;
int h[M];
int s[M]; //初级差分数组
int s2[M]; //最外层差分
int mm 100000000, MM;int main()
{cin n m;for(int i 1; i n; i ) {int v, x;cin v x;//记录下被影响到的边界//前缀和要从边界开始求mm min(mm, x - 3 * v 1 dif);MM max(MM, x 3 * v dif);s[x - 3 * v 1 dif] 1;s[x - 2 * v 1 dif] - 2;s[x 1 dif] 2;s[x 2 * v 1 dif] - 2;s[x 3 * v 1 dif] 1;}for(int i mm; i MM; i ) {s2[i] s2[i - 1] s[i];}for(int j mm; j MM; j ) {h[j] h[j - 1] s2[j];}for(int i 1; i m; i ) cout h[i dif] ;return 0;
}三步必杀
题目背景
三旧都
离开狭窄的洞穴眼前豁然开朗。
天空飘着不寻常的雪花。
一反之前的幽闭现在面对的是繁华的街市可以听见酒碗碰撞的声音。
这是由被人们厌恶的鬼族和其他妖怪们组成的小社会一片其乐融融的景象。
诶不远处突然出现了一些密密麻麻的小点好像大颗粒扬尘一样。
离得近了点终于看清楚了。
长着角的鬼们聚在一起围观着另一只鬼的表演。
那”扬尘”其实都是弹幕。
勇仪的招数之一三步之内所到之处弹幕云集几乎没有生存可能。
为了强化这一技能勇仪将对着一排柱子进行攻击。
旧地狱的柱子虽然无比坚固但保险起见还是先要了解一下这样一套攻击对柱子有多少损伤顺带也能检验练习的效果。
勇仪决定和其它鬼们商量商量…
“我知道妖怪之山的河童一族有一种叫做计算机的神奇道具说不定可以借来用用”萃香说道。
于是旧地狱的鬼族就决定请河城荷取来帮忙了。
“要记录【所有柱子的损伤程度】吗”荷取问道。
经过进一步的询问荷取发现他们仅仅需要【所有攻击都完成后】柱子的损伤程度。
任务了解地差不多了荷取将其中的重要部分提取了出来记录在了她的工作笔记本上
(记录的内容见题目描述)
那么实验就这样开始了。
在惊天动地的碰撞声中勇仪每完成一轮攻击荷取都忠实地记录下对每根柱子产生的伤害。而此时勇仪就在旁边等待着记录完成然后再进行下一轮的攻击。
地面上天色渐晚。
“不想在这里留到深夜啊不然就回不了家了”荷取这样想着手中依然在重复地向计算机中输入新产生的信息。
“真的必须一次一次地记录下每轮攻击对每个柱子产生的伤害吗有没有更高效的方法”这一念头在荷取的心中闪过…
后续剧情在题解中接下来请看T3
题目描述
问题摘要
NNN个柱子排成一排一开始每个柱子损伤度为0。
接下来勇仪会进行MMM次攻击每次攻击可以用4个参数lll,rrr,sss,eee来描述
表示这次攻击作用范围为第lll个到第rrr个之间所有的柱子(包含lll,rrr)对第一个柱子的伤害为sss对最后一个柱子的伤害为eee。
攻击产生的伤害值是一个等差数列。若l1l1l1,r5r5r5,s2s2s2,e10e10e10则对第1~5个柱子分别产生2,4,6,8,10的伤害。
鬼族们需要的是所有攻击完成之后每个柱子的损伤度。
输入格式
第一行2个整数NNN,MMM用空格隔开下同。
接下来MMM行每行4个整数lll,rrr,sss,eee含义见题目描述。
数据保证对每个柱子产生的每次伤害值都是整数。
输出格式
由于输出数据可能过大无法全部输出为了确保你真的能维护所有柱子的损伤度只要输出它们的异或和与最大值即可。
异或和就是所有数字按位异或起来的值
异或运算符在c里为^
样例 #1
样例输入 #1
5 2
1 5 2 10
2 4 1 1样例输出 #1
3 10样例 #2
样例输入 #2
6 2
1 5 2 10
2 4 1 1样例输出 #2
3 10提示
样例解释
样例1
第一次攻击产生的伤害:2 4 6 8 10
第二次攻击产生的伤害:0 1 1 1 0
所有攻击结束后每个柱子的损伤程度:2 5 7 9 10。
输出异或和与最大值就是3 10。
样例2
没有打到第六根柱子答案不变
数据范围
本题满分为100分下面是4个子任务。(x/y)表示(得分/测试点数量)
妖精级(18/3):1⩽n1\leqslant n1⩽n,m⩽1000m\leqslant1000m⩽1000。这种工作即使像妖精一样玩玩闹闹也能完成吧
河童级(10/1):sesese,这可以代替我工作吗
天狗级(20/4):1⩽n⩽1051\leqslant n\leqslant10^51⩽n⩽105,1⩽m⩽1051\leqslant m\leqslant10^51⩽m⩽105。小打小闹不再可行了呢。
鬼神级(52/2):没有特殊限制。要真正开始思考了。
以上四部分数据不相交。
对于全部的数据:1⩽n⩽1071\leqslant n\leqslant10^71⩽n⩽107,1⩽m⩽3×1051\leqslant m\leqslant3\times 10^51⩽m⩽3×1051⩽lr⩽n1\leqslant lr\leqslant n1⩽lr⩽n.
所有输入输出数据以及柱子受损伤程度始终在[0,9×1018][0,9\times 10^{18}][0,9×1018]范围内。
提示
由于种种原因时间限制可能会比较紧C选手请不要使用cin读入数据。
by orangebird
#include bits/stdc.h
using namespace std;
/*
Lycanthropy那题的升级版
那题就是公差为1和-1的情况
这题需要自己算公差
差分套差分
求两遍前缀和
*/
typedef long long LL;
const int N 10000005, M 300005;LL n, m, ans, MM;
LL hurt[N];
int s1[N], s2[N], h[N];int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n m;for(int i 1; i m; i ) {LL l, r, s, e;cin l r s e;LL d (e - s) / (r - l); //求公差s1[l 1] d;s1[r 1] - d;h[l] s; //首项也要记录一下 h[r 1] - e; //不把这个删掉的话后面不在这个范围内的也会累加上这个末项}for(int i 1; i n; i ) {s2[i] s2[i - 1] s1[i];hurt[i] hurt[i - 1] s2[i] h[i];ans ^ hurt[i];if(MM hurt[i]) MM hurt[i];}cout ans MM;return 0;
}[Poetize6] IncDec Sequence
题目描述
给定一个长度为 nnn 的数列 a1,a2,⋯,an{a_1,a_2,\cdots,a_n}a1,a2,⋯,an每次可以选择一个区间[l,r][l,r][l,r]使这个区间内的数都加 111 或者都减 111。
请问至少需要多少次操作才能使数列中的所有数都一样并求出在保证最少次数的前提下最终得到的数列有多少种。
输入格式
第一行一个正整数 nnn 接下来 nnn 行,每行一个整数,第 $i1 $行的整数表示 aia_iai。
输出格式
第一行输出最少操作次数 第二行输出最终能得到多少种结果
样例 #1
样例输入 #1
4
1
1
2
2样例输出 #1
1
2提示
对于 100%100\%100% 的数据n≤100000,0≤ai≤231n\le 100000, 0 \le a_i \le 2^{31}n≤100000,0≤ai≤231。
#include bits/stdc.h
using namespace std;
/*
首先对原序列求差分
会得到一些正负数和0
目标就是把他们全都变成0
当然第一项随便是几都行
所以先不要去改变第一项
把第一项放到一边去这种区间操作1、-1
只会改变差分序列的边界
序列的中间部分是不会改变的
所以最贪心的操作就是在序列中找到一个正数一个负数
让正数-1、负数1
对应的操作就是让原序列的中间部分整体-1
所以就在差分序列中求出正数的总和和负数的总和的绝对值
min(cnt[], cnt[-]) 就是最贪心的操作次数
做完以后还会剩下一些没法抵消的
那么就利用两个端点
整体1或-1来抵消
端点的选择可以是第一项也可以是最后一项
改变第一项的话就会多一种答案了
所以有多少个不能抵消的
就又会有多少个不同答案
*/
typedef long long LL;
const int N 100005;int n;
LL a[N], d[N];
LL pos, neg; //差分序列的正负数分别的绝对值总和
LL cnt, dif;int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;for(int i 1; i n; i ) {cin a[i];d[i] a[i] - a[i - 1];if(i 1) continue;if(d[i] 0) pos d[i];else neg d[i];}cnt min(pos, abs(neg));dif abs(pos - abs(neg)); //表示需要单独操作的次数cnt dif;cout cnt endl dif 1;return 0;
}[NOIP2012 提高组] 借教室
题目描述
在大学期间经常需要租借教室。大到院系举办活动小到学习小组自习讨论都需要向学校申请借教室。教室的大小功能不同借教室人的身份不同借教室的手续也不一样。
面对海量租借教室的信息我们自然希望编程解决这个问题。
我们需要处理接下来 nnn 天的借教室信息其中第 iii 天学校有 rir_iri 个教室可供租借。共有 mmm 份订单每份订单用三个正整数描述分别为 dj,sj,tjd_j,s_j,t_jdj,sj,tj表示某租借者需要从第 sjs_jsj 天到第 tjt_jtj 天租借教室包括第 sjs_jsj 天和第 tjt_jtj 天每天需要租借 djd_jdj 个教室。
我们假定租借者对教室的大小、地点没有要求。即对于每份订单我们只需要每天提供 djd_jdj 个教室而它们具体是哪些教室每天是否是相同的教室则不用考虑。
借教室的原则是先到先得也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足则需要停止教室的分配通知当前申请人修改订单。这里的无法满足指从第 sjs_jsj 天到第 tjt_jtj 天中有至少一天剩余的教室数量不足 djd_jdj 个。
现在我们需要知道是否会有订单无法完全满足。如果有需要通知哪一个申请人修改订单。
输入格式
第一行包含两个正整数 n,mn,mn,m表示天数和订单的数量。
第二行包含 nnn 个正整数其中第 iii 个数为 rir_iri表示第 iii 天可用于租借的教室数量。
接下来有 mmm 行每行包含三个正整数 dj,sj,tjd_j,s_j,t_jdj,sj,tj表示租借的数量租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 111 开始的整数编号。
输出格式
如果所有订单均可满足则输出只有一行包含一个整数 000。否则订单无法完全满足
输出两行第一行输出一个负整数 −1-1−1第二行输出需要修改订单的申请人编号。
样例 #1
样例输入 #1
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4样例输出 #1
-1
2提示
【输入输出样例说明】
第 111份订单满足后444天剩余的教室数分别为 0,3,2,30,3,2,30,3,2,3。第 222 份订单要求第 222天到第 444 天每天提供333个教室而第 333 天剩余的教室数为222因此无法满足。分配停止通知第222 个申请人修改订单。
【数据范围】
对于10%的数据有1≤n,m≤101≤ n,m≤ 101≤n,m≤10
对于30%的数据有1≤n,m≤10001≤ n,m≤10001≤n,m≤1000
对于 70%的数据有1≤n,m≤1051 ≤ n,m ≤ 10^51≤n,m≤105
对于 100%的数据有1≤n,m≤106,0≤ri,dj≤109,1≤sj≤tj≤n1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n1≤n,m≤106,0≤ri,dj≤109,1≤sj≤tj≤n。
NOIP 2012 提高组 第二天 第二题
2022.2.20 新增一组 hack 数据
#include atomic
#include bits/stdc.h
using namespace std;
/*
明显的区间修改和单点查询
m*n的复杂度明显不行
偷看标签发现了二分。。。
确实是单调的
越是编号靠后的人
越难以成功申请到教室
因此可以用二分来优化
*/
typedef long long LL;
const int N 1000005;struct Order
{int d, s, e;}ord[1000005]; //订单int n, m;
LL r[N]; //每天可用于租借地教室数量LL b[N]; //教室的差分数组求前缀和可得教室数组a
LL a[N];bool check(int x) //检验x号订单能否成功
{memset(b, 0, sizeof b);memset(a, 0, sizeof a);for(int i 1; i x; i ) {int d ord[i].d, s ord[i].s, e ord[i].e;b[s] d;b[e 1] - d;}for(int i 1; i n; i ) {a[i] a[i - 1] b[i];if(r[i] a[i]) return false;} //求一遍前缀和得到每天需要的教室数量return true;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n m; //天数和订单数量for(int i 1; i n; i ) cin r[i];for(int i 1; i m; i ) {cin ord[i].d;cin ord[i].s;cin ord[i].e;}int l 1, r m;while(l r){int mid (l r) / 2;if(check(mid)) l mid 1;else r mid - 1;}if(l m 1) cout 0;else cout -1 \n l;return 0;
}
