【算法/训练】：前缀和&&差分_机器学习

✨ 海压竹枝低复举，风吹山角晦还明 🌏

📃个人主页：

🔥个人专栏：

🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞

🚀 前言：

前面我们已经通过【算法/学习】前缀和&&差分-csdn博客学习了前缀和&&差分的效相关知识，现在我们开始进行相关题目的练习吧

1. 校门外的树

ac代码如下：

#include <iostream>
using namespace std;
const int n = 1e5 + 10;
int a[n];
int main()
{
    int n, m;
    cin>>n>>m;
    for(int i = 0; i <= n; i++) a[i] = 1;
    int l, r;
    for(int i = 1; i <= m; i++)
    {
        cin>>l>>r;
        for(int j = l; j <= r; j++) a[j] = 0;
    }
    int cnt = 0;
    for(int i = 0; i <= n; i++) {
        if(a[i] == 1) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

2. 值周

ac代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int n = 1e7 + 10;

int a[n];

int main()
{
    int n, m;
    cin >> n >> m;
    int l, r;
    for (int i = 0; i < m; i++){
        cin >> l >> r;
        a[l]--, a[r + 1]++;  //前缀和，l-r标记为-1，r + 1又标记为1
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] += a[i - 1];
    }
    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        if (a[i] >= 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

3. [cqoi2009]中位数图

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int n = 1e6 + 10;
ll a[n], s[n];

int main()
{
	int n, b;
	cin >> n >> b;
	int pos, x;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (a[i] > b)a[i] = 1;
		else if (a[i] < b) a[i] = -1;
		else pos = i;//标记中位数的位置
	}

	ll sum = 0, ans = 1; //自己也算一个
	for (int i = pos - 1; i >= 1; i--) {
		sum += a[i];
		s[n + sum]++; //记录左边和为sum的数量
		if (!sum) ans++; //sum为零就说明小于b的数的数量于大于b的数量相同
	}
	sum = 0; //再往右遍历，同时与左边比较
	for (int i = pos + 1; i <= n; i++) {
		sum += a[i];
		ans += s[n - sum]; //加上左边与其互补的数量
		if (!sum) ans++;
	}
	cout << ans << endl;
}

4. [hnoi2003]激光炸弹

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

typedef long long ll;
int n, r;
int g[5005][5005];

int main()
{
	cin >> n >> r;
	memset(g, 0, sizeof g);
	int xx = r, yy = r; //xx和yy表示边界，初始化为最小的r
	for (int i = 0; i < n; i++)
	{
		int x, y, v;
		cin >> x >> y >> v;
		g[x][y] = v;
		xx = max(xx, x); //记录输入的最大边
		yy = max(yy, y); 
	}

	for (int i = 1; i <= xx; i++){
		for (int j = 1; j <= yy; j++){
			g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + g[i][j];
		}
	}

	int ans = 0;
	for (int i = r; i <= xx; i++){
		for (int j = r; j <= yy; j++) {
			ans = max(ans, g[i][j] - g[i - r][j] - g[i][j - r] + g[i - r][j - r]);
		}
	}
	
	cout << ans << endl;
	return 0;
}

5. 二分

#include <iostream>
#include <map>
#include <limits.h>
using namespace std;

const int inf = int_max;//int型数据最大值，因为是对每个数进行统计

const int n = 1e7 + 10;
int a[n];
char s[n];
map<int, int> mp;

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i] >> s[i];
	for (int i = 1; i <= n; i++){
		if (s[i] == '.') mp[a[i]]++, mp[a[i] + 1]--;
		if (s[i] == '+') mp[a[i]]--, mp[-inf]++;
		if (s[i] == '-')mp[inf]--, mp[a[i] + 1]++;
	}

	int ans = -inf, h = 0;
	for (auto e : mp){
		h += e.second;
		ans = max(h, ans);
	}

	cout << ans << endl;
}

6. 货仓选址

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> a;
	for (int i = 0; i < n; i++){
		int x;
		cin >> x;
		a.push_back(x);
	}
	sort(a.begin(), a.end());
	int p = a[a.size() / 2];
	int ans = 0;
	for (int i = 0; i < n; i++) ans += abs(a[i] - p);
	cout << ans << endl;
	return 0;
}