【CF闯关练习】—— 800分段

2023-12-22 00:13:36

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

一.关卡1(00:11)

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

题目大意:


单果有一个整数 n n n

他想把这个数表示为三个不同的正整数 x x x y y y z z z 的和。此外,Monocarp 希望 x x x y y y z z z 中没有一个能被 3 3 3 整除。

你的任务是帮助 Monocarp 找到由不同的正整数 x x x y y y z z z 组成的有效三元组,或者报告说这样的三元组不存在。


1.Tutorial

a固定是1,b从2开始递增,c从n-b开始递减,然后维护b和c,判断他们是否是3的倍数,如果不满足条件就b++,c–,直到b>=c就结束

2.Solution

//https://codeforces.com/problemset/problem/1886/A
//00:11
//a固定是1,b从2开始递增,c从n-b开始递减,然后维护b和c,判断他们是否是3的倍数,如果不满足条件就b++,c--,直到b>=c就结束
#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;


void solve()
{
	int n;
	cin>>n;
	int a,b,c;
	a=1;
	n-=1;
	b=2;
	c=n-b;
	while(b<c)
	{
		if(b%3==0||c%3==0)
		{
			b+=1;
			c-=1;
			continue;
		}
		else
		{
			cout<<"Yes"<<"\n"<<a<<" "<<b<<" "<<c<<"\n";
			return;
		}
	}
	if(b>=c)
	{
		cout<<"NO"<<"\n";
	}
	else
	{
		cout<<"Yes"<<"\n"<<a<<" "<<b<<" "<<c<<"\n";
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}


二.关卡2(00:14(-1))

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

题目大意:


Monocarp 组织了一次举重比赛。有 n n n 个运动员参加比赛, i i i 个运动员有 s i s_i si? 个力量和 e i e_i ei? 个耐力。第 1 1 1 名运动员是莫诺卡普的朋友波利卡普,莫诺卡普非常希望波利卡普能够获胜。

比赛将按以下方式进行。评委将选择一个正**(大于零)整数 w w w ,表示比赛中使用的杠铃的重量。每位运动员的目标是尽可能多地举起杠铃。举起杠铃次数最多的运动员将被宣布为获胜者(如果有多个这样的运动员–则没有获胜者)**。

如果杠铃的重量 w w w 严格**大于 i i i (第3名)运动员的力量 s i s_i si? ,那么 i i i (第3名)运动员将一次也举不起杠铃。否则, i i i th运动员就能举起杠铃,而且他举起杠铃的次数将等于他的耐力 e i e_i ei?

例如,假设有 4 4 4 个运动员,参数分别为 s 1 = 7 , e 1 = 4 s_1 = 7, e_1 = 4 s1?=7,e1?=4 s 2 = 9 , e 2 = 3 s_2 = 9, e_2 = 3 s2?=9,e2?=3 s 3 = 4 , e 3 = 6 s_3 = 4, e_3 = 6 s3?=4,e3?=6 s 4 = 2 , e 4 = 2 s_4 = 2, e_4 = 2 s4?=2,e4?=2 。如果杠铃的重量是 5 5 5 ,那么:

  • 第一名运动员能够举起杠铃 4 4 4 次;
  • 第二名运动员能够举起杠铃 3 3 3 次;
  • 第三名运动员将无法举起杠铃;
  • 第四名运动员将无法举起杠铃。

莫诺卡普想选择 w w w ,让波利卡普( 1 1 1 (st)运动员)赢得比赛。请帮助他选择 w w w 的值,或者报告说这是不可能的。


1.Tutorial

从第二个人开始遍历,先看耐力值,如果大于等于第一个人再看力量,如果力量也大于等于那么就说明没有w满足条件

2.Solution

//https://codeforces.com/problemset/problem/1879/A
//00:14(-1)
//没输入完不能直接结束
//从第二个人开始遍历,先看耐力值,如果大于等于第一个人再看力量,如果力量也大于等于那么就说明没有w满足条件
#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;

void solve()
{
	int n;
	cin>>n;
	int s=0,e=0;
	cin>>s>>e;
	int ans=s;
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		if(b<e)
		{
			continue;
		}
		else
		{
			if(a>=s)
			{
				ans=-1;
			}
		}
	}
	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;
}

3.Conclusion

写的时候WA了一发,检查的时候发现当程序中有数据不满足时我就直接结束程序了,导致后面还有数据没输入,这就是边输入边检查最容易犯的一个错误


三.关卡3(00:19(-3))

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

题目大意:


塞尔维亚信息学奥林匹克竞赛结束后,阿莱克萨非常伤心,因为他没有获得奖牌(他不知道奖牌的数量),所以瓦西里耶来给他出了一道简单的题,让他的心情好起来。

瓦西里耶给了阿列克萨一个正整数 n n n ( n ≥ 3 n \ge 3 n3 ),让他构造一个大小为 n n n 的正整数严格递增数组,使得

  • 3 ? a i + 2 3\cdot a_{i+2} 3?ai+2? 不能被 a i + a i + 1 a_i+a_{i+1} ai?+ai+1? 整除。( 1 ≤ i ≤ n ? 2 1\le i \le n-2 1in?2 ).

请注意,大小为 n的严格递增数组 a是一个每 i( 1≤i≤n?1) 都有 a i a_i ai?< a i + 1 a_{i+1} ai+1?的数组。

由于 Aleksa 认为自己现在是个糟糕的程序员,所以他请你帮他找到这样一个数组。


1.Tutorial

通过选择第一个 n,奇正整数 1,3,5,…,2n-1,我们发现 3*ai+2也是奇数,而数字 ai+ai+1是偶数,奇数永远不能被偶数整除,所以构造是正确的。

2.Solution

//https://codeforces.com/problemset/problem/1878/B
//00:19,-3
//通过选择第一个 n,奇正整数 1,3,5,…,2n-1,我们发现 3*ai+2也是奇数,而数字 ai+ai+1是偶数,奇数永远不能被偶数整除,所以构造是正确的。
//
#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;

int s[200020];

void solve()
{
	int n;
	cin>>n;
	s[0]=1,s[1]=3,s[2]=5;
	for(int i=3;i<n;i++)
	{
		s[i]=s[i-1]+2;
	}
	for(int i=0;i<n;i++)
	{
		cout<<s[i]<<" ";
	}
	cout<<"\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

这道题我写的稀烂,数字没构造好导致WA了三发(数字太大直接越界了),写这类题目应该优先考虑特殊情况


四.关卡4(00:06)

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

题目大意:

1.Tutorial

所有队伍的效率和为0

2.Solution

//https://codeforces.com/problemset/problem/1877/A
//00:06
//所有队伍的效率和为0
#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;

void solve()
{
	int n;
	cin>>n;
	int sum=0;
	for(int i=0;i<n-1;i++)
	{
		int a;
		cin>>a;
		sum+=a;
	}

	cout<<0-sum<<"\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


五.关卡5(00:09)

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

题目大意:


给你一张长 s s s 格的纸条。每个单元格要么是黑色,要么是白色。在一次操作中,你可以取任意 k k k 个连续的单元格,并将它们全部变为白色。

请计算去除所有黑色单元格所需的最少操作次数。


1.Tutorial

直接找B,找到之后将指针往后移动k个单位

2.Solution

//https://codeforces.com/problemset/problem/1873/D
//00:09
//直接找B,找到之后将指针往后移动k个单位
#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;


void solve()
{
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<n;i++)
    {
    	if(s[i]=='B')
    	{
			ans++;
			i+=k;
			i--;
		}
	}
	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;
}




最后:

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

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

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

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