dede网站源码下载,中国网站排名网官网,营销型网站建设公司电话,学做衣服网站正题
题目链接:http://codeforces.com/contest/1628/problem/A 题目大意
给出一个长度为nnn的序列aaa和一个空序列bbb#xff0c;你每次可以选择aaa的一个前缀#xff0c;将它的mexmexmex加入序列bbb的末尾#xff0c;然后将aaa的这个前缀删除。
求bbb的最大字典序。 1≤…正题
题目链接:http://codeforces.com/contest/1628/problem/A 题目大意
给出一个长度为nnn的序列aaa和一个空序列bbb你每次可以选择aaa的一个前缀将它的mexmexmex加入序列bbb的末尾然后将aaa的这个前缀删除。
求bbb的最大字典序。
1≤∑n≤2×105,0≤ai≤n1\leq \sum n\leq 2\times 10^5,0\leq a_i\leq n1≤∑n≤2×105,0≤ai≤n 解题思路
显然地我们每次肯定要选mexmexmex最大的一个前缀为了最大化我们后面的值那么我们显然是选的前缀越短越好。
而考虑如何快速求到这个前缀我们可以考虑从小到大枚举这个mexmexmex的值假设现在枚举到xxx那么证明我们得到的前缀1∼r1\sim r1∼r之中已经有0∼x−20\sim x-20∼x−2了我们就先看这个前缀中是否有x−1x-1x−1如果有就枚举下一个数不然我们就让rrr跳到第一个xxx处。
显然这样一次的复杂度是O(mexlogn)O(mex\log n)O(mexlogn)的但是因为删除的数字个数和mexmexmex同级而一个数字最多被删除一次这样时间复杂度就是O(nlogn)O(n\log n)O(nlogn)了。
写个vectorvectorvector上二分就好了。 code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N2e510;
int T,n;vectorint v[N],mex;
int lb(int x,int L){int l0,rv[x].size()-1;while(lr){int mid(lr)1;if(v[x][mid]L)lmid1;else rmid-1;}return (lv[x].size())?(n1):v[x][l];
}
int main()
{scanf(%d,T);while(T--){scanf(%d,n);mex.clear();for(int i0;in;i)v[i].clear();for(int i1,x;in;i){scanf(%d,x);v[x].push_back(i);}int l0;while(ln){int rl1;for(int i0;in;i){int plb(i,l);if(pn){mex.push_back(i);break;}rmax(p,r);}lr;}printf(%d\n,mex.size());for(int i0;imex.size();i)printf(%d ,mex[i]);putchar(\n);}
}
