bzoj1318[spoj 744] Longest Permutation
题意
给出一个长度为n的,所有元素大小在[1,n]的整数数列,要求选出一个尽量长的区间使得区间内所有元素组成一个1到区间长度k的排列,输出k的最大值
n<=1e5
分析
不会做,好菜啊.jpg
学习了西方那一套理论,里面别人的题解写得挺吼的但是没多少人点赞23333.
外来的和尚好念经
一个合法排列必然包括一个1.那么我们可以枚举这个1的位置,既然包含了这个1就不能包含其他的1,所以我们可以找出这个1左边的第一个1的位置L(如果没有就是0)和右边的第一个1的位置R(如果没有就是n+1).包括这个1的排列左端不能超过L+1,右端不超过R-1.
于是我们把问题转化成若干个子问题,每个子问题处理的区间中只有一个1.所有子问题的区间总长之和是O(n)的,因为原序列中的每个位置只会对最多两个子问题贡献1的区间长度.
现在考虑怎样解决一个子问题.
一个长度为L的序列如果合法,那么序列中的最大值等于L且序列中没有重复元素.
在一个子问题中,区间内只有一个1,那么选出的序列必然包含这个1,而选出的序列中的最大值可以在这个1的左侧,也可以在这个1的右侧.由对称性,只考虑最大值在左侧的情况.在右侧的情况反着跑一遍就行.
如果最大值在左侧,我们可以枚举选出的序列的左端点l,那么从1的位置一直到l的最大值就是1左侧的最大值,因为我们假设最大值在1的左侧,所以现在我们也认为这个最大值是整个选出的序列的最大值.那么选出的序列的长度也就确定了,序列的右端点r也就确定了,我们只需判断[l,r]是不是一个合法的区间.也就是判一下[l,r]的最大值是不是在1的位置的左侧,判一下[l,r]中是否有重复元素.如果是合法的,就用r-l+1更新答案.
求最大值只需要预处理Max[i]表示从1所在的位置一直到i的最大值.
判断[l,r]是否有重复元素只需预处理lsame[i]表示i左侧第一个数值和a[i]相等的位置,如果l<=i<=r的所有i中存在一个i使得lsame[i]>=l,那么有重复元素,否则没有.
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=300005;
int a[maxn];
int lsame[maxn],rsame[maxn];
int pos[maxn];
int ans=0;
int Max[maxn],MaxLsame[maxn];
void work(int s,int L,int R){
if(ans==0)ans=1;
Max[s]=a[s];
for(int i=s-1;i>=L;--i)Max[i]=max(Max[i+1],a[i]);
for(int i=s+1;i<=R;++i)Max[i]=max(Max[i-1],a[i]);
MaxLsame[s]=lsame[s];
for(int i=s-1;i>=L;--i)MaxLsame[i]=max(MaxLsame[i+1],lsame[i]);
for(int i=s+1;i<=R;++i)MaxLsame[i]=max(MaxLsame[i-1],lsame[i]);
for(int i=s-1;i>=L;--i){//maximum number left of s
if(MaxLsame[i]>=i)continue;
int length=Max[i];
int r=i+length-1;
if(r>R)continue;
if(MaxLsame[r]>=i||Max[r]>=Max[i])continue;
if(length>ans)ans=length;
}
for(int i=s+1;i<=R;++i){//maximum number right of s
if(MaxLsame[i]>=s)continue;
int length=Max[i];
int l=i-length+1;
if(l<L)continue;
if(MaxLsame[l]>=l||MaxLsame[i]>=l||Max[l]>=Max[i])continue;
if(length>ans)ans=length;
}
}
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",a+i);
for(int i=1;i<=n;++i){
lsame[i]=pos[a[i]];pos[a[i]]=i;
}
for(int i=1;i<=n;++i)pos[i]=n+1;
for(int i=n;i>=1;--i){
rsame[i]=pos[a[i]];pos[a[i]]=i;
}
for(int i=1;i<=n;++i){
if(a[i]==1){
work(i,lsame[i]+1,rsame[i]-1);
}
}
printf("%d\n",ans);
return 0;
}
最新文章
- 【IOS】模仿windowsphone列表索引控件YFMetroListBox
- 静态代码审查工具FxCop插件开发(c#)
- localdb下载地址
- linux笔记四-------用户和组的管理
- Ubuntu 14.04中Mysql中文乱码问题最小化解决
- wpf 查找页面的所有TextBox
- Unable to open liblaunch_sim.dylib. Try reinstalling Xcode or the simulator
- jquery中prop()方法和attr()方法的区别
- DOM笔记(九):引用类型、基本包装类型和单体内置对象
- 关于AutoComplete整合
- JS字符串方法总结整理
- File文件操作学习总结
- typedef 摘自百度百科
- android踩坑日记1
- 每天学点SpringCloud(八):使用Apollo做配置中心
- ASP.NET MVC5+EF6+EasyUI 仓库管理系统
- [math][mathematica] archlinux 下 mathematica 的安装 (科学计算软件 mathematica/matlab/sagemath)
- jmeter 在linux服务器的安装和运行;
- mybatis关联查询resultmap的使用详解resultmap
- lucence学习系列之一 基本概念
热门文章
- 2017-2018-1 20155327 《信息安全系统设计基础》课堂测试&;课下作业
- WPF之路-键盘与鼠标事件 - 简书
- 1563: [NOI2009]诗人小G
- EmitMapper自动映射工具
- Jmeter资源监控工具ServerAgent运行原理的一些研究
- 怎样安装Scrapy
- sqlserver(2012)清理tempdb
- TPO-17 C2 Reschedule part-time job in campus dining hall
- IncDec序列:差分+贪心
- eBay报告:德国或将成为外贸电商热门市场