Codeforces Round ＃810 (Div.2) A-C

Codeforces Round #810 (Div.2) A-C

A. Perfect Permutation

Meaning and requirements ： Given an integer n, Form a slave 1 To n No repeated arrangement ,a[i] Can be i The number of divisions is the least .

Ideas ： When n Greater than 1 when ,n-1 It's impossible to be n to be divisible by . therefore The first output n, Then the output 1 To n-1.

Code ：

#include<bits/stdc++.h>
#define IOS std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long
#define endl "\n"

using namespace std;

const int mn = 1e5+10;
const int mod = 1e9+7;
const int N = 2e5+10;
int dr[4][2]={
   {-1,0},{1,0},{0,-1},{0,1}};

void solve(){
	int n;
	cin >>n;
	cout <<n<<" ";
	for(int i=1;i<n;i++){
		cout <<i<<" ";
	}
	cout <<endl;
}

signed main(){
	
	IOS;
	
	int T=1;
	cin >>T;
	while(T--){
		solve();
	}
	return 0;
}

---

B. Party

Meaning and requirements ： altogether m To friends , common n personal , Everyone has an unhappy value a[i], If he is not invited , Then the total unhappiness value increases a[i], Now hold a party , Each pair of friends can share a cake , But ask for The number of cakes eaten at last is even .

Ideas ： if m For the even , When you invite everyone , The number of cakes must be even

if m It's odd , The number of cakes is odd when everyone is invited , Change the number of cakes to an even number ：

• Delete a person j, And this person's friend is num[j] And must be odd , It is equivalent to missing odd numbers (num[j]) A cake ;
• Delete a pair of friends j1,j2, And the number of friends of these two people (num[j1] And num[j2]) They are all even numbers , Then the cake is equivalent to missing an odd number (1+num[j1]+num[j2]) individual .

Code ：

#include<bits/stdc++.h>
#define IOS std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long
#define endl "\n"
//#pragma GCC optimize(2)

using namespace std;

const int mn = 1e5+10;
const int mod = 1e9+7;
const int N = 2e5+10;
int dr[4][2]={
   {-1,0},{1,0},{0,-1},{0,1}};

int a[N];// Record everyone's unhappiness 
int num[N];// The number of times each person appears 
int people[N][2];// Record every pair of friends 

void solve(){
	memset(num,0,sizeof num);
	int n,m;
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	for(int i=1;i<=m;i++){
		cin >>people[i][0]>>people[i][1];
		num[people[i][0]]++;
		num[people[i][1]]++;
	}
	if(m%2==0){// if m It's even , Then invite everyone to the party and eat an even number of cakes 
		cout <<0<<endl;
		return;
	}
	
	int ans = 0x3f3f3f3f;
	for(int i=1;i<=m;i++){// Get rid of a pair of friends , And the number of their friends is even 
		if(num[people[i][0]]%2==0&&num[people[i][1]]%2==0){
			ans=min(ans,a[people[i][0]]+a[people[i][1]]);
		}
	}
	for(int i=1;i<=n;i++){// Remove one person , And his friends are odd 
		if(num[i]&1){
			ans=min(ans,a[i]);
		}
	}
	cout <<ans<<endl;
}

signed main(){
	
	IOS;
	
	int T=1;
	cin >>T;
	while(T--){
		solve();
	}
	return 0;
}

---

C. Color the Picture

Meaning and requirements ： Given n*m Matrix , existing k Pigment , Each pigment can be used a[i] Time . Ask if there is a dyeing method , You can make every lattice in the matrix , At least three of the four grids around it are the same color as it .

Ideas ： You can draw your own picture and try it , Finally found the same color pigments , You can only dye at least two rows or two columns . So direct force dyeing by row and column .

Code ：

#include<bits/stdc++.h>
#define IOS std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long
#define endl "\n"

using namespace std;

const int mn = 1e5+10;
const int mod = 1e9+7;
const int N = 2e5+10;
int dr[4][2]={
   {-1,0},{1,0},{0,-1},{0,1}};

int a[mn];
int b[mn];
int c[mn];

void solve(){
	int n,m,k;
	cin >>n>>m>>k;
	
	int t_a = min(n,m);
	int t_b = max(n,m);
	int line_a=t_b;
	int line_b=t_a;
	
	for(int i=1;i<=k;i++){
		cin >>c[i];
		a[i]=c[i];// How many lines can each dye dye dye 
		b[i]=c[i];// How many columns can each dye dye dye 
		a[i]/=t_a;
		b[i]/=t_b;
	}
	
	sort(a+1,a+1+k);
	sort(b+1,b+1+k);
	
	for(int i=1;i<=k;i++){
		if( c[i]>=(n*m) ){
			cout<<"YES"<<endl;
			return;
		}
		if(a[i]>=line_a||b[i]>=line_b){
			cout<<"YES"<<endl;
			return;
		}
		if(a[i]>1){
			if(line_a-a[i]!=1){
				line_a-=a[i];
			}else{
				if(a[i]!=2)
					line_a-=(a[i]-1);
			}
		}
		if(b[i]>1){
			if(line_b-b[i]!=1){
				line_b-=b[i];
			}else{
				if(b[i]-1!=1)
					line_b-=(b[i]-1);
			}
		}
		if(line_a<=0||line_b<=0){
			cout <<"YES"<<endl;
			return;
		}
	}
	cout <<"NO"<<endl;
}

signed main(){
	
	IOS;
	
	int T=1;
	cin >>T;
	while(T--){
		solve();
	}
	return 0;
}