「BZOJ1318」[SPOJ744] Longest Permutation
Description
给你一个序列A含有n个正整数(1<=Ai<=n)。A的子集形式类如Au, Au+1 … , Av (1<=u<=v<=n)，即必须是连续的。我们感兴趣的是一种子集，它含有元素包括1,2,…k。（k是子集的大小）。 你的任务是找到这种类型的最长的子集。
Input
第一行，一个数n，表示序列A的长度 第二行，n个数，第I个数表示元素Ai
Output
一个数，表示可选子集的长度
Sample Input
5
4 1 2 3 2
4 1 2 3 2
Sample Output
4
HINT
你可以选得子集从A1开始到A4,这个子集长度为4，包含了1，2，3，4）
1<=n<=100010
题解
对于一个题中要求的数列。必然满足条件：
A.数列中元素都不同
B.数列中元素和为（q+1)*q/2 （q为最大值）
c.数列中包含1
枚举每个1，例如a[x]=1，假定最大值在x的左边
向左扫描的过程中不断更新最大值即数列长度。。
通过记录前缀和该数后面第一个出现相同的数的位置
设最大值为len。。。向右最早出现相同的数的位置r也不断要更新。。
比如当前到了i。i+len<r且sum[i+len-1]-sum[i-1]=len*(len+1)/2 可以用len更新答案。
把数列翻转一下再做一遍
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans; int a[100015],nxt[100015],last[100015]; ll sum[100015]; bool mark[100015]; void cal(int x) { int len=0,r=inf; for(int i=x+1;a[i]!=1&&i<=n;i++) if(!mark[a[i]])mark[a[i]]=1; else {r=i;break;} for(int i=x;i;i--) { if(a[i]==1&&i!=x)break; len=max(len,a[i]); r=min(nxt[i],r); if(i+len-1<r&&i+len-1<=n) { if(sum[i+len-1]-sum[i-1]==(ll)len*(len+1)/2)ans=max(len,ans); } } for(int i=x+1;a[i]!=1&&i<=n;i++)mark[a[i]]=0; } void solve() { memset(last,127,sizeof(last)); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; for(int i=n;i;i--) { nxt[i]=last[a[i]]; last[a[i]]=i; } for(int i=1;i<=n;i++) if(a[i]==1)cal(i); } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); solve(); for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]); solve(); printf("%d\n",ans); return 0; } |
Subscribe
计数器 9304557
OI 课件=>
OI 课件=>