Codeforces Round 920 (Div. 3)(A-E)題解

发布时间:2024年01月21日

A. Square

题意:

给出矩形四个顶点的坐标,求出矩形面积;

思路:

记录最大的横纵坐标,以及最小的横纵坐标,最大的横坐标减去最小的横坐标就是矩形的一个边长,纵坐标类似减就是矩形的另一个边长

代码:

#include<iostream>
#include<algorithm>

using namespace std;

int t;
void solve(){
	int x1=-0x3f3f3f3f;
	int y1=-0x3f3f3f3f;
	int x2=0x3f3f3f3f;
	int y2=0x3f3f3f3f;
	for(int i=0;i<4;i++)
	{
		int x,y;
		cin>>x>>y;
		x1=max(x,x1);
		x2=min(x,x2);
		y1=max(y,y1);
		y2=min(y,y2);
	}
	cout<<(x1-x2)*(y1-y2)<<endl;
	
}
int main(){
	cin>>t;
	
	while(t--) solve();
	
	return 0;
}

B. Arranging Cats

题意:

给出两个01串,对其中一个01串操作,可以交换两个我位置的数字,或者翻转某个位置的数字,输出使两串位置对应相等最小的操作次数。

题解:

因为要输出最小的操作次数,所以当 a i = 1 a_{i}=1 ai?=1 b i = 0 b_{i}=0 bi?=0且存在 a j = 0 a_{j}=0 aj?=0 b j = 1 b_{j}=1 bj?=1时,最好的操作就是交换,因为可以使得两个位置都可以对应相等,当没有位置可以交换时,才进行翻转操作。若 a i = 1 a_{i}=1 ai?=1 b i = 0 b_{i}=0 bi?=0有x个, a j = 0 a_{j}=0 aj?=0 b j = 1 b_{j}=1 bj?=1情况有x个,则最少的操作次数取决于 m a x ( x , y ) max(x,y) max(x,y)

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=10010;
int a[N],b[N];
int t;
void solve(){
	int n;
	int x=0,y=0;
	
	string a,b;
	cin>>n;
	cin>>a>>b;
	
	for(int i=0;i<n;i++){
		if(a[i]=='1'&&b[i]=='0') x++;
		if(a[i]=='0'&&b[i]=='1') y++;
	}
	cout<<max(x,y)<<endl;
}
int main(){
	cin>>t;
	
	while(t--) solve();
	
	return 0;
}

C. Sending Messages

题意:

需要在n个时间段( m 1 m_{1} m1?, m 2 m_{2} m2?, m 3 m_{3} m3? m n m_{n} mn?)发送短信,初始手机电量为 f,待机每分钟消耗a个电,关机再开机这个操作需要消耗b个电,问是否能在电消耗完之前发送n条短信。

题解:

贪心的思想求出发送完n条短信所需要的总时间 s u m sum sum,若时间大于等于f则无法完成,否则可以,每次比较关机开机和待机 哪个耗电最少,加到 s u m sum sum上去,最后和 f f f比较,输出结果即可。

代码:

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;

int t;

void solve(){
	int n,f,a,b;
	int temp=0;
	int sum=0;
	int m;
	cin>>n>>f>>a>>b;
	
	for(int i=1;i<=n;i++){
		cin>>m;
		sum+=min((m-temp)*a,b);
		temp=m;
	}
	if(sum>=f) cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
}
signed main(){
	cin>>t;
	
	while(t--) solve();
	
	return 0;
}

D. Very Different Array

题意:

给出两个长度分别是n,m的数组a,b,在b数组中选出n个组成新数组c,使得 ∑ i = 0 n ( ∣ a i ? c i ∣ ) \sum_{i=0}^n(\lvert a_i-c_i\rvert) i=0n?(∣ai??ci?∣)值最大,并输出最大值。

题解:

贪心思想对两个数组排序,分别将a数组的最大值和b数组的最小值做差,以及a数组的最小值和b数组的最大值做差,差值大的即为此次配对。

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long

using namespace std;

const int  N=2e5+10;
int a[N],b[N];
int t;
void solve(){
	int n,m;
	int sum=0;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
		
	sort(a+1,a+1+n);
	sort(b+1,b+1+m);
	
	int al=1,ar=n,bl=1,br=m;
	for(int i=1;i<=n;i++){
		if(abs(a[al]-b[br])>abs(a[ar]-b[bl])){
			sum+=abs(a[al]-b[br]);
			al++;
			br--;
		}
		else{
			sum+=abs(a[ar]-b[bl]);
			ar--;
			bl++;
		}
	}
	cout<<sum<<endl;
}
signed main(){
	cin>>t;
	
	while(t--) solve();
	
	return 0;
}


E. Eat the Chip

题意:

Alice和Bob玩游戏,给定棋盘为h行,m列,给定Alice和Bob棋子的初始坐标,Alice和Bob轮流移动棋子,Alice先手移动,如果爱丽丝在回合开始时位于坐标为 ( x a , y a ) (x_{a},y_{a}) (xa?,ya?) 的单元格中,那么她可以将筹码移动到 ( x a + 1 , y a ) (x_{a}+1,y_{a}) (xa?+1,ya?) 、$ (x_{a}+1,y_{a}?1) 或 或 (x_{a}+1,y_{a}+1)$单元格中的一个。鲍勃在轮到他时,可以从坐标为 ( x b , y b ) (x_{b},y_{b}) (xb?,yb?) 的单元格移动 ( x b ? 1 , y b ) (x_{b}?1,y_{b}) (xb??1,yb?) ( x b ? 1 , y b ? 1 ) (x_{b}?1,y_{b}?1) (xb??1,yb??1) ( x b ? 1 , y b + 1 ) (x_{b}?1,y_{b}+1) (xb??1,yb?+1)。双方都想把对方的棋子吃掉,假设两人都是最佳状态下棋,求谁会赢的比赛,若无法将对方吃掉则为平局。

题解:

有三种情况
1.当 Δ \Delta Δ x x x < = <= <= 0 0 0时一定会平局,因为Alice移动一次就会下落一层,而Bob移动一次会上升一层,此时初始位置Alice在Bob下面所以就只能平局。
2.当 Δ \Delta Δ x x x为奇数时,因为Alice和Bob每次移动 Δ \Delta Δ x x x都会减一,所以此时只有Alice可能获胜,这时就变成Alice追Bob,Bob只能想法躲避,若Alice在Bob左上方,Alice会往右下方移动,Bob只会往右上方移动,若两个棋子到达相同层时,Alice无法追上Bob则平局,否则Alice获胜,反之亦然。
3.分析方法与上面类似,换成Bob追Alice。

代码:

#include<iostream>
#include<algorithm>

using namespace std;

int t;
void solve(){
	int h,w,xa,ya,xb,yb;
	
	cin>>h>>w>>xa>>ya>>xb>>yb;
	
	
	int dx=xb-xa;
	int stepa=(xb-xa+1)/2,stepb=(xb-xa)/2;
	if(dx<=0) cout<<"Draw"<<endl;
	else if(dx%2){
		if(ya<yb){
			int run=min(w-yb,stepb);
			if(ya+stepa>=yb+run) cout<<"Alice"<<endl;
			else cout<<"Draw"<<endl;
		}
		else{
			int run=min(yb-1,stepb);
			if(ya-stepa<=yb-run) cout<<"Alice"<<endl;
			else cout<<"Draw"<<endl;
		}
	}
	else{
		if(ya<yb){
			int run=min(ya-1,stepa);
			if(yb-stepb<=ya-run) cout<<"Bob"<<endl;
			else cout<<"Draw"<<endl;
		}
		else{
			int run=min(w-ya,stepa);
			if(yb+stepb>=ya+run) cout<<"Bob"<<endl;
			else cout<<"Draw"<<endl;
		}
	}
}
int main(){
	cin>>t;
	
	while(t--) solve();
	
	return 0;
}

文章来源:https://blog.csdn.net/m0_74461146/article/details/135685878
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。