Atcoder C - Nuske vs Phantom Thnook（递推+思维）

题目链接：http://agc015.contest.atcoder.jp/tasks/agc015_c

题意：给一个n*m的格，蓝色的组成路径保证不成环，q个询问，计算指定矩形区域内蓝色连通块的个数

题解：由于只有两种颜色所以求蓝色连通块就简单多了，连通块要么直接dfs一遍显然会超时，主要是询问有20000个。

但是求连通块也可以用总的个数减去连通的边数（主要是只有一种类型的连通块），直接存边不好处理不妨存一下横着连通的边数和竖着连通的边数，这样

就好处理很多了。

#include <iostream>

#include <cstring>

using namespace std;

const int M = 2e3 + 10;

int dprow[M][M] , dpcow[M][M] , a[M][M] , sum[M][M];

char mmp[M][M];

int main() {

    int n , m , q;

    cin >> n >> m >> q;

    memset(dprow , 0 , sizeof(dprow));

    memset(dpcow , 0 , sizeof(dpcow));

    memset(a , 0 , sizeof(a));

    memset(sum , 0 , sizeof(sum));

    for(int i = 1 ; i <= n ; i++) {

        cin >> mmp[i];

    }

    for(int i = 1 ; i <= n ; i++) {

        for(int j = 1 ; j <= m ; j++) {

            a[i][j] = mmp[i][j - 1] - '0';

        }

    }

    for(int i = 1 ; i <= n ; i++) {

        for(int j = 1 ; j <= m ; j++) {

            sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

            dpcow[i][j] = dpcow[i - 1][j] + dpcow[i][j - 1] - dpcow[i - 1][j - 1];

            dprow[i][j] = dprow[i - 1][j] + dprow[i][j - 1] - dprow[i - 1][j - 1];

            if(a[i][j] == 1) {

                if(a[i - 1][j] == 1) dpcow[i][j]++;

                if(a[i][j - 1] == 1) dprow[i][j]++;

            }

        }

    }

    while(q--) {

        int x1 , y1 , x2 , y2;

        cin >> x1 >> y1 >> x2 >> y2;

        int ans = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];

        ans -= (dpcow[x2][y2] - dpcow[x1][y2] - dpcow[x2][y1 - 1] + dpcow[x1][y1 - 1]);

        ans -= (dprow[x2][y2] - dprow[x2][y1] - dprow[x1 - 1][y2] + dprow[x1 - 1][y1]);

        cout << ans << endl;

    }

    return 0;

}

巴特西

Atcoder C - Nuske vs Phantom Thnook（递推+思维）

最新文章

热门文章