洛谷/USACO 家的范围 Home on the Range

洛谷题号:P2733
思路很简单,我是参考洛谷 最大正方形这道题来写的,都是二维前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n;
int arr[260][260];
int sum[260][260];
int cow[260];
inline int getSquareSum(int x, int y, int e){
    x--; y--;
    return sum[x + e][y + e] - sum[x + e][y] - sum[x][y + e] + sum[x][y];
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            scanf("%1d", &arr[i][j]);
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
        }
    }
    cow[1] = 1;
    for (int e = 2; e <= 250 && cow[e - 1] > 0; e++){
        for (int x = 1; x <= n - e + 1; x++){
            for (int y = 1; y <= n - e + 1; y++){
                if (getSquareSum(x, y, e) == e*e)
                    cow[e]++;
            }
        }
    }
    for (int i = 2; i <= 250 && cow[i] > 0; i++){
        printf("%d %d\n", i, cow[i]);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注