【题目描述】

地面上有一排长度为n的格子1-n，每个格子上都有一个数xi，开始时你在位置0，每次你可以向前跳1-2格，然后取走格子上的数，直到跳到位置n+1。取走的数的和就是你的得分，现在你想知道你可能的最大得分是多少。

【输入描述】

【输出描述】

【样例输入】

3 1 1 1

【样例输出】

-9993

【题目描述】

求一个数列的所有前缀最大值之和。

即：给出长度为n的数列a[i],求出对于所有1<=i<=n，max(a[1],a[2],...,a[i])的和。

比如，有数列：666 304 692 188 596，前缀最大值为：666 666 692 692 692，和为3408。

对于每个位置的前缀最大值解释如下：对于第1个数666，只有一个数，一定最大；对于第2个数，求出前两个数的最大数，还是666；对于第3个数，求出前3个数的最大数是692……其余位置依次类推，最后求前缀最大值得和。



由于读入较大，数列由随机种子生成。

其中a[1]=x，a[i]=(379*a[i-1]+131)%997。

【输入描述】

一行两个正整数n,x，分别表示数列的长度和随机种子。(n<=100000,x<997)

【输出描述】

一行一个正整数表示该数列的前缀最大值之和。

【样例输入】

5 666  Copy

【样例输出】

3408

【提示】

数列为{666,304,692,188,596}，前缀最大值为{666,666,692,692,692},和为3408。

【题目描述】

求一个数列的所有前缀最小值之和。

即：给出长度为n的数列a[i],求出对于所有1<=i<=n，min(a[1],a[2],...,a[i])的和。

由于读入较大，数列由随机种子生成。

其中a[1]=x，a[i]=(379*a[i-1]+131)%997。

【输入描述】

一行两个正整数n,x，分别表示数列的长度和随机种子。(n<=100000,x<997)

【输出描述】

一行一个正整数表示该数列的前缀最小值之和。

【样例输入】

5 666

【样例输出】

1650

【提示】

数列为{666,304,692,188,596}，前缀最小值为{666,304,304,188,188},和为1650。

前缀最小：

比如，有数列：666 304 692 188 596，前缀最大值为：666,304,304,188,188，和为1650。

对于每个位置的前缀最小值解释如下：对于第1个数666，只有一个数，一定最大；对于第2个数，求出前两个数的最小数，还是304；对于第3个数，求出前3个数的最小数是304……其余位置依次类推，最后求前缀最小值得和。

【题目描述】

NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为w$\mathrm{\%}$，即当前排名前 w$\mathrm{\%}$ 的选手的最低成绩就是即时的分数线。

$max(1,\lfloor p\ast w\mathrm{\%}\rfloor )$，其中 $w$ 是获奖百分比，$\lfloor x\rfloor$ 表示对$x$ 向下取整，$max(x,y)$ 表示 x 和y 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

【输入描述】

第一行有两个整数 n$,w$。分别代表选手总数与获奖率。

第二行有 $n$ 个整数，依次代表逐一评出的选手成绩。

【输出描述】

只有一行，包含 n 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。

【样例输入】

10 60  200 300 400 500 600 600 0 300 200 100

【样例输出】

200 300 400 400 400 500 400 400 300 300

【提示】

样例 1 解释:

注意，在第9名选手的成绩评出之后，计划获奖人数为5人，但由于有并列，实际会有6人获奖。

输入样例2：

10 30  100 100 600 100 100 100 100 100 100 100

输出样例2：

100 100 600 600 600 600 100 100 100 100

【数据规模与约定】:

各测试点的n 如下表：

【提示】

在计算计划获奖人数时，如用浮点类型的变量（如 C/C++ 中的 float 、 double，Pascal 中的 real 、 double 、 extended 等）存储获奖比例w$\mathrm{\%}$，则计算5$\times 60\mathrm{\%}$ 时的结果可能为$3.000001$，也可能为 $2.999999$，向下取整后的结果不确定。因此，建议仅使用整型变量，以计算出准确值。

【题目分析】

• 排序题，最简单的思路是每次新加一个人，然后就sort一遍，但是这样做肯定会超时的（n=100000）。

• 其实，从题目中给的测试数据可以发现，每个选手的成绩并不大，不超过600。那么比较好的做法就是用桶排了。

1. 样例

   
   
   

#include<iostream>  using namespace std;  int main(){  	cout<<(1&1)<<endl; //1   	cout<<(1&-1)<<endl; // 1   	cout<<(-1&-1)<<endl; //-1   	cout<<(-2&-3)<<endl; //-4   	return 0;  }

2.解释

 1&1：

      1    0000 0001  

      &   

      1    0000 0001  

-----------------------

      1    0000 0001   

 1&-1：

     1    0000 0001  

      &   

     -1   1111 1111  （补码）

-----------------------

      1    0000 0001   

解释：1的补码是1111 1111，然后进行逻辑与运算即可。

 -1&-1：

     -1   1111 1111  （补码）

      &   

     -1   1111 1111  （补码）

-----------------------

           1111 1111   

解释：负数和负数的逻辑与运算比较特殊。

-1 & -1 的直接结果是1111 1111，出符号位以外，剩下111 1111

然后把最低位减一得： 111 1110

然后按位取反得： 000 0001, 也就是1

加上符号就是-1，所以最后结果是-1

 -2&-3：

     -2   1111 1110 （补码）

      &   

     -3   1111 1101  （补码）

-----------------------

           1111 1100   

解释：

-2 & -3 的直接结果是1111 1100  ，出符号位以外，剩下111 1100

然后把最低位减一得： 111 1011

然后按位取反得： 000 0100, 也就是4

加上符号就是-1，所以最后结果是-4

一、差分：一维数组的差分可看作是一维数组前缀和的逆运算。

二、差分数组

首先给定一个原数组a:   a[1]、a[2]、a[3]、......

然后构造一个数组b: b[1]、b[2]、b[3]....

使得a[i]=b[1]+b[2]+b[3]+b[4]+.....b[i]。

那么根据上一节讲的，a数组就是b数组的前缀和数组。 

也就是说，a数组就是b数组的前缀和数组，反过来，我们把b数组叫做a数组的差分数组。话句话说，每一个a[i]数组都是b数组中从头开始的一段区间和。

三、功能及作用

    给区间[L,R]中每个数加上 c:  B[L] +=c， B[R+1] -=c

四、构造

考虑如何构造差分数组b：

最为直接的方法：

a[0]=0  b[1]=a[1]-a[0];  b[2]=a[2]-a[1];  b[3]=a[3]-a[2];  ......  b[n]=a[n]-a[n-1];

五、应用

【问题描述】给定区间[L,R]，让我们把a数组中的[L,R]区间中的每一个数都加上c， 即a[L]+c,  a[L+1]+c,  a[L+2]=c , ....  a[R]+c

解法一：暴力解法

用for循环，从L到R区间，时间复杂度O（n），如果我们需要对原数组执行m次这样的操作，那么时间复杂度就会变成O(n*m)。

解法二：差分

始终要记住一点：a数组是b数组的前缀和数组。比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

首先让差分b数组中的b[L]+c，通过前缀和运算，a数组变成a[L]+c,... a[L+1]+c,.... a[n]+c

然后我们打个补丁， b[R+1] -c ，通过前缀和运算， a数组变成 a[R+1]-c,  ...  a[R+2]-c, ...   a[n] -c, ...

图解过程：

b[L]+c, 效果使得a数组中a[L]及以后的数都加上了c(红色部分)，但是我们只要求L到R区间加上c，因此还需要执行b[R+1]-c， 让a数组中a[R+1]以及往后的区间再减去c(绿色部分)，这样对于a[r]以后区间的数组相当于没有发生改变。

结论：给a数组中的[L,R]区间中的每一个数加上c。只需要对差分数组b做b[L]+=c，b[R+]-=c，时间复杂度为O（1）。

如果上面的描述不够清楚，我们可以借助下面方式来表示，我们假设a数组是原始数组，b数组是差分数组。我们的目的是让a数组的某个区间段加上一个数c。初始状态如下：

需求1：我们要将[1,4]范围内所有的数都加上3

规律：当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反地变化。

那么用代码表示：

while(t--){//操作次数  	cin>>x>>y>>change;//左右端点值   	cin>>c;//c是每次加减的值   	b[x]=b[x]+c;  	b[y+1]=b[y+1]-c;  }

那么能不能反过来求a[i]呢，因为b数组是差分数组，满足公式b[i]=a[i]-a[i-1]

那么a[i]=a[i-1]+b[i]

六、题目

【题目描述】

输入一个长度为n的整数序列。

接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

【输入描述】

第一行包含两个整数n和m。

第二行包含n个整数，表示整数序列。

接下来m行，每行包含三个整数l，r，c，表示一个操作。

【输出描述】

共一行，包含n个整数，表示最终序列。

【样例输入】

6 3  1 2 2 1 2 1  1 3 1  3 5 1  1 6 1

【样例输出】

3 4 5 3 4 2

【数据范围】

1≤n,m≤100000,

1≤l≤r≤n,

−1000≤c≤1000,

−1000≤整数序列中元素的值≤1000

一、定义

前缀和：是指某序列的前n项和。可以理解成数学上上的数列的前n项和。

差分：是前缀和的逆运算。

二、前缀和的分类

可以分成一维数组的前缀和和二维 数组的前缀和

• 一维数组前缀和

    定义式：

 递推式：

• 二维数组前缀和

定义式：

递推式：

三、解决什么问题

前缀和、差分是为了解决某一类问题。比如下面这道题目：

【题目描述】

输入一个长度为n的整数序列。接下来再输入M次询问，每个询问输入一对L, R。对于每次询问，输出原序列中从第L个数到第R个数的和。

【输入描述】

第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。

【输出描述】

共m行，每行输出一个询问的结果。

【样例输入】

5 3  2 1 3 6 4  1 2  1 3  2 4

【样例输出】

3  6  10

【数据范围】

1≤l≤r≤n,

1≤n,m≤100000,

−1000≤数列中元素的值≤1000

【题目描述】

一个5*5的矩阵，矩阵内用0，1显示。其中，0是路，表示这个点可以走，1是墙表示这个点不可以走。

问，从给定的矩阵中从左上角到右下角最少需要走多少步？

注：题目保证有解（不存在左上角和右下角为1的情况）

【输入描述】

一个5*5的矩阵

【输出描述】

一行，表示最少要走多少步？

【样例输入】

0 1 0 0 0  0 1 0 1 0  0 0 0 0 0  0 1 1 1 0  0 0 0 1 0

【样例输出】

8