【CF闯关练习】—— 800分段
🌏博客主页: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 n≥3 ),让他构造一个大小为 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 1≤i≤n?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上的题目,想要学习算法的友友们千万别错过了,有什么疑问欢迎大家在评论区留言或者私信博主!
在这里送大家一句话:广积粮,缓称王!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!