【BZOJ 2351】 Matrix

【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=2351

【算法】

哈希

【代码】

#include<bits/stdc++.h>

using namespace std;

#define MAXN 1010

typedef unsigned long long ull;

const int base1 = ;

const int base2 = ;

const int P = 1e5 + ;

int i,j,m,n,a,b,q;

ull sum[MAXN][MAXN];

ull power1[MAXN],power2[MAXN];

ull t;

vector< ull > e[P];

char c;

char s[MAXN][MAXN];

inline void insert(ull x)

{

        int h = (int)(x % P);

        e[h].push_back(x);

}

inline bool query(ull x)

{

        int i;

        int h = (int)(x % P);

        for (i = ; i < (int)e[h].size(); i++)

        {

                if (e[h][i] == x)

                        return true;

        }

        return false;

}

int main()

{

        scanf("%d%d%d%d",&m,&n,&a,&b);

        for (i = ; i <= m; i++) scanf("%s",s[i]+);

        for (i = ; i <= m; i++)

        {

                for (j = ; j <= n; j++)

                {

                        sum[i][j] = s[i][j] - '';

                }

        }

        for (i = ; i <= m; i++)

        {

                for (j = ; j <= n; j++)

                {

                        sum[i][j] += sum[i-][j] * base1;

                }

        }

        for (i = ; i <= m; i++)

        {

                for (j = ; j <= n; j++)

                {

                        sum[i][j] += sum[i][j-] * base2;

                }

        }

        power1[] = power2[] = ;

        for (i = ; i < m; i++)

        {

                power1[i] = power1[i-] * base1;

                power2[i] = power2[i-] * base2;

        }

        for (i = a; i <= m; i++)

        {

                for (j = b; j <= n; j++)

                {

                        t = sum[i][j] - sum[i-a][j] * power1[a] - sum[i][j-b] * power2[b] + sum[i-a][j-b] * power1[a] * power2[b];

                        insert(t);

                }

        }

        scanf("%d",&q);

        while (q--)

        {

                for (i = ; i <= a; i++) scanf("%s",s[i]+);

                for (i = ; i <= a; i++)

                {

                        for (j = ; j <= b; j++)

                        {

                                sum[i][j] = s[i][j] - '';

                        }

                }

                for (i = ; i <= a; i++)

                {

                        for (j = ; j <= b; j++)

                        {

                                sum[i][j] += sum[i-][j] * base1;

                        }

                }

                for (i = ; i <= a; i++)

                {

                        for (j = ; j <= b; j++)

                        {

                                sum[i][j] += sum[i][j-] * base2;

                        }

                }

                if (query(sum[a][b])) printf("1\n");

                else printf("0\n");

        }

        return ;

}