首页 > 代码库 > CodeForces 486E LIS of Sequence
CodeForces 486E LIS of Sequence
题意:
n(10^5)个数字的序列a 求每个位置i 它是不出现在任何LIS中 还是 出现在一些LIS中 还是 出现在所有LIS中
思路:
比赛时候唯一没做出的题… 赛后还是不会做… - -b 看了别人的代码觉得好精妙!!
首先以O(nlogn)复杂度求出LIS
然后我们倒序扫描序列a 对于位置i 如果lis[i]=LIS或者a[i]<big[lis[i]+1] (big[x]表示lis=x的a的最大值 这里的意思是 如果a[i]是某个LIS的最后一个 或者 能与某个LIS想接) 那么这个位置是出现在LIS中的 它是不是必经之路呢?? 我们在记录一个num[y] 表示lis=y的且出现在LIS中的位置的个数
最后 我们判断如果不出现在LIS中则分到1组 否则 如果num[lis[i]]=1说明它是毕竟之路(没有与它并列的位置) 分到3组 否则 到2组
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<map> #include<set> #include<vector> #include<queue> #include<cstdlib> #include<ctime> #include<cmath> using namespace std; typedef long long LL; #define N 100010 int n; int a[N], lis[N], st[N], top, in[N], big[N], num[N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); top = 1; for (int i = 1; i <= n; i++) { if (st[top - 1] < a[i]) { st[top] = a[i]; lis[i] = top; top++; } else { int pos = lower_bound(st + 1, st + top, a[i]) - st; st[pos] = a[i]; lis[i] = pos; } } top--; for (int i = n; i >= 1; i--) { if (lis[i] == top || big[lis[i] + 1] > a[i]) { in[i] = 1; num[lis[i]]++; big[lis[i]] = max(big[lis[i]], a[i]); } } for (int i = 1; i <= n; i++) { if (in[i]) { if (num[lis[i]] > 1) putchar('2'); else putchar('3'); } else putchar('1'); } return 0; }
CodeForces 486E LIS of Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。