laekov

BZOJ2351/2462 [BeiJing2011]Matrix

好像要用二维AC自动机的样子!?不对,还要优化不然还会MLE!?


naive。


哈希水过之。


中途某处忘强转导致调了良久。


2462丧心病狂卡stl常数,差点写平衡树了,然后想了想二分水之。


#include <cstdio>

#include <cstring>

#include <set>

#include <algorithm>


using namespace std;


typedef long long qw;

typedef unsigned long long uqw;


#define _l (qw)


const int rmod = 345379;

const int b1 = 3;

const int b2 = 3153131;

const int maxn = 1009;


int pb1[maxn];

int n, m, x, y, q, hr[maxn][maxn], t;

uqw hl[maxn][maxn], pb2[maxn];

char g[maxn];

uqw th[maxn * maxn];


void pre() {

pb1[0] = 1;

pb2[0] = 1;

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

pb1[i] = _l pb1[i - 1] * b1 % rmod;

pb2[i] = pb2[i - 1] * b2;

}

}


bool findv(uqw x) {

int l = 0, r = t - 1;

while (l < r) {

int mid = (l + r) >> 1;

if (th[mid] == x)

return 1;

else if (x < th[mid])

r = mid;

else

l = mid + 1;

}

return th[l] == x;

}


int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif


pre();

scanf("%d%d%d%d", &n, &m, &x, &y);

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

scanf("%s", g + 1);

hr[i][0] = 0;

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

hr[i][j] = (_l hr[i][j - 1] * b1 + g[j] - 48) % rmod;

for (int j = m; j >= y; -- j)

hr[i][j] = (_l hr[i][j] - _l hr[i][j - y] * pb1[y] % rmod + rmod) % rmod;

}

t = 0;

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

hl[0][j] = 0;

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

hl[i][j] = hl[i - 1][j] * b2 + hr[i][j];

for (int i = n; i >= x; -- i) {

hl[i][j] = hl[i][j] - hl[i - x][j] * pb2[x];

th[t ++] = hl[i][j];

}

}

sort(th, th + t);

scanf("%d", &q);

while (q --) {

uqw hv = 0;

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

int hh = 0;

scanf("%s", g + 1);

for (int j = 1; j <= y; ++ j)

hh = (_l hh * b1 + g[j] - 48) % rmod;

hv =  hv * b2 + hh;

}

if (findv(hv))

puts("1");

else

puts("0");

}

}


评论

© laekov | Powered by LOFTER