https://codeforces.com/gym/100500/
$n^3$暴力显然超时,考虑优化
我们考虑题目的特殊性质,
显然,最终的序列我们可以直接通过总和得到
记为$ans$序列
那么,我们考虑另外一个方向的暴力
固定$arr_1$,枚举$arr_2$的循环同构$loop_k(arr2)$,相加得到$n$个不同的序列$A_i$
固定$arr_3$,枚举$arr_4$的循环同构$loop_k(arr4)$,相加得到$n$个不同的序列$B_i$
再固定每一个$A_i$,枚举$B_j$的每一个$loop_k(B_j)$
看这$2n$个序列两两配对能否凑出最终序列
此时复杂度达到了$n^4$
即,枚举$i,j,k$最后线性判断
我们考虑优化
假设答案的为$i,j,k$且序列长度为$n$
即,$A_i$与$loop_k(B_j)$相加,可以得到$ans$
换句话说,如果我们把$ans$和$loop_k(B_j)$相减,可以得到$A_i$的某一个循环同构
此时,我们就可以同时得到2个优化
1.使用多项式哈希,把所有$A_i$放入哈希表中,
直接枚举$j$即可,此时复杂度为$n^3*hashmap$
2.由于$ans$和$loop_k(B_j)$相减,可以得到$A_i$
又因为$ans$的每一个循环同构都相等,因此我们换一下枚举的顺序
即$ans$和$B_j$相减,可以得到$loop_x(A_i)$,x为未知数
此时利用$Rabbin-Karp$的思想,枚举他的循环同构哈希值,就可以$n^2*hashmap$的解决问题了
在这里也提供另外一个方法:
如果我们把每一个$A_i$都变成它的最小表示$minrep(A_i)$,再放入哈希表
同时,把$ans$和$B_j$相减得到的$loop_x(A_i)$也变为它的最小表示$minrep(loop_x(A_i))$
由于$minrep(A_i)$恒等于$minrep(loop_x(A_i))$
然后我们也可以直接通过哈希值快速判断了
复杂度也为$n^2*hashmap$
#include<bits/stdc++.h> #define rep(ii,a,b) for(int ii=a;ii<=b;++ii) #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define ull unsigned long long using namespace std;//head const int maxn=1e3+10,maxm=2e6+10; int casn,n,m,k; int a[5][maxn]; int minrep(int *s,int n){ int i=0,j=1,k=0,t; while(i<n&&j<n&&k<n){ t=s[i+k>=n?i+k-n:i+k]-s[j+k>=n?j+k-n:j+k]; if(!t) ++k; else { if(t>0) i+=k+1; else j+=k+1; if(i==j) ++j; k=0; } } return min(i,j); } int id[maxn*2+10]; const ull base=1e9+7; int b[maxn]; ull gethash(int *s,int n){ int pos=minrep(s,n); ull res=0; rep(i,0,n-1) res=res*base+s[id[pos+i]]; return res; } unordered_set<ull> vis; ull ans; bool check(int i){ rep(j,0,n-1)b[j]=ans-a[3][j]-a[4][id[j+i]]; return vis.count(gethash(b,n)); } int main() {IO; cin>>casn; int kase=0; while(casn--){ cin>>n; ull sum=0; rep(i,1,4){ rep(j,0,n-1){ cin>>a[i][j]; sum+=a[i][j]; } } if(sum%n){ cout<<"Case "<<++kase<<": No\n"; continue; } vis.clear(); ans=sum/n; rep(i,0,2*n) id[i]=i%n; rep(i,0,n-1){ rep(j,0,n-1) b[j]=a[1][j]+a[2][id[i+j]]; vis.insert(gethash(b,n)); } bool flag=0; rep(i,0,n-1){ if(check(i)) { flag=1; break; } } if(flag)cout<<"Case "<<++kase<<": Yes\n"; else cout<<"Case "<<++kase<<": No\n"; } }