数据是否过水?刚学OI的萌妹在线等神犇
查看原帖
数据是否过水?刚学OI的萌妹在线等神犇
629377
iamajcer楼主2024/7/22 11:20

我输入的时候把 nn 与 mm 的输入顺序互换,两次都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;
}
2024/7/22 11:20
加载中...