BZOJ4698 & 洛谷2463:[SDOI2008]Sandy的卡片——题解
http://www.lydsy.com/JudgeOnline/problem.php?id=4698
https://www.luogu.org/problemnew/show/P2463#sub
Sandy和Sue的热衷于收集干脆面中的卡片。
然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积攒卡片兑换超炫的人物模型。
每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型,首先必须要集够N张卡片,对于这N张卡片,如果他们都有一个相同的子串长度为k,则可以兑换一个等级为k的人物模型。相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。
Sandy的卡片数远远小于要求的N,于是Sue决定在Sandy的生日将自己的卡片送给Sandy,在Sue的帮助下,Sandy终于集够了N张卡片,但是,Sandy并不清楚他可以兑换到哪个等级的人物模型,现在,请你帮助Sandy和Sue,看看他们最高能够得到哪个等级的人物模型。
如果你做过POJ2774:Long Long Message和POJ1743:Musical Theme的话,这道题想起来就很容易了。
将所有数差分后接起来(中间加一个大数作为分隔符),后缀数组和height数组预处理,然后二分答案,按照height分组找是否存在。
PS:差分处理具体看POJ1743:Musical Theme。
(吐槽:最开始我还想把所有数段的区间记下来,然后用log查找一个后缀属于哪个串,越想越不对劲看了题解,果然我还是太naive了,直接开个id数组记录每个数属于哪个数段就行了吗!)
(果然我容易思维定式。)
(姑且也算是不看题解1A233。)
#include<cstdio>
#include<cmath>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
typedef long long ll;
const int N=1e6+;
const int big=;
int s[N],a[N],cnt=big*+;
int n,m,t,rk[N],sa[N],w[N],height[N],id[N];
bool in[];
inline bool pan(int *x,int i,int j,int k){
int ti=i+k<n?x[i+k]:-;
int tj=j+k<n?x[j+k]:-;
return ti==tj&&x[i]==x[j];
}
void SA_init(){
int *x=rk,*y=height,r=cnt;
for(int i=;i<r;i++)w[i]=;
for(int i=;i<n;i++)w[s[i]]++;
for(int i=;i<r;i++)w[i]+=w[i-];
for(int i=n-;i>=;i--)sa[--w[s[i]]]=i;
r=;x[sa[]]=;
for(int i=;i<n;i++)
x[sa[i]]=s[sa[i]]==s[sa[i-]]?r-:r++;
for(int k=;r<n;k<<=){
int yn=;
for(int i=n-k;i<n;i++)y[yn++]=i;
for(int i=;i<n;i++)
if(sa[i]>=k)y[yn++]=sa[i]-k;
for(int i=;i<r;i++)w[i]=;
for(int i=;i<n;i++)w[x[y[i]]]++;
for(int i=;i<r;i++)w[i]+=w[i-];
for(int i=n-;i>=;i--)sa[--w[x[y[i]]]]=y[i];
swap(x,y);r=;x[sa[]]=;
for(int i=;i<n;i++)
x[sa[i]]=pan(y,sa[i],sa[i-],k)?r-:r++;
}
}
void height_init(){
int i,j,k=;
for(int i=;i<=n;i++)rk[sa[i]]=i;
for(int i=;i<n;i++){
if(k)k--;
int j=sa[rk[i]-];
while(s[i+k]==s[j+k])k++;
height[rk[i]]=k;
}
}
bool check(int k){
int sum=;
in[id[sa[]]]=;
for(int i=;i<=n;i++){
if(height[i]>=k){
if(!in[id[sa[i]]]){
sum++;
in[id[sa[i]]]=;
}
}else{
memset(in,,sizeof(in));
sum=;
in[id[sa[i]]]=;
}
if(sum==t)return ;
}
return ;
}
int main(){
scanf("%d",&t);
for(int i=;i<=t;i++){
scanf("%d",&m);
for(int j=n;j<=n+m-;j++){
scanf("%d",&a[j]);
}
for(int j=n+;j<=n+m-;j++){
s[j-]=a[j]-a[j-]+big;
id[j-]=i;
}
s[n+m-]=cnt++;
n+=m;
}
s[n++]=;
SA_init();
n--;
height_init();
int l=,r=;
while(l<r){
int mid=(l+r+)>>;
if(check(mid))l=mid;
else r=mid-;
}
printf("%d\n",l+);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者:luyouqi233。 +
+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
最新文章
- PHP-Mysqli扩展库的预编译
- Oracle列操作(增加列,修改列,删除列)
- SpringMVC实现上传和下载
- Redhat修改主机名_Red hat怎么永久修改主机名hostname(转)
- pgbouncer+pg(fdw)+pg(datanode)分表方案
- poj3159 最短路(差分约束)
- Java Load Properties 文件,定义message信息
- poj1504--求两个数的反转数的和的反转数
- asp.net用户身份验证时读不到用户信息的问题 您的登录尝试不成功。请重试。 Login控件
- 让你的代码量减少3倍!使用kotlin开发Android(四) kotlin bean背后的秘密
- A - Alice&#39;s Print Service ZOJ - 3726 (二分)
- 深度系统 deepin 15.9 关闭桌面
- juqery 点击分页显示,指定一页显示多少个,首次加载显示多少个
- vue-cli 构建项目在IE中无法运行解决方式(build之后可运行)
- bzoj5093:[Lydsy1711月赛]图的价值
- MFC中添加了一个dialog,并创建了相应的类,初始化函数没有怎么办?
- sscanf 与 ssprintf 用法 (转载--https://www.cnblogs.com/Anker/p/3351168.html)
- bzoj3884上帝与集合的正确用法
- android sdk更新代理设置
- 八、springboot整合redis
热门文章
- Java String 字符串类细节探秘
- ogg的安装配置 配置双向同步(含DDL)
- 强制删除无用old windows文件夹命令
- 使用union
- ThinkPHP开启设置子域名笔记
- 虚拟机克隆CentOs后网卡问题
- OSG-HUD
- Qt-QML-Charts-ChartView-编译错误-ASSERT: ";!";No style available without QApplication!
- Unity Lighting - The Precompute Process 预计算过程(二)
- [JSON].valueOf( keyPath )