【CF比赛记录】 —— Codeforces Round 920 (Div. 3)(A、B、C、D)

发布时间:2024年01月16日

🌏博客主页:PH_modest的博客主页
🚩当前专栏:CF比赛记录
💌其他专栏:
🔴每日一题
🟡 cf闯关练习
🟢 C语言跬步积累
🌈座右铭:广积粮,缓称王!

A. Square

👉传送门👈
在这里插入图片描述

1.Tutorial

直接暴力每个点直接的距离,然后排个序,排序后的结果为:宽、宽、长、长、斜边、斜边,第一个和第三个就是宽和长,因为一个点和另外几个点组成的边分为三种:宽、长、斜边。根据斜边大于宽和长就可以得到前面的结论。

2.Solution

//https://codeforces.com/contest/1921/problem/A
//
//
#include<bits/stdc++.h>
#define int long long
using namespace std;

int f(int x,int y)
{
	return sqrt(x*x+y*y);
}

void solve()
{
	int s[8];
	int a,aa,b,bb,c,cc,d,dd;
	cin>>a>>aa>>b>>bb>>c>>cc>>d>>dd;
	s[0]=f(abs(a-b),abs(aa-bb));
	s[1]=f(abs(a-c),abs(aa-cc));
	s[2]=f(abs(a-d),abs(aa-dd));
	s[3]=f(abs(b-c),abs(bb-cc));
	s[4]=f(abs(b-d),abs(bb-dd));
	s[5]=f(abs(c-d),abs(cc-dd));
	sort(s,s+6);
	int x=s[0],y=s[2];
	cout<<x*y<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

3.Conclusion

这边不建议使用hypot来求斜边(我一开始用了之后结果会出错,浪费了我好长时间


B. Arranging Cats

👉传送门👈
在这里插入图片描述

1.Tutorial

  • 结论:分别记录操作一和操作二的次数,最大的就是结果。
  • 推导:分别统计需要放入猫的数量(操作一,pt),和需要移除猫的数量(操作二,mov),因为这两个可以合并成一个动作完成(操作三),两个值当中求取一个最小的(minn),这个就是合并成操作三,然后用这两个数的较大值减去较小值就是得到需要单独完成的次数(maxx-minn),两个相加就得到结果了(minn+maxx-minn)。

2.Solution

//https://codeforces.com/contest/1921/problem/B
//
//
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
	int n;
	cin>>n;
	string s,f;
	cin>>s>>f;
	int mov=0,pt=0;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='1'&&f[i]=='0')
		{
			mov++;
		}
		else if(s[i]=='0'&&f[i]=='1')
		{
			pt++;
		}
	}
	int minn=min(mov,pt);
	int maxx=max(mov,pt);
	int ans=minn+maxx-minn;
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

C. Sending Messages

👉传送门👈
在这里插入图片描述

1.Tutorial

每次可以选择两种操作:

  • 操作一:不黑屏,一直亮屏到下一次发消息(x*a)(x表示经过的时间,a表示单位时间失去的电量)
  • 操作二:黑屏,到下一次发消息再亮屏(b)(b表示操作二需要花费的电量)

只需要每次发消息前比较一下哪种情况消耗的电量少,最后判断一下电量是否大于0即可

2.Solution

//https://codeforces.com/contest/1921/problem/C
//
//
#include<bits/stdc++.h>
#define int long long
using namespace std;

int s[200020];
int v[200020];
void solve()
{
	int n,f,a,b;
	cin>>n>>f>>a>>b;
	s[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
	}
	for(int i=0;i<n;i++)
	{
		v[i]=s[i+1]-s[i];
		if(v[i]*a<b)
		{
			f-=(v[i]*a);
		}
		else
		{
			f-=b;
		}
	}
	if(f>0) cout<<"YES\n";
	else cout<<"NO\n";
	
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}


3.Conclusion

这种题目很容易想复杂,建议先以简单的情况写,发现结果不对再改,不然很浪费时间


D. Very Different Array

👉传送门👈
在这里插入图片描述

1.Tutorial

贪心
每次肯定是选差值最大的,差值最大会在两种情况下产生:

  • a数组中最大的 - b数组中最小的
  • b数组中最大的 - a数组中最小的

所以只需要比较这两个值,取最大值即可

具体操作就是先将两个数组排序,因为是直接判断,顺序对结果没有影响,然后将排好序的数组分别尾插到双端队列中(方便尾删和头删),然后遍历判断即可

2.Solution

//https://codeforces.com/contest/1921/problem/D
//
//
#include<bits/stdc++.h>
#define int long long
using namespace std;

int a[200020];
int b[200020];
deque<int>s;
deque<int>v;
int ans=0;
int k=0;
int m,n;

void solve()
{
	s.clear();
	v.clear();
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<m;i++)
	{
		cin>>b[i];
	}
	sort(a,a+n);
	sort(b,b+m);
	for(int i=0;i<n;i++)
	{
		s.push_back(a[i]);
	}
	for(int i=0;i<m;i++)
	{
		v.push_back(b[i]);
	}
	ans=0;
	for(k=0;k<n;k++)
	{
		if(abs(s.back()-v.front())>abs(v.back()-s.front()))
		{
			ans+=(abs(s.back()-v.front()));
			s.pop_back();
			v.pop_front();
		}
		else
		{
			ans+=(abs(v.back()-s.front()));
			s.pop_front();
			v.pop_back();
		}
	}
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}


最后:

CF比赛记录系列旨在记录比赛过程,所以对代码的解释并不会特别详细,但足够引导大家写出来,选的题目都不会特别难,但也不是特别简单,比较考验大家的基础和应用能力,我希望能够将这个系列一直写下去,也希望大家能够和我一起坚持每天写代码。

之后每个星期都会不定期更新codeforces和atcoder上的题目,想要学习算法的友友们千万别错过了,有什么疑问欢迎大家在评论区留言或者私信博主!

在这里送大家一句话:广积粮,缓称王!

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