TOI 練習賽 202404 潛力組

發布於 分類於 閱讀次數： 文章字數： 243 所需閱讀時間 ≈ 1 分鐘

說明

這次 TOIP 第一題考到了差分的概念，並運用在二維陣列裡。第二、三題都在考 DP 的運用。

解題

1. 降雨量統計（Rainfall）

展開程式碼

 
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
#include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;

int main() {
    ouo;
    int r, c;
    cin >> r >> c;
    int g[r + 1][c + 1];
    memset(g, 0, sizeof(g));
    int q;
    cin >> q;
    int arr[5];

    // 做差分陣列
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < 5; j++) cin >> arr[j];

        g[arr[0]][arr[1]] += arr[4];
        g[arr[0]][arr[3]] -= arr[4];
        g[arr[2]][arr[1]] -= arr[4];
        g[arr[2]][arr[3]] += arr[4];
    }

    // 先輸出第一行
    int presum = 0;
    for (int i = 0; i < c; i++) {
        presum += g[0][i];
        g[0][i] = presum;
        cout << g[0][i] << ' ';
    }
    cout << '\n';

    // 處理後續前綴
    for (int i = 1; i < r; i++) {
        presum = 0;
        for (int j = 0; j < c; j++) {
            presum += g[i][j];
            g[i][j] = presum + g[i - 1][j];
            cout << g[i][j] << ' ';
        }
        cout << '\n';
    }
}

2. 切割板材（Plate）

尚未解題

3. 搭船渡河 （Boat）

尚未解題