Description
Sandy 和 Sue 的热衷于收集干脆面中的卡片然而, Sue 收集卡片是因为卡片上漂亮的人物形象, 而 Sandy 则是为了积
攒卡片兑换超炫的人物模型每一张卡片都由一些数字进行标记, 第 i 张卡片的序列长度为 Mi, 要想兑换人物模型
, 首先必须要集够 N 张卡片, 对于这 N 张卡片, 如果他们都有一个相同的子串长度为 k, 则可以兑换一个等级为 k 的人
物模型相同的定义为: 两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串 Sandy 的卡片数远
远小于要求的 N, 于是 Sue 决定在 Sandy 的生日将自己的卡片送给 Sandy, 在 Sue 的帮助下, Sandy 终于集够了 N 张卡片
, 但是, Sandy 并不清楚他可以兑换到哪个等级的人物模型, 现在, 请你帮助 Sandy 和 Sue, 看看他们最高能够得到
哪个等级的人物模型
Input
第一行为一个数 N, 表示可以兑换人物模型最少需要的卡片数, 即 Sandy 现在有的卡片数
第 i+1 行到第 i+N 行每行第一个数为第 i 张卡片序列的长度 Mi, 之后 j+1 到 j+1+Mi 个数, 用空格分隔, 分别表示序列中
的第 j 个数
- n<=1000,M<=1000,2<=Mi<=101
- Output
一个数 k, 表示可以获得的最高等级
- Sample Input
- 2
- 2 1 2
- 3 4 5 9
- Sample Output
- 2
罕见的抄了一发题解毕竟 NOI 原题哪有那么容易写出来的道理
并没有什么罕见的算法, 不过思路还是很巧妙的
一开始我的想法是用单调栈, 而且好像的确有这种算法的 std, 不过我乱搞了一下午样例都没过于是只好作罢
改为大众并查集做法
首先很容易发现, 对于任意一对 r 相似, 它一定是 k(0<k<r) 相似的
所以求出 height 数组后按其中的值排序, 然后从大到小做
当前需要处理的串为 i 和 i-1, 设前缀长度为 k
易知若将两个并查集合并, 则当前的前缀在并查集中一定是最小的, 所以 Ans[k][0]+= 两棵树 size 的乘积 (因为任意两两前缀都是 k 相似的, 可以配对)
除了并查集的 size, 还维护一下并查集的 max 和 min 值,
则 Ans[k][1]=max(Ans[k][1],Max1*Max2,Min1*Min2)
维护 min 值是为了防止有很小的复数这种情况 (负负得正)
最后因为 Ans[i] 也是满足 Ans[i+1] 的, 所以做个前缀和合并一下答案就好
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- #define MAXN (300000+100)
- #define LL long long
- using namespace std;
- LL wt[MAXN],wa[MAXN],wb[MAXN];
- LL SA[MAXN],Rank[MAXN],Height[MAXN];
- char r[MAXN];
- LL a[MAXN],cnt,Ans[MAXN][2];
- LL ID[MAXN],INF;
- LL Father[MAXN],Size[MAXN],Max[MAXN],Min[MAXN];
- LL n,m=130;
- bool cmp(LL *y,LL a,LL b,LL k)
- {
- LL arank1=y[a];
- LL brank1=y[b];
- LL arank2=a+k>=n?-1:y[a+k];
- LL brank2=b+k>=n?-1:y[b+k];
- return arank1==brank1 && arank2==brank2;
- }
- void Build_SA()
- {
- LL *x=wa,*y=wb;
- for (LL i=0;i<m;++i) wt[i]=0;
- for (LL i=0;i<n;++i) wt[x[i]=r[i]]++;
- for (LL i=1;i<m;++i) wt[i]+=wt[i-1];
- for (LL i=n-1;i>=0;--i) SA[--wt[x[i]]]=i;
- for (LL j=1;j<=n;j<<=1)
- {
- LL p=0;
- for (LL i=n-j;i<n;++i) y[p++]=i;
- for (LL i=0;i<n;++i) if (SA[i]>=j) y[p++]=SA[i]-j;
- for (LL i=0;i<m;++i) wt[i]=0;
- for (LL i=0;i<n;++i) wt[x[y[i]]]++;
- for (LL i=1;i<m;++i) wt[i]+=wt[i-1];
- for (LL i=n-1;i>=0;--i) SA[--wt[x[y[i]]]]=y[i];
- m=1;swap(x,y);
- x[SA[0]]=0;
- for (LL i=1;i<n;++i)
- x[SA[i]]=cmp(y,SA[i],SA[i-1],j)?m-1:m++;
- if (m>=n) break;
- }
- }
- void Build_Height()
- {
- for (LL i=0;i<n;++i) Rank[SA[i]]=i;
- LL k=0;
- Height[0]=0;
- for (LL i=0;i<n;++i)
- {
- if (!Rank[i]) continue;
- if (k) k--;
- LL j=SA[Rank[i]-1];
- while (r[i+k]==r[j+k]) k++;
- Height[Rank[i]]=k;
- }
- }
- LL Find (LL x) {return Father[x]==x?x:Father[x]=Find(Father[x]);}
- void Merge (LL x,LL y)
- {
- LL f1=Find(x),f2=Find(y);
- LL k=Height[x];
- Ans[k][0]+=Size[f2]*Size[f1];
- Ans[k][1]=max(max(Max[f2]*Max[f1],Min[f2]*Min[f1]),Ans[k][1]);
- Min[f1]=min(Min[f1],Min[f2]);
- Max[f1]=max(Max[f1],Max[f2]);
- Father[f2]=f1;
- Size[f1]+=Size[f2];
- }
- void Solve()
- {
- for (LL i=0;i<n;++i)
- {
- Father[i]=i;
- Size[i]=1;
- Max[i]=Min[i]=a[SA[i]];
- }
- for (LL i=0;i<=n-1;++i)
- if (Find(ID[i])!=Find(ID[i]-1))
- Merge(ID[i],ID[i]-1);
- }
- bool cmp1(LL x,LL y)
- {
- return Height[x]>Height[y];
- }
- int main()
- {
- memset(&INF,0x7f,sizeof(INF));
- scanf("%lld",&n);
- scanf("%s",r);
- for (LL i=0;i<n;++i)
- scanf("%lld",&a[i]);
- Build_SA();
- Build_Height();
- for (LL i=0;i<n;++i)
- {
- ID[i]=i;
- Ans[i][0]=0;
- Ans[i][1]=-INF;
- }
- sort(ID,ID+n,cmp1);
- Solve();
- for (LL i=n-2;i>=0;--i)
- {
- Ans[i][0]+=Ans[i+1][0];
- Ans[i][1]=max(Ans[i][1],Ans[i+1][1]);
- }
- for (LL i=0;i<n;++i)
- printf("%lld %lld\n",Ans[i][0],Ans[i][0]==0?0:Ans[i][1]);
- }
来源: http://www.bubuko.com/infodetail-2544757.html