CodeForces Pound #550(div3)

A. Diverse Strings

time limit per test1 second
memory limit per test256 megabytes

A string is called diverse if it contains consecutive (adjacent) letters of the Latin alphabet and each letter occurs exactly once. For example, the following strings are diverse: “fced”, “xyz”, “r” and “dabcef”. The following string are not diverse: “az”, “aa”, “bad” and “babc”. Note that the letters ‘a’ and ‘z’ are not adjacent.

Formally, consider positions of all letters in the string in the alphabet. These positions should form contiguous segment, i.e. they should come one by one without any gaps. And all letters in the string should be distinct (duplicates are not allowed).

You are given a sequence of strings. For each string, if it is diverse, print “Yes”. Otherwise, print “No”.Input

The first line contains integer 𝑛n (1≤𝑛≤1001≤n≤100), denoting the number of strings to process. The following 𝑛n lines contains strings, one string per line. Each string contains only lowercase Latin letters, its length is between 11 and 100100, inclusive.Output

Print 𝑛n lines, one line per a string in the input. The line should contain “Yes” if the corresponding string is diverse and “No” if the corresponding string is not diverse. You can print each letter in any case (upper or lower). For example, “YeS”, “no” and “yES” are all acceptable.
Example

input

8 
fced
xyz
r
dabcef
az
aa
bad
babc

output

Yes 
Yes
Yes
Yes
No
No
No
No

对字符串排序一次即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define INF 0x3f3f3f3f
#define pb push_back
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int main(){
	int t;cin>>t;
	while(t--){
		string s;cin>>s;
		int flag=1;set<char> num;
		//if(s.length()==1) flag=1;
		sort(s.begin(),s.end());
		for(int i=0;i<s.length();++i){
			num.insert(s[i]);
			if(i==0) continue;
			if(abs(s[i]-s[i-1])!=1) flag=0;
		}
		if(num.size()!=s.length()) flag=0;
		if(flag) cout<<"Yes\n";
		else cout<<"No\n";
	}
}

 

B. Parity Alternated Deletions

time limit per test2 seconds memory limit per test256 megabytes

Polycarp has an array 𝑎a consisting of 𝑛n integers.

He wants to play a game with this array. The game consists of several moves. On the first move he chooses any element and deletes it (after the first move the array contains 𝑛−1n−1 elements). For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-… or odd-even-odd-even-…) of the removed elements. Polycarp stops if he can’t make a move.

Formally:

  • If it is the first move, he chooses any element and deletes it;
  • If it is the second or any next move:
    • if the last deleted element was odd, Polycarp chooses any even element and deletes it;
    • if the last deleted element was even, Polycarp chooses any odd element and deletes it.
  • If after some move Polycarp cannot make a move, the game ends.

Polycarp’s goal is to minimize the sum of non-deleted elements of the array after end of the game. If Polycarp can delete the whole array, then the sum of non-deleted elements is zero.

Help Polycarp find this value.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤20001≤n≤2000) — the number of elements of 𝑎a.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (0≤𝑎𝑖≤1060≤ai≤106), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a.Output

Print one integer — the minimum possible sum of non-deleted elements of the array after end of the game.

input

5
1 5 7 8 2

output

0

input

6
5 1 2 4 6 3

output

0

input

2
1000000 1000000

output

1000000

分类讨论一波

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define INF 0x3f3f3f3f
#define pb push_back
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int main(){
	int n;cin>>n;
	vector<int> aodd,aeven;
	int odd=0,even=0;
	for(int i=0;i<n;++i){
		int x;cin>>x;
		if(x%2) aodd.pb(x),odd++;
		else aeven.pb(x),even++;
	}
	if(odd==even) cout<<"0\n";
	else if(odd>even){
		odd-=even;
		odd--;
		sort(aodd.begin(),aodd.end());
		int ans=0;
		for(int i=0;i<odd;++i) ans+=aodd[i];
		cout<<ans<<endl;
	}
	else if(odd<even){
		even-=odd;
		even--;
		sort(aeven.begin(),aeven.end());
		int ans=0;
		for(int i=0;i<even;++i) ans+=aeven[i];
		cout<<ans<<endl;
	}

}

 

C. Two Shuffled Sequences

time limit per test2 seconds memory limit per test256 megabytes

Two integer sequences existed initially — one of them was strictly increasing, and the other one — strictly decreasing.

Strictly increasing sequence is a sequence of integers [𝑥1<𝑥2<⋯<𝑥𝑘][x1<x2<⋯<xk]. And strictly decreasing sequence is a sequence of integers [𝑦1>𝑦2>⋯>𝑦𝑙][y1>y2>⋯>yl]. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

They were merged into one sequence 𝑎a. After that sequence 𝑎a got shuffled. For example, some of the possible resulting sequences 𝑎a for an increasing sequence [1,3,4][1,3,4] and a decreasing sequence [10,4,2][10,4,2] are sequences [1,2,3,4,4,10][1,2,3,4,4,10] or [4,2,1,10,4,3][4,2,1,10,4,3].

This shuffled sequence 𝑎a is given in the input.

Your task is to find any two suitable initial sequences. One of them should be strictly increasing and the other one — strictly decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

If there is a contradiction in the input and it is impossible to split the given sequence 𝑎a to increasing and decreasing sequences, print “NO”.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of elements in 𝑎a.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (0≤𝑎𝑖≤2⋅1050≤ai≤2⋅105), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a.Output

If there is a contradiction in the input and it is impossible to split the given sequence 𝑎a to increasing and decreasing sequences, print “NO” in the first line.

Otherwise print “YES” in the first line and any two suitable sequences. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

In the second line print 𝑛𝑖ni — the number of elements in the strictly increasing sequence. 𝑛𝑖ni can be zero, in this case the increasing sequence is empty.

In the third line print 𝑛𝑖ni integers 𝑖𝑛𝑐1,𝑖𝑛𝑐2,…,𝑖𝑛𝑐𝑛𝑖inc1,inc2,…,incni in the increasing order of its values (𝑖𝑛𝑐1<𝑖𝑛𝑐2<⋯<𝑖𝑛𝑐𝑛𝑖inc1<inc2<⋯<incni) — the strictly increasing sequence itself. You can keep this line empty if 𝑛𝑖=0ni=0 (or just print the empty line).

In the fourth line print 𝑛𝑑nd — the number of elements in the strictly decreasing sequence. 𝑛𝑑nd can be zero, in this case the decreasing sequence is empty.

In the fifth line print 𝑛𝑑nd integers 𝑑𝑒𝑐1,𝑑𝑒𝑐2,…,𝑑𝑒𝑐𝑛𝑑dec1,dec2,…,decnd in the decreasing order of its values (𝑑𝑒𝑐1>𝑑𝑒𝑐2>⋯>𝑑𝑒𝑐𝑛𝑑dec1>dec2>⋯>decnd) — the strictly decreasing sequence itself. You can keep this line empty if 𝑛𝑑=0nd=0 (or just print the empty line).

𝑛𝑖+𝑛𝑑ni+nd should be equal to 𝑛n and the union of printed sequences should be a permutation of the given sequence (in case of “YES” answer).
Examples

input

7 
7 2 7 3 3 1 4

output

YES 
2
3 7
5
7 4 3 2 1

input

5 
4 3 1 5 3

output

YES 
1
3
4
5 4 3 1

input

5 
1 1 2 1 2

output

NO

input

5 
0 1 2 3 4

output

YES 
0

5
4 3 2 1 0

如果一个数出现次数大于2则输出NO,否则正着扫一遍倒着扫一遍即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define INF 0x3f3f3f3f
#define pb push_back
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int a[maxn];int num[maxn];
int flag[maxn];
int main(){
	int n;cin>>n;
	
	for(int i=0;i<n;++i){
		cin>>a[i];
		num[a[i]]++;
		if(num[a[i]]>2){
			cout<<"NO\n";
			exit(0);
		}
	}
	cout<<"YES\n";
	sort(a,a+n);
	
	mst(flag,0);
	vector<int> ans1,ans2;
	
	for(int i=n-1;i>=0;--i){
		if(!flag[a[i]]&&num[a[i]]){
			ans2.pb(a[i]);
			flag[a[i]]=1;
			num[a[i]]--;
		}
	}
	for(int i=0;i<n;++i){
		if(num[a[i]]){
			ans1.pb(a[i]);
			
			num[a[i]]--;
		}
	}
	cout<<ans1.size()<<endl;
	for(int i=0;i<ans1.size();++i){
		printf(i==0?"%d":" %d",ans1[i]);
	}
	cout<<endl;
	cout<<ans2.size()<<endl;
	for(int i=0;i<ans2.size();++i){
		printf(i==0?"%d":" %d",ans2[i]);
	}
	cout<<endl;
	exit(0);
}

 

D. Equalize Them All

time limit per test2 seconds memory limit per test256 megabytes

You are given an array 𝑎a consisting of 𝑛n integers. You can perform the following operations arbitrary number of times (possibly, zero):

  1. Choose a pair of indices (𝑖,𝑗)(i,j) such that |𝑖−𝑗|=1|i−j|=1 (indices 𝑖i and 𝑗j are adjacent) and set 𝑎𝑖:=𝑎𝑖+|𝑎𝑖−𝑎𝑗|ai:=ai+|ai−aj|;
  2. Choose a pair of indices (𝑖,𝑗)(i,j) such that |𝑖−𝑗|=1|i−j|=1 (indices 𝑖i and 𝑗j are adjacent) and set 𝑎𝑖:=𝑎𝑖−|𝑎𝑖−𝑎𝑗|ai:=ai−|ai−aj|.

The value |𝑥||x| means the absolute value of 𝑥x. For example, |4|=4|4|=4, |−3|=3|−3|=3.

Your task is to find the minimum number of operations required to obtain the array of equal elements and print the order of operations to do it.

It is guaranteed that you always can obtain the array of equal elements using such operations.

Note that after each operation each element of the current array should not exceed 10181018 by absolute value.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of elements in 𝑎a.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (0≤𝑎𝑖≤2⋅1050≤ai≤2⋅105), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a.Output

In the first line print one integer 𝑘k — the minimum number of operations required to obtain the array of equal elements.

In the next 𝑘k lines print operations itself. The 𝑝p-th operation should be printed as a triple of integers (𝑡𝑝,𝑖𝑝,𝑗𝑝)(tp,ip,jp), where 𝑡𝑝tp is either 11 or 22 (11means that you perform the operation of the first type, and 22 means that you perform the operation of the second type), and 𝑖𝑝ip and 𝑗𝑝jp are indices of adjacent elements of the array such that 1≤𝑖𝑝,𝑗𝑝≤𝑛1≤ip,jp≤n, |𝑖𝑝−𝑗𝑝|=1|ip−jp|=1. See the examples for better understanding.

Note that after each operation each element of the current array should not exceed 10181018 by absolute value.

If there are many possible answers, you can print any.
Examples


input

5 
2 4 6 6 6

output

2 
1 2 3
1 1 2

input

3 
2 8 10

output

2 
2 2 1
2 3 2

input

4 
1 1 1 1

output

0

出现次数最多的那个数就是我们最终要得到的那个序列,因此正着扫一遍倒着扫一遍即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define INF 0x3f3f3f3f
#define pb push_back
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
struct node{
	int op,i,j;
};
int a[maxn];
int num[maxn],maxnum=0,maxx=0;
vector<node> ans;
int main(){
	int n;cin>>n;
	for(int i=0;i<n;++i){
		cin>>a[i];
		num[a[i]]++;
		if(num[a[i]]>maxnum){
			maxnum=num[a[i]];
			maxx=a[i];
		}
	}
	ans.clear();
	for(int i=0;i<n-1;++i){
		if(a[i]==maxx&&a[i+1]!=maxx){
			node tem;tem.op=a[i+1]<a[i]?1:2;tem.i=i+1+1;tem.j=i+1;
			ans.pb(tem);
			a[i+1]=maxx;
		}
	}

	for(int i=n-1;i>0;--i){
		if(a[i]==maxx&&a[i-1]!=maxx){
			node tem;tem.op=a[i-1]<a[i]?1:2;tem.i=i+1-1;tem.j=i+1;
			ans.pb(tem);
			a[i-1]=maxx;
		}
	}
	cout<<ans.size()<<endl;
	for(int ii=0;ii<ans.size();++ii){
		cout<<ans[ii].op<<" "<<ans[ii].i<<" "<<ans[ii].j<<endl;
	}
	exit(0);
}

 

E. Median String

time limit per test2 seconds memory limit per test256 megabytes

You are given two strings 𝑠s and 𝑡t, both consisting of exactly 𝑘k lowercase Latin letters, 𝑠s is lexicographically less than 𝑡t.

Let’s consider list of all strings consisting of exactly 𝑘k lowercase Latin letters, lexicographically not less than 𝑠s and not greater than 𝑡t(including 𝑠s and 𝑡t) in lexicographical order. For example, for 𝑘=2k=2, 𝑠=s=”az” and 𝑡=t=”bf” the list will be [“az”, “ba”, “bb”, “bc”, “bd”, “be”, “bf”].

Your task is to print the median (the middle element) of this list. For the example above this will be “bc”.

It is guaranteed that there is an odd number of strings lexicographically not less than 𝑠s and not greater than 𝑡t.Input

The first line of the input contains one integer 𝑘k (1≤𝑘≤2⋅1051≤k≤2⋅105) — the length of strings.

The second line of the input contains one string 𝑠s consisting of exactly 𝑘k lowercase Latin letters.

The third line of the input contains one string 𝑡t consisting of exactly 𝑘k lowercase Latin letters.

It is guaranteed that 𝑠s is lexicographically less than 𝑡t.

It is guaranteed that there is an odd number of strings lexicographically not less than 𝑠s and not greater than 𝑡t.Output

Print one string consisting exactly of 𝑘k lowercase Latin letters — the median (the middle element) of list of strings of length 𝑘klexicographically not less than 𝑠s and not greater than 𝑡t.Examples

input

2 
az
bf

output

bc

input

5 
afogk
asdji

output

alvuw

input

6 
nijfvj
tvqhwp

outputCopy

qoztvz

模拟除法和加法,只是变成了26进制

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define INF 0x3f3f3f3f
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int ans[maxn];
int main(){
	int n;cin>>n;
	string s1,s2;cin>>s1>>s2;
	for(int i=n-1;i>=0;--i){
		ans[i]=(s1[i]+s2[i]-'a'-'a');
		if(ans[i]%2){
			ans[i]/=2;
			ans[i+1]+=13;
			ans[i]+=ans[i+1]/26;
			ans[i+1]%=26;
		}
		else ans[i]/=2;
	}
	for(int i=0;i<n;++i) printf("%c",ans[i]+'a');
}

 

F. Graph Without Long Directed Paths

time limit per test2 seconds memory limit per test256 megabytes

You are given a connected undirected graph consisting of 𝑛n vertices and 𝑚m edges. There are no self-loops or multiple edges in the given graph.

You have to direct its edges in such a way that the obtained directed graph does not contain any paths of length two or greater (where the length of path is denoted as the number of traversed edges).Input

The first line contains two integer numbers 𝑛n and 𝑚m (2≤𝑛≤2⋅1052≤n≤2⋅105, 𝑛−1≤𝑚≤2⋅105n−1≤m≤2⋅105) — the number of vertices and edges, respectively.

The following 𝑚m lines contain edges: edge 𝑖i is given as a pair of vertices 𝑢𝑖ui, 𝑣𝑖vi (1≤𝑢𝑖,𝑣𝑖≤𝑛1≤ui,vi≤n, 𝑢𝑖≠𝑣𝑖ui≠vi). There are no multiple edges in the given graph, i. e. for each pair (𝑢𝑖,𝑣𝑖ui,vi) there are no other pairs (𝑢𝑖,𝑣𝑖ui,vi) and (𝑣𝑖,𝑢𝑖vi,ui) in the list of edges. It is also guaranteed that the given graph is connected (there is a path between any pair of vertex in the given graph).Output

If it is impossible to direct edges of the given graph in such a way that the obtained directed graph does not contain paths of length at least two, print “NO” in the first line.

Otherwise print “YES” in the first line, and then print any suitable orientation of edges: a binary string (the string consisting only of ‘0’ and ‘1’) of length 𝑚m. The 𝑖i-th element of this string should be ‘0’ if the 𝑖i-th edge of the graph should be directed from 𝑢𝑖ui to 𝑣𝑖vi, and ‘1’ otherwise. Edges are numbered in the order they are given in the input.

Example

input

6 5 
1 5
2 1
1 4
3 1
6 1

output

YES 
10100

Note

The picture corresponding to the first example:

And one of possible answers:

染色问题,如果dfs过程中染到和当前点一样的颜色就输出0

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define INF 0x3f3f3f3f
#define pb push_back
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,m;
vector<int> g[maxn];
int a[maxn],b;
int op[maxn];
int flag=1;
void dfs(int x,int fa,int cnt){
	op[x]=cnt;
	for(int i=0;i<g[x].size();++i){
		if(g[x][i]!=fa){
			if(op[g[x][i]]==-1)
				dfs(g[x][i],x,1-cnt);
			else if(op[x]==op[g[x][i]]){
				flag=0;return;
			}
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;++i){
		cin>>a[i]>>b;
		g[a[i]].pb(b);g[b].pb(a[i]);
	}
	mst(op,-1);
	dfs(1,1,1);
	if(flag==0){
		cout<<"NO\n";
		exit(0);
	}
	cout<<"YES\n";
	for(int i=0;i<m;++i){
		//cout<<mp[i]<<endl;
		if(op[a[i]])cout<<"1";
		else cout<<"0";
	}
}

 

发表评论,支持MarkDown语法