[Aug4] Deviation

哈希写挂…


题意

给定两个序列A,B,求A的所有连续子序列a满足:

  • a和B等长。
  • a和B对应位上的差相等。

思路

满足的连续子序列的差分序列和B的差分序列一样。所以Hash一下就可以了。

(写了双哈希)

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <set>
#include <vector>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
typedef long long LL;
const int N = 100010,inf = 0x3f3f3f3f;
int A[N],B[N],a[N],b[N],n,m,T;
const LL bs[2] = {105137, 233}, mod[2] = {1000000787, 1000000241};
LL po[2][N];
LL hs[2][N],bhs[2];
inline LL gethash(int l,int r,int k){return (hs[k][r] - 1LL * hs[k][l - 1] * po[k][r - l + 1] % mod[k] + mod[k]) % mod[k];}
std::set<int> khs;
std::vector<int> V;
int main()
{
po[0][0] = 1;po[1][0] = 1;
for(int i = 1;i < N;i++) po[0][i] = 1LL * po[0][i - 1] * bs[0] % mod[0];
for(int i = 1;i < N;i++) po[1][i] = 1LL * po[1][i - 1] * bs[1] % mod[1];
T = getint();while(T--)
{
khs.clear();
n = getint();for(int i = 1;i <= n;i++) A[i] = getint();
m = getint();for(int i = 1;i <= m;i++) B[i] = getint();
if(m == 1)
{
int ret = inf,kk;
for(int i = 1;i <= n;i++)
{
kk = B[1] - A[i];
if(!khs.count(kk)) khs.insert(kk);
ret = std::min(ret,std::abs(kk));
}
printf("%d %d %d %d %d\n",khs.size(),ret == inf ? 0 : ret,n,1,n);
continue;
}
V.clear();
for(int i = 1;i < n;i++) V.push_back(A[i + 1] - A[i]);
for(int i = 1;i < m;i++) V.push_back(B[i + 1] - B[i]);
std::sort(V.begin(),V.end());
for(int i = 1;i < n;i++) a[i] = std::lower_bound(V.begin(),V.end(),A[i + 1] - A[i]) - V.begin();
for(int i = 1;i < m;i++) b[i] = std::lower_bound(V.begin(),V.end(),B[i + 1] - B[i]) - V.begin();
int f1 = 0,f2 = 0,f3 = 0,f4 = 0,f5 = 0;
bhs[0] = bhs[1] = 0LL;
for(int i = 1;i < m;i++) bhs[0] = (1LL * bhs[0] * bs[0] + b[i]) % mod[0];
for(int i = 1;i < m;i++) bhs[1] = (1LL * bhs[1] * bs[1] + b[i]) % mod[1];
hs[0][0] = hs[1][0] = 0LL;
for(int i = 1;i < n;i++) hs[0][i] = (1LL * hs[0][i - 1] * bs[0] + a[i]) % mod[0];
for(int i = 1;i < n;i++) hs[1][i] = (1LL * hs[1][i - 1] * bs[1] + a[i]) % mod[1];
for(int l = 1;l + m - 2 < n;l++)
{
int r = l + m - 2;
LL ahs0 = gethash(l,r,0),ahs1 = gethash(l,r,1);
if(ahs0 == bhs[0] && ahs1 == bhs[1])
{
int nowk = B[1] - A[l];
if(!f1)
{
f1 = 1;
f2 = std::abs(nowk);
f3 = 1;f4 = l;f5 = l;
khs.insert(nowk);
}
else
{
if(!khs.count(nowk))
{
f2 = std::min(f2,std::abs(nowk));
khs.insert(nowk);
}
f3++;
f4 = std::min(f4,l);
f5 = std::max(f5,l);
}
}
}
printf("%d %d %d %d %d\n",khs.size(),f2,f3,f4,f5);
}
return 0;
}