2026年编程兔冬令营集训第三场作业

1、差分 2、STL

1、通过维护相邻元素的差值，将区间操作转化为端点操作：
a.原数组差分d[i]=a[i]-a[i-1]
b.区间[L,R]加C → d[L] += C; d[R+1] -= C
c.通过差分数组d进行前缀和还原操作后的原数组a
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005];
int n,p,x,y,z,ans=INT_MAX;
int main(){
	cin>>n>>p;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		b[i] = a[i]-a[i-1];//原数组差分 
	}
	while(p-->0){
		cin>>x>>y>>z;
		b[x]+=z;b[y+1]-=z;//区间[x,y]加上z 
	}
	for(int i=1;i<=n;++i){
		b[i]+= b[i-1];//差分数组前缀和，恢复成原数组 
		ans = min(ans,b[i]);
	}
	cout<<ans<<endl;
	return 0;
}

2、利用差分的来处理，a[i]>a[i-1]需要补次数
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int n,ans=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		// 差分，大的说明需要补次数 
		if (a[i]-a[i-1]>0) ans+=a[i]-a[i-1];
	}
	cout<<ans<<endl;
	return 0;
} 

3、有一个二维数组s[N][M]，a[N][M]为s的差分矩阵，那么如下图所示：a矩阵中所有标记为蓝色的元素之和就是s[i,j]，二维前缀和有：s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] +a[i][j];那么通过移项可以知道：a[i][j] = s[i][j] - s[i-1][j] - s[i][j-1] + s[i-1][j-1]；这个公式非常重要，这既是差分矩阵的性质，也是我们求解差分矩阵的重要甚至是唯一的依据。



这里我们假设：我们要在s矩阵紫色位置所有元素+c，这个时候相当于对其差分矩阵a进行以下操作：
a[x1, y1] += c;
a[x1, y2 + 1] -= c;
a[x2 + 1, y1] -=c;
a[x2 + 1, y2 +1] += c;
大家可以结合下面的图片自行验证一下！


#include<iostream>
using namespace std;
const int N = 1010;
// a为s的差分矩阵，s为a的前缀和矩阵
int a[N][N], s[N][N];
// s数组有m行n列，进行q次操作
int m, n, q;
// 对a进行操作（插入）
// 表示对于s数组，以（x1，y1）为左上角，以（x2，y2）为右下角的子矩阵全部都＋c
void insert(int x1, int y1, int x2, int y2, int c) {
    a[x1][y1] += c;
    a[x1][y2 + 1] -= c;
    a[x2 + 1][y1] -= c;
    a[x2 + 1][y2 + 1] += c;
}
int main() {
    scanf("%d%d", &n, &q);
    m=n;
    // 操作q次
    for(int i = 1; i <= q; i ++) {
        int x1, y1, x2, y2, c=1;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        insert(x1, y1, x2, y2, c);
    }
    // 求出s数组（通过差分求前缀和）
    for(int i = 1; i <= m; i ++) {
        for(int j = 1; j <= n; j ++){
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    // 输出s数组
    for(int i = 1; i <= m; i ++) {
        for(int j = 1; j <= n; j ++) {
            cout << s[i][j] <<" ";
        }
        cout << endl;
    }
    return 0;
}

4、在C++ STL（标准模板库）中，set 是一个自带“有序+去重”buff的容器，底层基于红黑树实现，既能自动排序元素，又能保证无重复值，日常开发中处理去重、有序遍历、快速查找等场景时特别好用。
https://mp.weixin.qq.com/s/lQtXpfdh2I83UXauSqnN2Q

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,ans=0;
	string s;
	set<string> st;//定义字符串类型的set 
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>s;
		st.insert(s);//直接存入st，自动去重排序 
	} 
	cout<<52-st.size()<<endl;//st.size()去重后的总数量 
	return 0;
}

5、思考一下这题跟上一题的相似点和不同点？本题需要统计重复数字出现的次数，明显set不能完全符合（只有去重无法统计），而开数组的话，数据范围太大。
在C++中，map 是一种关联容器，用于存储键值对（key-value），其中每个键（key）是唯一的，并且每个键都映射到一个值（value）。map 内部通常使用红黑树实现，因此其插入、删除和查找操作的时间复杂度都是对数级别的（O(log n)）。
每一对中的第一个值称之为关键字(key)，每个关键字只能在map中出现一次；第二个称之为该关键字的对应值（value）。

map适用题目：
a.元素去重，因为map的key也是不能重复的（梦回set）
b.统计数据出现的次数
c.需要将多个数据进行绑定处理的题目
#include <bits/stdc++.h>
using namespace std;
map<int, int> cnt;//定义map，第一维是key出现的数字，第二维是统计次数 
int n, x;
int main(){
    cin >> n;
    while(n--){
        cin >> x;
        cnt[x]++;//类似数组使用，统计次数 
    }
    for(auto x : cnt){//map是有序的，遍历输出 
        cout << x.first << " " << x.second << "\n";
    }
    return 0;
}
6、对比上题，key从数字换成了字符串
#include <bits/stdc++.h>
using namespace std;
map<string, int> cnt;//定义map，第一维是key出现的字符串，第二维是对应的数字 
int n, q,x;
string s;
int main(){
    cin >> n>>q;
    while(n--){
        cin>>s>>x;
        cnt[s]=x;//s--x对应 
    }
    while(q--){
    	cin>>s;
    	cout<<cnt[s]<<endl;//字符串下标的数组 
	} 
    return 0;
}