二維字首和 - 算法學習 - 輸入輸出優化

2017-08-27 11:11:38

writer：pprp

二維字首和主要用到了容斥定理，具體實作還是有點複雜的

詳見代碼：

/*
@theme:二維字首和
@writer:pprp
@declare:用到容斥定理
@date:2017/8/27
*/

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1010;

int n, m, a[maxn][maxn];

//輸入優化
inline int read()
{
    int X=0,w=1;
    char ch=0;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}

inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int main()
{
    freopen("in.txt","r",stdin);
    n = read();
    m = read();
    a[0][0] = read();

    //前n向子矩陣和的求法
    for(int i = 1; i < n ; i++)
    {
        a[0][i] = read();
        a[0][i] += a[0][i-1];
    }
    //這段的實作比較複雜
    for(int i = 1; i < n ; i++)
    {
        a[i][0] = read();
        a[i][0] += a[i-1][0];
        for(int j = 1; j < n ; j++)
        {
            a[i][j] = read();
            //容斥原理
            a[i][j] = a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        }
    }

    for(int i = 0 ; i < m ; i++)
    {
        int x, y, x1, y1;
        x = read();
        y = read();
        x1 = read();
        y1 = read();
        //write(a[x1-1][y1-1]-a[x-2][y1-1]-a[x1-1][y-2]+a[x-2][y-2]);
        //如果這樣寫就有問題了，因為如果考慮邊界情況，在x = 1||y = 1的時候，會減去a[x1-1][-1]，減去不存在的數
        //是以需要判斷四種情況
        if(x==1 && y==1)
        {
            write(a[x1-1][y1-1]);
        }
        else if(x==1)
        {
            write(a[x1-1][y1-1]-a[x1-1][y-2]);
        }
        else if(y==1)
        {
            write(a[x1-1][y1-1]-a[x-2][y1-1]);
        }
        else
        {
            write(a[x1-1][y1-1]-a[x-2][y1-1]-a[x1-1][y-2]+a[x-2][y-2]);//輸出結果，單次O(1)，總共O(m)
        }
        putchar('\n');
    }
    return 0;
}      

代碼改變世界