Codeforces Round #550 (Div. 3)———A~C的题解

emmmmmm好久没有打CF了，因为我......自闭了2333~~~

A. Diverse Strings

如果字符串包含拉丁字母表中连续的(相邻的)字母，并且每个字母恰好出现一次，则称为diversity。

例如，以下字符串是多种多样的:“fced”、“xyz”、“r”和“dabcef”。

下面的字符串没有多样性:“az”、“aa”、“bad”和“babc”，注意字母“a”和“z”并不相邻。

正式地说，考虑字母表中字符串中所有字母的位置。这些位置应该形成连续的线段，也就是说，它们应该一个接一个，没有任何间隙。

给定一个字符串序列。对于每个字符串，如果它是不同的，打印“Yes”。否则,打印“不”。

输入

第一行包含整数n(1≤n≤100)，表示要处理的字符串数。下面的n行包含字符串，每一行一个字符串。每个字符串只包含小写拉丁字母，长度在1到100之间(含)。

输出

打印n行，输入中的每个字符串一行。如果对应的字符串是多种多样的，则行应该包含“Yes”;如果对应的字符串不是多种多样的，则行应该包含“No”。

思路：

小编对字符串有点恐惧，so......这题是小编最后打的。思路嘛.......字符也是可以排序的，（26个字母的ASCALL）。之后结果就出来了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
	char a[105];
	int n,d=0,sum=0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a;
		sum=strlen(a);
		sort(a,a+sum);
	if(sum==1)
		cout<<"YES"<<endl;
	else{
		for(int j=0;j<sum-1;j++){
			if(a[j]==a[j+1]){
				d=1;
				cout<<"NO"<<endl;
				break;
			}
			else{
				if(a[j]+1!=a[j+1]){
					d=1;
					cout<<"NO"<<endl;
					break;
				}
			}
		}
		if(d!=1){
			cout<<"YES"<<endl;
		}
	}
		d=0;
	}
	return 0;
}
           

B. Parity Alternated Deletions

题意：

给一个数组，里面都是整数，先删除一个奇数（偶数），然后再删除一个偶数（奇数）——交替删除，到最后不能删除的时候，求剩下的数之和的最小值。

例子

input

5

1 5 7 8 2

output

input

6

5 1 2 4 6 3

output

input

2

1000000 1000000

output

1000000

思路：

先排序，然后可以用两个数组去存，数字（一个奇数，一个偶数），然后，就可以分别统计奇数和偶数的个数（假设奇数 i 个，偶数 j 个），并将这两个数组排序，用sum=abs( i - j ) , sum表示两种数之间相差的个数。

如果，sum<2 , 输出 0 

否则，将个数多的一方，求它们sum-1个元素之和的最小值。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[1000005];
int b[1000005];
int main()
{
	int n,k,i=0,j=0;
	cin>>n;
	while(n--){
		cin>>k;
		if(k%2==0){
			a[i]=k;
			i++;
		}
		else{
			b[j]=k;
			j++;
		}
	}
	sort(a,a+i);
	sort(b,b+j);
	int sum=abs(i-j);
	int ans=0;
	if(i==0){
		int q=0;
		for(int w=0;w<j-1;w++)
			q+=b[w];
		cout<<q<<endl;
		return 0;
	}
	if(j==0){
		int q=0;
		for(int w=0;w<i-1;w++)
			q+=a[w];
		cout<<q<<endl;
		return 0;
	}
	if(i<j&&sum>1){
		for(int m=0;m<sum-1;m++)
			ans+=b[m];
		cout<<ans<<endl;
	}
	else if(i>j&&sum>1){
		for(int m=0;m<sum-1;m++)
			ans+=a[m];
		cout<<ans<<endl;
	}
	else{
		cout<<"0"<<endl;
	}
	return 0;
}
           

C. Two Shuffled Sequences

题意：

给定一个序列，将它拆成两个序列，一个严格递增，一个严格递减。不能输出“No”。（一个数字的序列和空序列符合递增和递减要求

思路：

emmmmmmm,不难，与上述B题的思路类似，用一个数组b[ i ] 统计输入元素中相同的元素，（如果相同元素的个数大于2，就输出NO）

先排序

将b[ i ],倒着输出，剩下的正着输出

#include<cstdio>
#include<iostream> 
#include<algorithm>
using namespace std;
int a[200005];
int b[200005];
int c[200005],d[200005];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		b[a[i]]++;
		if(b[a[i]]==3){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	sort(a,a+n);
	int j=0,w=0;
	for(int i=0;i<n;i++){
		if(a[i]==a[i+1]){
			d[w]=a[i];
			w++;
		}
		else{
			c[j]=a[i];
			j++;
		}
	}
	cout<<"YES"<<endl;
	cout<<w<<endl;
	if(w==0)
		cout<<endl;
	else{
		for(int i=0;i<w;i++)
			cout<<d[i]<<" ";
		cout<<endl;
	}
	cout<<j<<endl;
	for(int i=j-1;i>=0;i--){
		cout<<c[i]<<" ";
	}
return 0;
}