AtCoder Beginner Contest 382 A~D

· · 题解

A - Daily Cookie

洛谷链接

AtCoder链接

题目

有 N 个盒子排成一排，其中一些盒子里装有饼干。

这些盒子的状态由长度为 N 的字符串 S 表示。具体来说，如果 S 的第 i 个字符是 @，则从左边开始的第 i 个方框 (1 \le i \le N) 中包含一块饼干；如果是 .，则为空。

在接下来的 D 天里，高桥每天都会从这些盒子里的饼干中选择并吃掉一块。

求 D 天过去后，N 个盒子中有多少个是空的。(可以证明这个值并不取决于高桥每天选择的饼干）。

可以保证 S 中至少有 D 次出现 @。

代码

#include <bits/stdc++.h>

using namespace std;

int n, d, cnt;
string s;

int main()
{
    scanf("%d %d", &n, &d);
    cin >> s;
    for (int i = 0; i < s.length(); i ++ )
    {
        if (s[i] == '@')
            cnt ++;
    }
    cout << n - (cnt - d) << '\n';
    return 0;
}

B - Daily Cookie 2

洛谷链接

AtCoder链接

题目

高桥选择 cookie 的方式和要求你找到的东西与问题 A 不同。

有 N 个盒子排成一行，其中一些盒子里有饼干。

这些盒子的状态由长度为 N 的字符串 S 表示。具体来说，如果 S 的第 i 个字符是 @，那么从左边开始的第 i 个盒子 (1 \le i \le N) 包含一个 cookie，如果是 .，则为空。

在接下来的 D 天里，高桥每天都会从这些盒子里的饼干中选择并吃掉一块。在每一天里，他都会选择最右边盒子里的饼干，因为该盒子里有一块饼干。

请判断 N 个盒子中的每个盒子在 D 天后是否装有饼干。

保证 S 中至少有 D 次出现 @。

代码

#include <bits/stdc++.h>

using namespace std;

int n, d;
string s;

int main()
{
    scanf("%d %d", &n, &d);
    cin >> s;
    for (int i = s.length() - 1; d != 0; i -- )
    {
        if (s[i] == '@')
        {
            d --;
            s[i] = '.';
        }
    }
    cout << s << '\n';
    return 0;
}

C - Kaiten Sushi

洛谷链接

AtCoder链接

题目

有 N 人光顾一家传送带寿司店，他们的编号从 1 到 N。第 i 个的美食级别是 A_i。

现在，M 块寿司将被放在传送带上。第 j 个寿司的美味度为 B_j。每块寿司按照这个顺序从 1,2, \ldots ,N 人面前经过。当美味程度不低于自己美食水平的寿司从面前经过时，每个人都会拿起并吃掉这个寿司；否则，他们什么也不会做。拿起并吃掉的寿司 i 将不再从 j\ (j>i) 面前经过。

对于 M 个寿司，确定谁吃了该寿司，或者是否没人吃，如果没人吃则输出 -1。

代码

#include <bits/stdc++.h>

using namespace std;

int n, m, a[200010], x[200010], cnt, app[200010], b, w;

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        if (app[a[i]] == 0)
        {
            x[++ cnt] = a[i];
            app[a[i]] = i;
        }
    }
    sort(x + 1, x + 1 + cnt);
    for (int i = 2; i <= cnt; i ++ )
        app[x[i]] = min(app[x[i]], app[x[i - 1]]);
    while (m -- )
    {
        scanf("%d", &b);
        if (b < x[1])
        {
            puts("-1");
            continue;
        }
        w = upper_bound(x + 1, x + 1 + cnt, b) - x - 1;
        cout << app[x[w]] << '\n';
    }
    return 0;
}

D - Keep Distance

洛谷链接

AtCoder链接

题目

给你整数 N 和 M。

按词典顺序，打印所有长度为 N 的整数序列 (A_1,A_2, \ldots ,A_N)，这些序列满足以下所有条件。

思路

这些序列最后可以很容易地按词序排序，因此我们将首先尝试简单地枚举符合要求的序列。

为便于解释，如果一个序列符合符合性序列的前缀（最初连续的几个项），我们就认为这个序列是好的。

我们将考虑如何枚举好的序列。

长度为 1 的序列 (A_1) 如果且仅如果 1 \le A_1 \le M-10(N-1) 才是好序列。(如果 A_1>M-10(N-1)，那么 A_N 即使是最小值，也会超过 M）。

假设 2 \le i \le N 和 (A_1,A_2, \ldots ,A_{i-1}) 是一个好序列。那么，当且仅当 A_{i-1}+10 \le A_i \le M-10(N-i) 是良好序列时，A_i 的范围 (A_1,A_2, \ldots ,A_{i-1},A_i) 才是良好序列。(理由与 A_1 相同）。

根据这一规则枚举出好序列，问题就迎刃而解了。

由于好序列最多有 \binom{21}{9} = 293930 个，因此如果实施得当，枚举速度已经足够快了。在某些情况下，可能会自然而然地产生按词典顺序排列的好序列。

即使不评估答案的数量，我们也可以猜测符合要求的序列没有那么多，因为我们被要求打印所有的序列，并认为只要操作的数量与好序列的数量一样多，算法就会在规定的时间内完成。

代码

#include <bits/stdc++.h>

using namespace std;

int n, m, X;
vector<int> na;

int main()
{
    scanf("%d %d", &n, &m);
    vector<vector<int> > w = {{}};
    for (int i = 1; i <= n; i ++ )
    {
        vector<vector<int> > v;
        for (vector<int> a : w)
        {
            for (int x = (i == 1 ? 1 : a.back() + 10); x <= m - 10 * (n - i); x ++ )
            {
                na = a;
                na.push_back(x);
                v.push_back(na);
            }
        }
        swap(v, w);
    }
    X = w.size();
    cout << X << '\n';
    for (int i = 0; i < X; i ++ )
    {
        for (int j = 0; j < n; j ++ )
            cout << w[i][j] << " \n"[j == n - 1];
    }
    return 0;
}