算法竞赛进阶指南-0x03基本算法-前缀和与差分

激光炸弹

题意:
一个矩阵上有许多点,每个点有权值,问用R * R的正方形覆盖,最大权值是多少。

Solution:
二维前缀和预处理,枚举R找最大值。

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int n, x, y, w, r;
int mx, my;
int s[5005][5005];

int main()
{
    __;
    cin >> n >> r;
    mx = r, my = r;
    for(int i = 1; i <= n; i ++){
        cin >> x >> y >> w;
        x ++;
        y ++;
        mx = max(x, mx), my = max(my, y);
        s[x][y] += w;
    }

    for(int i = 1; i <= mx; i ++){
        for(int j = 1; j <= my; j ++){
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
        }
    }

    int ans = 0;
    for(int i = r; i <= mx; i ++){
        for(int j = r; j <= my; j ++){
            ans = max(ans, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
        }
    }

    printf("%d\n", ans);
    return 0;
}

IncDec序列

题意:
给定一个序列,每次选择一个区间加一或减一,问求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。

Solution:
求出差分数组 b
那么题目就转化为,将b_2...b_n变成 0,即原数组相同,最后得到的序列,就是这 nb_1

选取 b_ib_j2<=i,j<=n, 而且这两个数,一个为正数,一个为负数,至于为什么要是正负配对,因为我们是要这个 b 序列 2-n 都要为 0,所以这样负数增加,正数减少,就可以最快地到达目标为0的状态。

最后无法配对的数 b_i 可以选 b_1 或者 b_{n+1},这两个不影响的数,进行修改。

pb 序列中正数之和,qb 序列中负数之和

最小的操作次数 = max(p, q)
数列可能的种数 = abs(p - q) + 1

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)


int n;
ll a[N], b[N];


int main(){
    __;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    ll p = 0, q = 0;
    for(int i = 2; i <= n; i ++){
        b[i] = a[i] - a[i - 1];
        if(b[i] > 0)    p += b[i];
        else    q -= b[i];
    }
    printf("%lld\n%lld\n", max(p, q), abs(p - q) + 1);
    return 0;
}

最高的牛

题意:
N 头牛站成一行,被编队为 1、2、3…N
当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。
现在,我们只知道其中最高的牛是第 P 头,它的身高是 H ,剩余牛的身高未知。
但是,我们还知道这群牛之中存在着 M 对关系,每对关系都指明了某两头牛 AB 可以相互看见。
求每头牛的身高的最大可能值是多少。

Solution:

如果 AB 可以互相看见说明他俩中的牛身高至少比它们少 1 ,那么我们可以设置一个 D 数组, D[P] = 0,
D[a + 1] --, D[b] ++ \ (a<b), 然后从左到右前缀和,就可以求出矮多少。
最后每头牛的身高还要加上初始值 H

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)


int n, p, h, m;
map<P, int> mp;
int c[N], d[N];

int main(){
    __;
    cin >> n >> p >> h >> m;
    while(m --){
        int a, b;
        cin >> a >> b;
        if(a > b)   swap(a, b);
        if(mp[{a, b}])  continue;
        mp[{a, b}] = 1;
        d[a + 1] --, d[b] ++;
    }
    for(int i = 1; i <= n; i ++){
        c[i] = c[i - 1] + d[i];
        printf("%d\n", c[i] + h);
    }

    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注