我输入的时候把 n 与 m 的输入顺序互换,两次都AC了
另外有一个小问题,就是每篇题解中,关于小矩阵,每次处理时没清除数据,我认为是要的,这是为什么?例下段代码的前两行:
bh[1][0]=0;
bh2[0][1]=0;
for (int i=1; i<=n2; i++)
for (int j=1; j<=m2; j++)
bh[i][j]=bh[i][j-1]*base+(b[i][j]=='1');
for (int i=1; i<=n2; i++)
for (int j=1; j<=m2; j++)
bh2[i][j]=bh2[i-1][j]*base2+bh[i][j];
这题我要开O2才能过,大佬能否帮蒟蒻看看哪儿可以优化?感激不尽!
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
typedef unsigned long long ull;
ull base=131, base2=1331;
char a[N][N], b[N][N];
ull ah[N][N], ah2[N][N], bh[N][N], bh2[N][N], p[N], p2[N];
int n, m, n2, m2, q;
map<ull, bool> mp;
ull js(int x, int y, int x2, int y2)
{
return ah2[x2][y2]-(ah2[x-1][y2]*p2[x2-x+1])-(ah2[x2][y-1]*p[y2-y+1])+(ah2[x-1][y-1]*p2[x2-x+1]*p[y2-y+1]);
}
int main()
{
scanf("%d%d%d%d", &n, &m, &n2, &m2);
for (int i=1; i<=n; i++)
scanf("%s", a[i]+1);
p[0]=p2[0]=1;
for (int i=1; i<=max(n, m); i++) p[i]=p[i-1]*base, p2[i]=p2[i-1]*base2;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
ah[i][j]=ah[i][j-1]*base+(a[i][j]=='1');
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
ah2[i][j]=ah2[i-1][j]*base2+ah[i][j];
for (int i=n2; i<=n; i++)
for (int j=m2; j<=m; j++)
mp[js(i-n2+1, j-m2+1, i, j)]=1;
scanf("%d", &q);
while (q--)
{
for (int i=1; i<=n2; i++)
scanf("%s", b[i]+1);
bh[1][0]=0;
bh2[0][1]=0;
for (int i=1; i<=n2; i++)
for (int j=1; j<=m2; j++)
bh[i][j]=bh[i][j-1]*base+(b[i][j]=='1');
for (int i=1; i<=n2; i++)
for (int j=1; j<=m2; j++)
bh2[i][j]=bh2[i-1][j]*base2+bh[i][j];
if (mp[bh2[n2][m2]]) printf("1\n");
else printf("0\n");
}
return 0;
}