前缀和与差分概念

有一个数组为 [1, 2, 3, 4, 5] , 他的前缀和数组就是 [1, 3, 6, 10, 15] 公式为 sum[i] = a[i] + sum[i - 1];

有一个数组为 [1, 3, 6, 10, 15] , 他的差分数组为 [1, 2, 3, 4, 5] , 公式为 a[i] = sum[i] - sum[i - 1];

也就是说, 我们在对差分数组中的一个位置 加上一个数时, 如果不在后面减去相同的数值, 那么在对差分数组求前缀和后, 前缀和数组的每一个位置都会加上这个数.

值周 - 差分

题目描述:

JC内长度为L的马路上有一些值周同学，每两个相邻的同学之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0,1,2,…L，都有一个值周同学。 由于水宝宝有用一些区间来和ssy搞事情，所以为了避免这种事走漏风声，水宝宝要踹走一些区域的人。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的人（包括区域端点处的两个人）赶走。你的任务是计算将这些人都赶走后，马路上还有多少个人。

输入描述:

第一行有2个整数L和M，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。 接下来的M行每行包含2个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标

输出描述:

1个整数，表示马路上剩余的人的数目。

示例1

输入

1
2
3
4

500 3
150 300
100 200
470 471

输出

1

298

说明

对于所有的数据，1 ≤ L ≤ 100000000

对于10%的数据，1 <= M <= 100

对于20%的数据，1 <= M <=1000

对于50%的数据，1 <= M <=100000

对于100%的数据，1 <= M <=1000000

参考代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>

using namespace std;

const int N = 100000010;

int a[N], sum, ans;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    
    int n, m; cin >> n >> m;
    
    for(int i = 0; i < m; i ++){
        int st, ed; cin >> st >> ed;
        a[st] += 1;
        a[ed + 1] -= 1;
    }
    for(int i = 0; i <= n; i ++){
        sum += a[i];
        if(sum == 0) ans++;
    }
    
    cout << ans << endl;
    
    return 0;
}

中位数图 - 前缀和

题目描述

给出 1 ~ n 的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

输入描述:

第一行为两个正整数 n 和 b ，第二行为 1 ~ n 的排列。

输出描述:

输出一个整数，即中位数为 b 的连续子序列个数。

示例1

输入

1
2

7 4
5 7 2 4 3 1 6

输出

1

4

备注:

对于30%的数据中，满足 n ≤ 100;

对于60%的数据中，满足 n ≤ 1000;

对于100%的数据中，满足 n ≤ 100000, 1 ≤ b ≤ n。

参考代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 100010;
int a[N];
unordered_map<int,int> occ;

int main() {
    int n, b; cin >> n >> b;
    int pos = -1;
    for(int i = 0; i < n; i++) {
        int t; cin >> t;
        if(t > b) a[i] = 1;
        else if(t < b) a[i] = -1;
        else pos = i;
    }
    int sum = 0, ans = 1, cur;
    for(cur = pos - 1; cur >= 1; --cur) {
        sum += a[cur];
        occ[sum]++;
        if(sum == 0) ans++;
    }
    sum = 0;
    for(cur = pos + 1; cur < n; ++cur) {
        sum += a[cur];
        ans += occ[-sum];
        if(sum == 0) ans++;
    }
    
    cout << ans << endl;
    
    return 0;
}

激光炸弹 - 二维前缀和

题目中的正方形边上的目标不会被摧毁存在问题, 实际上需要计算这一部分

题目描述

一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。

现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。

若目标位于爆破正方形的边上，该目标将不会被摧毁。

输入描述:

输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。

输出描述:

输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。

示例1

输入

1
2
3

2 1
0 0 1
1 1 1

输出

1

1

备注:

对于100%的数据，保证 1 ≤ n ≤ 10^4，0 ≤ xi, yi ≤ 5 × 10^3，1 ≤ m ≤ 5 × 10^3，1 ≤ vi <100.

参考代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>

using namespace std;

const int N = 5010;

int s[N][N];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n, r; cin >> n >> r;
    
    int xx = r, yy = r;
    
    for(int i = 0; i < n; ++i){
        int x, y, w;
        cin>> x >> y >> w;
        s[++x][++y] += w;
        xx = max(xx, x);
        yy = max(yy, y);
    }
    
    for(int i = 1; i <= xx; ++i)
        for(int j = 1; j <= yy; ++j)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    
    int ans = 0;
    
    for(int i = r; i <= xx; ++i)
        for(int j = r; j <= yy; ++j)
            ans = max(ans, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
    
    cout << ans << endl;
    
    return 0;
}

二分 - 离散化, 差分

题目虽然为二分, 实际上并不需要使用二分解题.

我们可以通过枚举一个范围内的值得到答案.

按照示例输入来说

5 . 在枚举值处于 [5, 5] 区间内可以正确答案数加一;

8 + 在枚举值处于 [INT_MIN, 7] 正确答案数可以加一;

8 - 在枚举值处于 [8, INT_MAX) 正确答案数可以加一;

题目描述

我们刚刚学了二分查找——所谓二分查找就是在一堆有序数里找某个符合要求的数。在学完二分查找之后如果让你玩猜数游戏（裁判选定一个目标数字，你说一个数裁判告诉你是高了还是低了直到你猜到那个数）的话，显然你会用二分的方式去猜。

但是不是每一个玩猜数游戏的人都知道二分是最好，甚至一个健忘的玩家都有可能在得到裁判回答的下一个瞬间就忘了他之前问了什么以及裁判的回答），而现在更可怕的是，这个告诉你猜的数是高还是低的裁判他也很健忘，他总是薛定谔的记得这个目标数字，也就是说他的回答有可能出错。我们已经不关心这个不靠谱的游戏本身了，我们更关心裁判这个薛定谔的记得到底有几个是记得……

现在给出这个健忘的玩家的所有猜测和裁判的所有回答，问裁判最多能有多少次是记得目标数字的，即裁判的回复是符合情况的。

输入描述:

第一行包含一个正整数n，表示裁判的回答数（也是玩家的猜数次数）。 接下来n行，首先是猜的数，然后是一个空格，然后是一个符号。符号如果是“+”说明猜的数比答案大，“-”说明比答案小，“.”说明猜到了答案。

输出描述:

包含一个正整数，为裁判最多有多少个回答是正确的。

示例1

输入

1
2
3
4
5

4
5 .
8 +
5 .
8 -

输出

1

3

说明

当目标数组是5时，5 . 5 . 8 + 这三个回答都是正确的

备注:

n ≤ 100000 所有数的大小都小于int类型最大值。

参考代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>
#include <map>
#include <climits>

using namespace std;

map<int, int> mp;

int main() {
    int n; cin >> n;
    for(int i = 0; i < n; ++i) {
        int a;
        char c;
        cin >> a >> c;
        if(c == '+') {
            mp[a]--;
            mp[INT_MIN]++;
        } else if(c == '-') {
            mp[a + 1]++;
            mp[INT_MAX]--;
        } else {
            mp[a]++;
            mp[a + 1]--;
        }
    }
    
    int ans = 0, sum = 0;
    for(auto &[k, v] : mp) {
        sum += v;
        ans = max(sum, ans);
    }
    
    cout << ans << endl;
    
    return 0;
}

货仓选址 - 差值求和

这道题目实际上就是找到一个中位数, 排序后求两端差值的和就好了, 放到前缀和与差分专题里可能是因为对差值求和了? 🤔

题目描述

在一条数轴上有N家商店，它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入描述:

第一行一个整数N，第二行N个整数A[1]~A[N]。

输出描述:

一个整数，表示距离之和的最小值。

示例1

输入

1
2

4
6 2 9 1

输出

1

12

备注:

对于100%的数据: N≤100000, A[i]≤1000000

参考代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int a[N];

int main() {
    int n; cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    sort(a, a + n);
    long long ans = 0;
    for(int i = 0, j = n - 1; i < j; ++i, --j)
        ans += a[j] - a[i];
    
    cout << ans << endl;
    
    
    return 0;
}