训练的时候一看题目长的一批就根本没看，现在看看发现还是可做的啊。。
题目简述
给定一个n*n的矩阵，q次询问，每次给定一个矩形范围，问一个最小矩阵的面积，可以通过此矩阵循环覆盖给定的范围，多出的部分可以不计
例如:ababa可以通过ab循环构成
思路
如果一个子矩阵满足条件，把这玩意纵向扩展后肯定也可以满足条件，那么我们求可以横向循环满足的循环节和纵向的循环节长度，乘一下就行。
用hash把这玩意压成一维，在找循环节就行了。
这个就是找最长公共前后缀长度d，那么n-d就是循环节长度。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<iostream>
#include<stdio.h>
#include<cstring>
#include<vector>
#include<math.h>
#include<algorithm>
#include <stdio.h>
#include <queue>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 5e5+ 5;
const ll mod = 1e9 + 7;
ull p1 = 131;
ull p2 = 20111203;
char dat[3000][3000];
ull h1[3000][3000], h2[3000][3000],pp1[3000],pp2[3000];
ll q;
ull r[3000], c[3000];
int main() {
ll n,q;
cin >> n >> q;
for (int i = 1; i <=n; i++)cin >> dat[i]+1;
pp1[0] = pp2[0] = 1;
for (int i = 1; i <= n; i++) {
pp1[i] = pp1[i - 1] * p1;
pp2[i] = pp2[i - 1] * p2;
}
for (int i = 1; i <=n; i++) {
for (int j = 1; j <= n; j++) {
h1[i][j] = h1[i - 1][j] * p1 + dat[i][j] - 'a';
h2[i][j] = h2[i][j-1] * p1 + dat[i][j] - 'a';
}
}
while (q--) {
ll x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int i = y1; i <= y2; i++)r[i] = h1[x2][i] - h1[x1 - 1][i] * pp1[x2 - x1 + 1];
for (int i = x1; i <= x2; i++)c[i] = h2[i][y2] - h2[i][y1-1] * pp1[y2 - y1 + 1];
ull s1 = 0, s2 = 0;
ll ans1 = -1, ans2 = -1;
for (int i = 0; i+y1<y2; i++) {
s1 = s1 * p2 + r[i+y1];
s2 = s2 + r[y2 - i]*pp2[i];
if (s1 == s2)ans1 = i;
}
ans1 = y2 - y1 - ans1;
s1 = s2 = 0;
for (int i = 0; i + x1 < x2; i++) {
s1 = s1 * p2 + c[i + x1];
s2 = s2 + c[x2 - i] * pp2[i];
if (s1 == s2)ans2 = i;
}
ans2 = x2 - x1 - ans2;
cout << ans2 * ans1 << '\n';
}
}
|
这里考虑一下如果d==n的时候，其实答案是n而不是n-d，把ans预设为-1可以很巧妙的解决。
结果写的时候天天犯病，对题解抄都nm能给抄歪来，hash也迷惑冲突，只能说base不能乱设了呃呃。
