浙工大校赛-puzzle-Hash
Primo Pan
  2022-03-22 19:41:05 2022-03-22 19:41    

题目大意

给三个长度为n(1<=n<=100 000)的数组A,B,C。可以将A数组或者B数组左移，每次移动记一次操作，问最少多少次操作可以使得Ai+Bi=Ci，否则扣-1。

题解

比赛的时候脑子抽了...推了一个非充要条件，然后看有点假，想想会不会是字符串相关的题，然后去做核酸了。

后来发现很假，直接环形哈希就完事儿了。带上map复杂度是的。 

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//This amazing code is written by Primo.Jay.Pan From CUC

//Any questions please contact me
//QQ:898021802
//Mail: primojpan@gmail.com
//.    primojaypan@cuc.edu.cn


// Untitled 3.txt
// Created by Primo Jay Pan on 2022/3/22.
//While (true) RP++;


//head
#include <iostream>
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <csignal>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
#define maxlongint 2147483647
#define maxint 32767
#define pi(double)acos(-1.0)
#define eps 1e-9
#define MID ((l+r)>>1)
#define lson (o<<1)
#define rson (o<<1|1)
//clear the array
#define cla(a) memset(a,0,sizeof(a))
#define clb(a) memset(a,INF,sizeof(a))
#define clc(a) memset(a,-1,sizeof(a))




using namespace std;

const ull mod=998244353;
const int maxn =100010;
 

ull A[maxn],B[maxn],C[maxn],base[maxn];
map<ull , int > MP;
int n;

inline void init()
{
	base[0]=1;
	for (int i=1;i<=n;i++)
		base[i]=base[i-1]*mod;
	
}
int ans=mod;

//main
int main()
{
	//freopen("Untitled 3.txt.in","r",stdin);
	//freopen("Untitled 3.txt.out","w",stdout);
	cin>>n;
	init();
	for (int i=1;i<=n;i++)
	{
		cin>>A[i];
		A[i]=A[i-1]*mod+A[i];
	}
	for (int i=1;i<=n;i++)
	{
		cin>>B[i];
		B[i]=B[i-1]*mod+B[i];
	}
	for (int i=1;i<=n;i++)
		{
			cin>>C[i];
			C[i]=C[i-1]*mod+C[i];
		}
	for (int i=0;i<n;i++)
	{
		ull cur=(A[n]-A[i]*base[n-i])*base[i]+A[i];
		MP[cur]=i;//A左移动i位
	}
	for (int i=0;i<n;i++)
	{
		ull cur=(B[n]-B[i]*base[n-i])*base[i]+B[i];//B左移动n位
		if (MP.count(C[n]-cur))
			ans=min(ans,MP[C[n]-cur]+i);
		
	}
	cout<<((ans==mod)?-1:ans)<<endl;
	return 0;
}



/*
Test Data1:
Test Data2:
*/