Nebius Welcome Round (Div. 1 + Div. 2) 题解 A - D

Nebius Welcome Round (Div. 1 + Div. 2) 题解 A - D,这四题的整体难度不大,都是过题人数上千的题。

很久没打Codeforces了,在此记录一篇题解,开学了也会不断更新的。

🎈 作者:Eriktse
🎈 简介:19岁,211计算机在读,现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)🚀
🎈 个人博客:www.eriktse.com

A. Lame King

题意:

在一个大小为201x201的网格上,每次操作可以往“上下左右”四个方向移动一格或者不动,耗时1秒。一个人从(0, 0)出发,问到达(a, b)所需的时间,要求不能出现连续两次向一样的方向移动(意思是可以暂停一秒再动)。

思路:

首先把坐标换成绝对值,表示往x, y两个方向需要移动的距离ab

不难发现这俩其实是等价的对吧,我们就不妨设a >= b

a == b时有ans = a + b,只要一直“右上右上”或者“上右上右”地走就行了。

a > b时,我如果想让x坐标到达a,那起码要走a次“向右”,然后会产生a - 1个间隙,我们可以往里面放上b个“向上”,剩余的放“暂停”就行了。答案是a + (a - 1)

所以ans = a + max(a - 1, b)

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
 int a, b;scanf("%lld %lld", &a, &b);
 if(a < 0)a = -a;
 if(b < 0)b = -b;
 
 if(a < b)swap(a, b);//保证a >= b
 int ans = a + max(a - 1, b);
 printf("%lld\n", ans);
}
signed main()
{
 int _;scanf("%lld", &_);
 while(_ --)solve();
 return 0;
}

B. Vaccination

题意:

现在有n个病人需要打疫苗,每个病人可以等待w单位时间,每箱疫苗有k支,每箱疫苗开箱后就立刻全部取出并开封,每支疫苗在开封后的保质时间为d单位时间。现在给出n个病人开始等待的时间序列,问至少消耗多少箱疫苗。

思路:

模拟 + 贪心。考虑当“疫苗用尽或疫苗过期”的时候需要开封新的疫苗,再考虑“开封新的疫苗的时间应该尽可能晚,这样能让尽可能减少过期的疫苗”。

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;
int t[maxn];
void solve()
{
 int n, k, d, w;scanf("%lld %lld %lld %lld", &n, &k, &d, &w);
 //每箱疫苗有k支,每支保质时间d,病人等待时间w
 for(int i = 1;i <= n; ++ i)scanf("%lld", t + i);
 
 int ans = 0, cnt = 0, st = 0;//st是开封时间,cnt是当前疫苗支数
 
 for(int i = 1;i <= n; ++ i)
 {
 //当疫苗耗尽或疫苗过期就开封新的疫苗,但是要赶在当前病人走的最后时刻开封
 if(cnt == 0 || st + d < t[i])st = a[i] + w, cnt = k, ans ++;//尽可能晚开封
 
 cnt --;//消耗掉一支疫苗
 }
 printf("%lld\n", ans);
}
signed main()
{
 int _;scanf("%lld", &_);
 while(_ --)solve();
 return 0;
}

C. Pull Your Luck

题意:

有一个大小为n的轮盘(下标对n取模的循环数组),当前指针位置为x,当用f的力量去转动轮盘,轮盘指针会向前移动f + (f - 1) + (f - 2) + ... + 1个位置,现在你的力量介于[1, p],问有没有可能使得指针指向0

所有样例的n之和不超过2e5

思路:

实际上就是要让指针前进(n - x) % n位嘛,取模是因为x可能等于0,每次前进的距离起始是等差数列求和f * (f + 1) / 2

值得注意的是力量不能为0,且力量上限可能非常大,所以1 ~ p枚举每一个f显然是不可行的。实际上当p较大时,我们只需要枚举到2n就够了。

判断的方法是:存在力量i满足(i * (i + 1) / 2) % n == (n - x) % n时,答案为Yes,若不存在则答案为No

简单解释一下这个2n:先考虑什么情况下会回到原地,即(i * (i + 1) / 2) == 0,当i == 2 * n的时候,存在(2n * (2n + 1) / 2) % n == 0必然成立,然后下一步是往前走2n + 1步,等价于1步,周期开始,相当于回到原点开始走第一步。

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;
int a[maxn];
void solve()
{
 int n, x, p;scanf("%lld %lld %lld", &n, &x, &p);
 int ans = false;
 for(int i = 1;i <= min(p, n * 2); ++ i)
 if((i * (i + 1) / 2) % n == (n - x) % n)ans = true;
 
 printf("%s\n", ans ? "Yes" : "No");
}
signed main()
{
 int _;scanf("%lld", &_);
 while(_ --)solve();
 return 0;
}
本文由eriktse原创,未经允许禁止转载。

D. Accommodation

题意:

一栋楼有n层,每层m个窗户,每个窗户要么亮灯(1表示)要么关灯(0表示),且每一层一定有准确的m / 4个双人间(由两个连续的窗户构成),和m / 2个单人间,这两种房间的窗户加起来恰好m个窗户,但是你不知道哪些窗户是单人间的,哪些是双人间的。

现在定义,当窗户开了灯说明这一户有人,当关灯说明没人。问你这栋楼最少人数和最多人数。

思路:

每层楼之间相互独立,所以可以单独计算最后加起来就行。

不难发现,单人间很好处理,有多少1就有多少户人嘛,主要是双人间不太好搞。

双人间可以有4种情况:00, 01, 10, 11。其中只有双人间选择为11的时候会影响到最终的人数,即使得总人数-1。

最少人数就是“尽可能多选择11的双人间”,最多人数就是“尽可能少选择11的双人间”,可以分别通过连续1的方法和模拟贪心的方法求得。

先讲最少人数,我们可以求出01串中所有连续的1的个数,假如有5个1连在一起,那就可以构成至多5 / 2 = 211双人间。通过处理出每一段连续1对结果的贡献,我们可以求得最多选出多少个11双人间,再和m / 4取个小,因为最多m / 4个双人间。

再看看最多人数,我们可以从头到尾扫描,当遇到01,10,00就直接将其设为双人间,剩余的自动变成单人间就好,同样注意m / 4

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 9;
char s[maxn];
signed main()
{
 int n, m;scanf("%lld %lld", &n, &m);
 int ans_min = 0, ans_max = 0;
 for(int i = 1;i <= n; ++ i)
 {
 scanf("%s", s + 1);
 
 int all0 = 0, all1 = 0;//all0, 1表示整个字符串中01的个数
 int c1 = 0, c0 = 0;//这是临时变量
 int k00 = 0, k11 = 0;
 for(int j = 1;j <= m; ++ j)
 {
 if(s[j] == '1')
 {
 all1 ++;
 c1 ++;
 if(c0)k00 += c0 / 2, c0 = 0;
 }else
 {
 all0 ++;
 c0 ++;
 if(c1)k11 += c1 / 2, c1 = 0;
 }
 }
 if(c1)k11 += c1 / 2, c1 = 0;
 if(c0)k00 += c0 / 2, c0 = 0;
 ans_min += all1 - min(m / 4, k11);
 
 int y = 0;
 for(int j = 1;j < m; ++ j)
 {
 if(s[j] != s[j + 1] || s[j] == '0')y ++, j ++;
 }
 
 ans_max += all1 - max(0ll, m / 4 - y);
 
 }
 printf("%lld %lld\n", ans_min, ans_max);
 return 0;
}
🎈 本文由eriktse原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞👍、收藏⭐、留言💬
作者:Eriktse原文地址:https://segmentfault.com/a/1190000043549971

%s 个评论

要回复文章请先登录注册