soj4554 Boring Game HASH

题目

给你一个N*M的矩阵,($a_{ij} \leq NM$)接下来有$1e5$次询问,$x_1,y_1,x_2,y_2$分别为子矩阵左上右下的点,问这个子矩阵中是否$1到size(子矩阵)$这些数都在这个矩阵中出现一次.

题解

我们可以采用hash的方法.

首先hash要满足可计算.

我们如果知道子矩阵的size,那么这个子矩阵中 所有数的和,所有数的平方的和,所有数立方的和等等信息,都可以知道了.那么我们需要先预处理一下原来矩阵中的信息.

记$sum[k][i][j]$为[1,i]*[1,j]矩阵中,每个数的k次方的和.那么有

预处理:

• $sum[k][i][j]=sum[k][i-1][j]+sum[k][i][j-1]-sum[k][i-1][j-1]+a[k][i][j]$

询问:

• $sum[k][x_1..x_2][y_1..y_2]=sum[k][x_2][y_2]+sum[k][x_1-1][y_1-1]-sum[x_1-1][y_1]-sum[x_2][y_1-1]$

这个题开始我hash了5次,但其实只要hash一次,hash一个数的三次方就行了.

代码:

#include <stdio.h>
typedef unsigned int uint;
const int maxn = 1010;
uint f[maxn][maxn], g[maxn * maxn];
int main(){
    for(uint i = 1; i <= 1000000; i++)
        g[i] = g[i-1] + i * i * i;
    int n, m;
    while(scanf("%d%d", &n, &m) == 2){
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                scanf("%u", &f[i][j]);
                f[i][j] = f[i][j] * f[i][j] * f[i][j] + f[i-1][j] + f[i][j-1] - f[i-1][j-1];
            }
        int q; scanf("%d", &q);
        for(int k = 0; k < q; k++){
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            uint val = f[x2][y2] - f[x1-1][y2] - f[x2][y1-1] + f[x1-1][y1-1];
            printf("%s\n", val == g[(x2-x1+1)*(y2-y1+1)] ? "YES" : "NO");
        }

    }
    return 0;   
}