题目描述 有一天，一个名叫顺旺基的程序员从石头里诞生了。又有一天，他学会了冒泡排序和独立集。在一个图里，独立集就是一个点集，满足任意两个点之间没有边。于是他就想把这两个东西结合在一起。众所周知，独立集是需要一个图的。那么顺旺基同学创造了一个算法，从冒泡排序中产生一个无向图。 
那么我们要算出这个无向图G最大独立集的大小。但是事情不止于此。顺旺基同学有时候心情会不爽，这个时候他就会要求你再回答多一个问题：最大独立集可能不是唯一的，但有些点是一定要选的，问哪些点一定会在最大独立集里。今天恰好他不爽，被他问到的同学就求助于你了。
输入 两行。第一行为N，第二行为1到N的一个全排列。
输出 两行。第一行输出最大独立集的大小，第二行从小到大输出一定在最大独立集的点的编号(输入时的序号)，每个编号后面空一个空格。
样例输入 3 3 1 2 样例输出 2 2 3
提示 【数据范围】 30%的数据满足 N<=16 60%的数据满足 N<=1,000 100%的数据满足 N<=100,000
第一问很简单，就是LIS长度 第二问的意思是最长不下降子序列的方案有许多种，需要确定哪些是肯定在方案中的。 我始终想不出用二分法的LIS应该如何解决这个，最好能够知道每个点LIS的值。 这个可以用线段树做，正着一遍，倒着一遍。 唯一性的判断可以自己再思考一下。
#include<cstdio>#include<cstring>#include<iostream>#define p1 id<<1#define p2 id<<1^1using namespace std;int n,ans;int a[100005],f[100005],h[100005],tree[400005],ok[100005];int query(int id,int l,int r,int x,int y){ if(x<=l&&r<=y) return tree[id]; int mid=(l+r)/2; if(y<=mid) return query(p1,l,mid,x,y); else if(x>mid) return query(p2,mid+1,r,x,y); else return max(query(p1,l,mid,x,mid),query(p2,mid+1,r,mid+1,y));}void update(int id,int l,int r,int x,int y){ if(l==r) { tree[id]=y; return; } int mid=(l+r)/2; if(x<=mid) update(p1,l,mid,x,y); else update(p2,mid+1,r,x,y); tree[id]=max(tree[p1],tree[p2]);}void build(int id,int l,int r){ if(l==r) { tree[id]=0; return; } int mid=(l+r)/2; build(p1,l,mid); build(p2,mid+1,r); tree[id]=0;}int main(){ cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { if(a[i]==1) f[i]=1; else f[i]=query(1,1,n,1,a[i]-1)+1; update(1,1,n,a[i],f[i]); } build(1,1,n); for(int i=n;i>=1;i--) { if(a[i]==n) h[i]=1; else h[i]=query(1,1,n,a[i]+1,n)+1; update(1,1,n,a[i],h[i]); } for(int i=1;i<=n;i++) ans=max(ans,f[i]); for(int i=1;i<=n;i++) { if(h[i]+f[i]==ans+1) { if(ok[f[i]]==0) ok[f[i]]=i; else ok[f[i]]=-1; } } cout<<ans<<endl; for(int i=1;i<=ans;i++) if(ok[i]>0) PRintf("%d ",ok[i]); return 0;}新闻热点
疑难解答
