跳转至

前缀和-差分-二分

99 激光炸弹

二维前缀和公式

很简单, \(R \times R\) 的矩阵最多可以覆盖 \((R-1) \times (R-1)\) 的矩形地块

C++
 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
37
38
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010;

int s[N][N];

int main()
{
    int n, R;
    scanf("%d%d", &n, &R);
    R = min(R, 5001);

    for (int i = 0; i < n; i ++ )
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x ++, y ++ ;
        s[x][y] += w;
    }

    for (int i = 1; i <= 5001; i ++ )
        for (int j = 1; j <= 5001; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int res = 0;
    for (int i = R; i <= 5001; i ++ )
        for (int j = R; j <= 5001; j ++ )
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);

    printf("%d\n", res);

    return 0;
}

100 增减序列

差分数组

这题是纯思维题, 代码倒是很简单...

C++
 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
#include<iostream>
#include<algorithm>

using namespace std;

const int N  = 1e5+10;

int b[N],a[N];
long long pos,neg;

int main()
{
    int n;
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
        b[i] = a[i] - a[i-1];
    }
    for(int i = 2;i <= n;i++){
        if(b[i] > 0) pos += b[i];
        else  neg -=b[i];
    }
    cout<<min(pos,neg)+abs(pos-neg)<<endl;
    cout<<abs(pos-neg) + 1;

}

102 最佳牛围栏

实数二分模板

C++
 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
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, F;
double a[N], s[N];

bool check(double avg)
{
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i] - avg;

    double mins = 0;
    for (int k = F; k <= n; k ++ )
    {
        mins = min(mins, s[k - F]);
        if (s[k] >= mins) return true;
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &F);

    double l = 0, r = 0;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lf", &a[i]);
        r = max(r, a[i]);
    }

    while (r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%d\n", (int)(r * 1000));

    return 0;
}

113 特殊排序

C++
 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
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res(1, 1);
        for (int i = 2; i <= N; i ++ )
        {
            int l = 0, r = res.size() - 1;
            while (l < r)
            {
                // 注意: +1 还是 不+1 (二分的模板, 复习)
                int mid = l + r + 1 >> 1;
                if (compare(res[mid], i)) l = mid;
                else r = mid - 1;
            }

            res.push_back(i);
            for (int j = res.size() - 2; j > r; j -- ) swap(res[j], res[j + 1]);
            if (compare(i, res[r])) swap(res[r], res[r + 1]);
        }

        return res;
    }
};

vector初始化:

C++
1
2
3
vector<Type> array_name(element_num, element_init_value);
// vector<int> res(1, 1);     {1}
// vector<int> res(100, 1);   {1, 1, 1, 1, ..., 1} 100个1