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;
}