区間と問題

22738 ワード
テキストリンク
これらの問題は実はそんなに難しくない.しかし、ほとんどが時間の制限を受けています.そのため、私たちに必要なのは直接解くのではなく、迅速に解くことです.

1 Dアレイ領域のマージ


arr=[1.2.3.4.5]
入力と同時に、すべての和を前の桁数に加算します.
ではsum=[1,3,6,10,15].
次に固定区間、例えば2~4、
sum[4]-sum[1]を作ればいい
2 + 3 + 4 = 9/10 - 1 = 9
典型的な問題は白駿11659号です.

11659回答

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

int n, m, val;
int a, b, sum;


int main() {
    cin >> n >> m;
    int arr[n+1];
    int sum[n+1];
    int ans[m];
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        sum[i] = sum[i - 1] + arr[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        int temp = sum[b] - sum[a-1];
        ans[i] = temp;
    }
    for(int i = 0; i < m; i++) {
        cout << ans[i] << "\n";
    }
    
}
何も説明する必要はないようです.

2 Dアレイ


2 D配列も1 Dと同じ方法で処理されますが、より複雑です.
これは時間を考慮せずに、直接問題を解決する方法です.

ちょくせつかいほう

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

struct point {
    int x1;
    int y1;
    int x2;
    int y2;
};

int n, m;
int arr[1025][1025];
vector <point> vec;

int main() {
    cin >> n >> m;
    int ans[m];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }
    int x1, y1, x2, y2;

    for (int i = 0; i < m; i++) {
        point p1;
        cin >> p1.x1>> p1.y1 >> p1.x2 >> p1.y2;
        vec.push_back(p1);
    }
    for (int i = 0; i < m; i++) {
        int sum = 0;
        x1 = vec[i].x1;
        y1 = vec[i].y1;
        x2 = vec[i].x2;
        y2 = vec[i].y2;

        for (int x = x1; x <= x2; x++) {
            for (int y = y1; y <= y2; y++) {
                sum += arr[x][y];
            }
        }
        ans[i] = sum;
    }
    
    for(int elem : ans) {
        cout << elem << "\n";
    }
}

O(1)時間以内の放出

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

int n, m;
int arr[1025][1025];

int main() {
    cin >> n >> m;
    int ans[m];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] += arr[i-1][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] += arr[i][j-1];
        }
    }
    int x1, y1, x2, y2;

    for (int i = 0; i < m; i++) {
        int sum = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        sum = arr[x2][y2]-arr[x1-1][y2]-arr[x2][y1-1]+arr[x1-1][y1-1];
        ans[i] = sum;
    }
    for (int elem : ans) cout << elem << "\n";
}
二次元配列なので、区間和を求めるときは、x軸、y軸ともに注意して合わせます.
そして最後に車を救う時もx-1,y-1を外します.このときx-1,y-1は2回重なってしまうので加算します.
第11週プロジェクト4-ファミリーの設計
明日学習キャンプ2日目開発ログ