Codeforces Round #767 (Div. 2) C D

打比赛的那天晚上太累了，想先睡一会，听见闹钟的时候发现比赛还有两分钟就要开始了。。加之这几天实际上并没有在训练（下次一定TAT，对自己的做题能力没什么信心，于是我在ll“希望”大家都参加比赛的时候睡了过去。 醒来一看，div2怎么全是蓝名？原来紫名和橙名都去打div1了。原来没打这场的人只有我。 ll出于对我在acm竞赛实训甲课程上的良好表现的鼓励，为我这个青名破了例，让我又能回到集训队。站在命运的转折点上，哪里还有理由不努力？ “希望”又怎么可能是字面意思，寒假没有专门的训练安排，“希望参加cf”的含义只能是必须完成的训练任务。

比赛链接

[https://codeforces.com/contest/1629](https://codeforces.com/contest/1629 "https://codeforces.com/contest/1629")

C

题意

给定2e5个数构成的序列a，要求构造一个字典序最大的序列b。构造规则如下：每次选取前k个a中的数，求出他们的mex值插入b的末尾，并在a中删除他们，并改变下标。

思路

有一个很重要的性质：a[1...i]的mex值是随着i的增加而单调不减的。
如果a[1..i]>a[1..i-1]，那么i必须划分给前一段，并在这里分段（断开）

很容易想到O(n^2)的做法
从后往前依次枚举a中的下标i，计算a[1..i]和a[1..i-1]，如果值不一样，那么i必须加入前一段

O(n^2)

		vector<int>ans;
		int st=1;
		while(st&lt;=n){
			for(int i=n;i&gt;=st;i--){    //特判 
				int mx=mex(st,i);int mn=mex(st,i-1);
				if(mx&gt;mn||st==n&amp;&amp;mx==mn){
					ans.push_back(mx);
					st=i+1;
				}
			}
		}
		printf("%d\n",ans.size());
		for(auto i:ans){
			printf("%d ",i);
		}
		puts("");

然而会超时


O(n)做法：每次加进b的值一定是整个序列a的mex值，因此先求出mex(a)，再删除前k（他们的mex最大，且k最小）个a中的值。细节见代码

O(n)

//求mex 
		int mex=0;
		for(int i=0;i<=n;i++){
			if(!cnt[i]){
				mex=i;
				break;
			}
		}
		//删除前k个数（它们的mex最大，且k最小 
		int cntt=0;
		for(int i=0;i<=n;i++) tem[i]=0;
		bool flag=0;
		for(int i=1;i<=n;i++){
			if(mex==0){
				ans.push_back(0);
				continue;
			}
			if(!tem[a[i]]&&a[i]<=mex-1){
				tem[a[i]]++;
				cntt++;   //如果cntt刚好出现k次，就可以分段了 (cntt必须是小于mex的才计数 
				if(cntt==mex){
					cntt=0;
					ans.push_back(mex);
					for(int j=0;j<mex;j++) cnt[j]-=tem[j],tem[j]=0;
					for(int j=0;j<=n;j++){
						if(!cnt[j]){
							mex=j;
							break;
						}
					}
				} 
			}
			else tem[a[i]]++;
		}
		printf("%d\n",ans.size());
		for(auto i:ans){
			printf("%d ",i);
		}
		puts("");

<br />学习了同学的代码发现还有O(nlogn)做法<br />
1.STL<br />
2.主席树</p>

D

题意

给定1e5个字符串，每个字符串长度不超过3（长度为1~3），从中删除一些字符，问能否使得剩下字符连在一起构成回文串

思路

用map把字符串映射到bool类型（是否出现过）
一个重要性质：回文串最短只可能是由a/ab+ba+abc+cba+ab+cba+abc+ba构成的
而且对不对称的字符串顺序也有要求

D

                scanf("%d",&n);
		for(int i=1;i<=n;i++) cin>>s[i],m[s[i]]++;
		bool flag=0;
		string tem1,tem2,tem3;
		for(int i=0;i<26;i++){
			tem1="";
			char ch1=(i+'a');
			tem1+=ch1;
			
			for(int j=0;j<26;j++){
				tem2="";
				char ch2=(j+'a');
				tem2+=ch2; 
				
				for(int k=0;k<26;k++){
					tem3 = "";
					char ch3=(k+'a');
					tem3+=ch3;
					if(m[tem3]>=1){
						flag=1;
						break;
					}
					if(m[tem2+tem3]>=1&&m[tem3+tem2]>=1){
						flag=1;
						break;
					}
					if(m[tem1+tem2+tem3]>=1&&m[tem3+tem2+tem1]>=1){
						flag=1;
						break;
					}
				}
				if(flag) break;
			}
			if(flag) break;
		}
		
		map<string,int>mp;
		for(int i=1;i<=n;i++) mp[s[i]]++;
		for(int i=1;i<=n;i++){
			if(s[i].length()==2){
				for(int j=0;j<26;j++){
					char ch=(j+'a');
					string pre=s[i];
					reverse(pre.begin(),pre.end());
					pre=(string)(pre+ch);
					string last=(string)(ch+pre.substr(0,2));
					if(mp[pre]==0&&m[pre]>=1||mp[last]){
						flag=1;
						break;
					}
				}
			}
			if(s[i].length()==3){
				for(int j=0;j<26;j++){
					char ch=(j+'a');
					string tem=s[i];
					reverse(tem.begin(),tem.end());
					tem=tem[0]+tem[1];
					string last=tem.substr(1,2);
					if(mp[tem]==0&&m[tem]>=1||mp[last]){
						flag=1;
						break;
					}
				}
			}
			if(flag) break;
			mp[s[i]]--;
		}
		
		if(flag){
			puts("yes");
		}
		else puts("no");
		m.clear();