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

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

A. Perfect Permutation

题意及要求： 给定一个整数n，构成一个从1到n无重复排列中，a[i]能被i整除的个数最少。

思路： 当n大于1时，n-1不可能被n整除。 所以 首先输出n，再输出1到n-1。

代码：

#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

题意及要求： 一共m对朋友，共n个人，每个人都有一个不开心值a[i]，如果他没有被邀请，则总不开心值就增加a[i]，现举行派对，每对朋友可以分享一个蛋糕，但要求 最后吃掉的蛋糕数量为偶数 。

思路：若m为偶数，则将所有人邀请时，蛋糕数量一定为偶数

若m为奇数，则邀请所有人时蛋糕数量为奇数，则将蛋糕数量变为偶数：

• 删去一个人j，且这个人的朋友为num[j]且必须是奇数，相当于少了奇数 (num[j]) 个蛋糕；
• 删去一对朋友j1,j2，且这两个人的朋友数量 (num[j1]与num[j2]) 均为偶数，则蛋糕相当于少了奇数 (1+num[j1]+num[j2]) 个。

代码：

#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];//记录每个人的不开心值
int num[N];//每个人出现的次数
int people[N][2];//记录每对朋友

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){//若m是偶数，则邀请所有人去派对吃的蛋糕一定是偶数
		cout <<0<<endl;
		return;
	}
	
	int ans = 0x3f3f3f3f;
	for(int i=1;i<=m;i++){//去掉一对朋友，且他们朋友数均为偶数
		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++){//去掉一个人，且他的朋友是奇数
		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

题意及要求： 给定n*m的矩阵，现有k种颜料，每种颜料可以使用a[i]次。问有没有一种染色方法，可以让矩阵中的每个格子，它的周围四个格子至少有三个格子和它的颜色相同。

思路： 可以自己画图试一下，最终发现同一种颜色颜料，只能染至少两行或两列。所以直接暴力按行染色和按列染色即可。

代码：

#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];//每种染料能染几行
		b[i]=c[i];//每种染料能染几列
		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;
}