题意
Zxl 有一次决定制造一条项链, 她以非常便宜的价格买了一长条鲜艳的珊瑚珠子, 她现在也有一个机器, 能把这条珠子切成很多块 (子串), 每块有 k(k>0) 个珠子, 如果这条珠子的长度不是 k 的倍数, 最后一块小于 k 的就不要拉 (nc 真浪费), 保证珠子的长度为正整数. Zxl 喜欢多样的项链, 为她应该怎样选择数字 k 来尽可能得到更多的不同的子串感到好奇, 子串都是可以反转的, 换句话说, 子串(1,2,3) 和(3,2,1)是一样的. 写一个程序, 为 Zxl 决定最适合的 k 从而获得最多不同的子串. 例如: 这一串珠子是: (1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1), k=1 的时候, 我们得到 3 个不同的子串: (1),(2),(3) k=2 的时候, 我们得到 6 个不同的子串: (1,1),(1,2),(2,2),(3,3),(3,1),(2,3) k=3 的时候, 我们得到 5 个不同的子串: (1,1,1),(2,2,2),(3,3,3),(1,2,3),(3,1,2) k=4 的时候, 我们得到 5 个不同的子串: (1,1,1,2),(2,2,3,3),(3,1,2,3),(3,1,2,2),(1,3,3,2)
分析
参照 http://hzwer.com/6563.html 的题解.
枚举串长哈希暴力. 时间复杂度 \(O(n \ln n)\).
正反哈希相乘, 学习了.
代码
BZOJ 不支持 %llu 而只支持 %lu......
- #include<bits/stdc++.h>
- #define rg register
- #define il inline
- #define co const
- template<class T>il T read()
- {
- rg T data=0;
- rg int w=1;
- rg char ch=getchar();
- while(!isdigit(ch))
- {
- if(ch=='-')
- w=-1;
- ch=getchar();
- }
- while(isdigit(ch))
- {
- data=data*10+ch-'0';
- ch=getchar();
- }
- return data*w;
- }
- template<class T>il T read(rg T&x)
- {
- return x=read<T>();
- }
- using namespace std;
- typedef unsigned long long ll;
- co int N=1e6+10;
- co ll B=200191;
- ll mul[N],s1[N],s2[N];
- int n,mx;
- int a[N];
- set<ll>M;
- vector<int>k;
- ll gethash(int l,int r)
- {
- if(l<=r)
- return s1[r]-s1[l-1]*mul[r-l+1];
- else
- return s2[r]-s2[l+1]*mul[l-r+1];
- }
- void solve(int x)
- {
- if(mx*x>n) return;
- int ans=0;
- M.clear();
- for(int i=1;i<=n;i+=x)if(i+x-1<=n)
- {
- ll t=gethash(i,i+x-1)*gethash(i+x-1,i);
- if(M.find(t)!=M.end()) continue;
- ++ans;M.insert(t);
- }
- if(ans>mx)
- {
- mx=ans;
- k.clear();
- }
- if(ans==mx)
- k.push_back(x);
- }
- int main()
- {
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- read(n);
- for(int i=1;i<=n;++i)
- read(a[i]);
- mul[0]=1;
- for(int i=1;i<=n;++i)
- mul[i]=mul[i-1]*B;
- for(int i=1;i<=n;++i)
- s1[i]=s1[i-1]*B+a[i];
- for(int i=n;i>=1;--i)
- s2[i]=s2[i+1]*B+a[i];
- for(int i=1;i<=n;++i)
- solve(i);
- printf("%d %lu\n",mx,k.size()); // edit 1:only %lu available
- for(int i=0;i<k.size();++i)
- {
- printf("%d",k[i]);
- if(i<k.size()-1)
- printf(" ");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2935896.html