【通俗易懂】Nebius Welcome Round (Div. 1 + Div. 2) 题解 A – D

发布于 2023-03-17  237 次阅读


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 all1 = 0;
        for(int j = 1;j <= m; ++ j)if(s[j] == '1')all1 ++;

        int y = 0;
        for(int j = 1;j < m; ++ j)
        {
            if(s[j] == s[j + 1] && s[j] == '1')y ++, j ++;
        }

        ans_min += all1 - min(m / 4, y);

        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原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞👍、收藏⭐、留言💬