【藍橋杯C組】備賽基礎篇之前綴和演算法

演算法介紹：

設a為數組，a[i]中儲存的是前i 個數（包括自己）的總和，相當於我們中學學過的前N項和，那麼，弄成這樣的好處是什麼呢？假如我們要多次訪問一段區間的總和，難道每次都加一次進行重複運算嗎？？？而我們的前綴和就可以解決這個問題，提前預處理，訪問到這段區間直接相減就得出了答案，避免了許多的重複運算。

基本程式碼解析：

#include<iostream>
using namespace std;

const int N = 100000 + 10;
int s[N], a[N];

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

    for (int i = 1;i <= n;i++) scanf("%d", &a[i]);
    for (int i = 1;i <= n;i++) s[i] = s[i - 1] + a[i];//保存前i項數之和。
    //這裡可以只用一個循環和一個數組，為了方便理解，我將他分開了。

    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
        //大段區域減小段區域，得到中間區域，l記得要-1，別把第l個數減去了。
    }
    return 0;
}

子矩陣和

那我們可不可以升級一下，解決二維的數組呢，當然是可以的，這時候我們s[i][j]的性質變了，變成了前   i、j  所有數的和，我們儲存和訪問的子矩陣的時候就要注意一下重複的部分了。

升級程式碼解析：

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

const int N = 1010;
int a[N][N], s[N][N];

int main() {
    int n, m, q, x1, x2, y1, y2;
    scanf("%d %d %d", &n, &m, &q);

    //可化為一次兩個循環，一個數組儲存，為方便理解，分開表示。
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            scanf("%d", &a[i][j]);
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    //可在紙上畫一個草圖，要得到s[i][j]，先加上a[i][j]，加上s[i - 1][j] 和 s[i][j - 1]所表示的區域，這時候，我們發現，有一段子矩陣重複了，再減去 s[i - 1][j - 1]便是我們的答案了。

    while (q--) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
        //要得到我們想要的子矩陣的數值，就要把旁邊的數給減去，也就是s[x1 - 1][y2] 和 s[x2][y1 - 1]所代表的區域，在草圖上我們發現又有重複的區域，也就多減了，所以我們把s[x1 - 1][y1 - 1]加上。
    }
    return 0;
}

 

Tags:

VirMach 便宜 VPS

QNews

QNews