等差数列题解!.py

看到好多人都写题解了 (就我没有),手痒写一个,难度不算大,就是公式有点难
题目:


样例:

样例解释:

数据范围:
image

总体思路

根据数据规模可知:
你要想用暴力那就用,反正浪费时间才搞到70分,你要问我咋么知道的,呵呵呵


:smiling_face_with_tear: :smiling_face_with_tear: :smiling_face_with_tear:
不管怎么样,你需要使用差分(两次),然后用一堆公式。。。。

    a[pos+1]+=d;
    a[pos+len]-=d*len+p;
    a[pos+len+1]+=d*(len-1)+p;
    a1[pos]+=p;
    a1[pos+1]-=p;

额。你想直接拿来用随你,但是后面有解析,(如果老师问你为什么要用这个怎么办,还是接着往下看吧)

核心代码详细解析
    a1[pos]+=p;

    a1[pos+1]-=p;

    a[pos+1]+=d;

    a[pos+len]-=d*len+p;

    a[pos+len+1]+=d*(len-1)+p;

这个一大堆,我来讲解一下是啥意思
a代表第2层差分
a1代表第1层差分
对于第一次样例操作2, 4, 3, 2,我们可以解析成

    a1[pos]+=p;

第一句:p下去,所以a1里pos的位+p。
.

    a1[pos+1]-=p;

第二句:保证p不像d一样成为一个倍数递增,a1里只有这一个位置是p,让最终答案数组里他始终+p。
.

    a[pos+1]+=d;

第三句:开始对d处理,因为d是在等差数列第二个元素才出现的,所以pos+1位置放d。
.

    a[pos+len]-=d*len+p;

第四句:因为目前代码运行的话会出现最后几个数不是0的情况,所以第四句来了,最后几个数永远都是(len - 1) * d + p,所以我们要减去他,但是后来调的时候发现最后几个数虽然没之前那么大了,但还是有,这就是因为a1里还残留着一个d,我们需要减去a1里的这个d,所以是len * d + p。
.

    a[pos+len+1]+=d*(len-1)+p;

第五句:呼,终于到最后一句了,因为第四句在a1中残留了一些东西。。。
.

这就能让他=0
最终结论(有点乱,可以跳过):

伪代码
#include<bits/stdc++.h>
using namespace std;
// 最终数组和两个差分数组
int main(){
// 输入n, m;
  for(int i=1~m){
    // 输入pos, len, p和d
    // 刚刚教你们的核心代码
  }
  for(int i=2~n){
    a1[i]+=a1[i-1]+a[i];
  }
  for(int i=1~n){
    s[i]=s[i-1]+a1[i];
    // 输出
  }
}

OK,最后声明:小编制作不易(午饭都没吃)可以给一个小小的赞么 :growing_heart:

1 个赞