欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

AGC015 C Nuske vs Phantom Thnook(前缀和)

程序员文章站 2022-04-19 15:34:14
题意 题目链接 给出一张$n \times m$的网格,其中$1$为蓝点,$2$为白点。 $Q$次询问,每次询问一个子矩阵内蓝点形成的联通块的数量 保证任意联通块内的任意蓝点之间均只有一条路径可达 Sol mdzz不好好读题目还想做题,。。 题目中说“联通块内的任意点都只有一条路径可达”,不难推断出 ......

题意

给出一张$n \times m$的网格,其中$1$为蓝点,$2$为白点。

$q$次询问,每次询问一个子矩阵内蓝点形成的联通块的数量

保证任意联通块内的任意蓝点之间均只有一条路径可达

sol

mdzz不好好读题目还想做题,。。

题目中说“联通块内的任意点都只有一条路径可达”,不难推断出这是一棵树

因此 联通块个数 = 蓝点的数量 - 蓝点间边的数量

考虑用前缀和维护,点的数量好处理,但是这个边的数量有点麻烦

反正我用一个数组是搞不出来,因为无法判断左右的方向。。

那就行列分别记录一下就可以了。

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long 
using namespace std;
const int maxn = 2001;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, q;
char s[maxn][maxn];
int p[maxn][maxn], r[maxn][maxn], l[maxn][maxn];
int getp(int x, int y) {
    if(x == 0 || y == 0) return 0;
    return p[x - 1][y] + p[x][y - 1] - p[x - 1][y - 1];
}
int getr(int x, int y) {
    if(x == 0 || y == 0) return 0;
    return r[x - 1][y] + r[x][y - 1] - r[x - 1][y - 1];
}
int getl(int x, int y) {
    if(x == 0 || y == 0) return 0;
    return l[x - 1][y] + l[x][y - 1] - l[x - 1][y - 1];
}
main() {
    n = read(); m = read(); q = read();
    for(int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= m; j++) {
            p[i][j] = getp(i, j);
            r[i][j] = getr(i, j);
            l[i][j] = getl(i, j);
            if(s[i][j] == '1') l[i][j] += (s[i - 1][j] == '1'),
                               r[i][j] += (s[i][j - 1] == '1'), 
                               p[i][j]++;
        }
    }
    /*for(int i = 1; i <= n; i++, puts(""))
        for(int j = 1; j <= m; j++)
            printf("%d ", l[i][j]);*/
    while(q--) {
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        // printf("%d %d %d %d\n", getp(x2, y2), getp(x1 - 1, y2), getp(x2, y1 - 1), getp(x1 - 1, y1 - 1));
        int ans1 = p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1];
        int ans2 = r[x2][y2] - r[x1 - 1][y2] - r[x2][y1] + r[x1 - 1][y1];
        int ans3 = l[x2][y2] - l[x2][y1 - 1] - l[x1][y2] + l[x1][y1 - 1];
        cout << ans1 - ans2 - ans3 << endl;
    }
    return 0;
}
/*
*/