AtCoder Beginner Contest 388 题解

A. ?UPC

签到

code:

#include <bits/stdc++.h>

using namespace std;

string s;

int main()
{
    cin >> s;

    cout << s[0] << "UPC" << endl;

    return 0;
}

B. Heavy Snake

暴力枚举

code:

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, d;
int t[N], l[N];

int main()
{
    cin >> n >> d;
    for (int i = 0; i < n; i++) cin >> t[i] >> l[i];

    for (int i = 1; i <= d; i++)
    {
        int res = 0;
        for (int j = 0; j < n; j++) res = max(res, t[j] * (l[j] + i));
        cout << res << endl;
    }

    return 0;
}

C. Various Kagamimochi

对于每个年糕，可以用二分来查找尺寸大与等于它两倍的年糕的数量，统计所有数量即可

时间复杂度 \(o(nlogn)\)

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 500010;

int n;
int a[N];

signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = i - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (a[mid] * 2 > a[i]) r = mid - 1;
            else l = mid;
        }
        if (a[l] * 2 <= a[i]) res += l + 1;
    }

    cout << res << endl;

    return 0;
}

D. Coming of Age Celebration

对于第 \(i\) 个刚成年的人，假设此时他拥有的石头数量为 \(x\)，那么他会向之后 \(min(x, n - i)\) 个人赠送石头，也就是使 \([i + 1, i + min(x, n - i)]\) 这个区间的所有人石头数加一。

对于区间修改操作，可以使用差分数组来维护。

设 \(b[i]\) 为 第 \(i\) 个人获得石头数的差分数组，则 只需要进行 \(b[i + 1]+1\) 和 \(b[i + min(x, n-i)+1]-1\) 这两步操作即可维护第 \(i\) 个人赠送礼物的过程。

时间复杂度 \(O(n)\)

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 500010;

int n;
int a[N], b[N];

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        b[i] += b[i - 1];
        a[i] += b[i];
        int x = min(a[i], n - i);
        b[i + 1]++, b[i + x + 1]--;
        a[i] -= x;
        cout << a[i] << ' ';
    }
    cout << endl;

    return 0;
}

E. Simultaneous Kagamimochi

首先注意到答案具有单调性，因此可以考虑二分答案。

对于 \(check\) 函数，假设二分的答案为 \(x\)，则最优解一定是把最小的 \(x\) 个年糕放在上面，最大的 \(x\) 个年糕放在下面，对于这两组年糕，从小到大一一对应即可。

时间复杂度 \(O(nlogn)\)

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 500010;

int n;
int a[N];
int c[N];

bool check(int x)
{
    int l = 0, r = n - x;
    while (r < n)
    {
        if (a[l] * 2 > a[r]) return false;
        l++, r++;
    }
    return true;
}

signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int l = 0, r = n / 2;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (!check(mid)) r = mid - 1;
        else l = mid;
    }

    cout << l << endl;

    return 0;
}

F. Dangerous Sugoroku

由于 \(n\) 的数量级很大，遍历 \(n\) 显然超时，可以考虑分情况讨论。

• 对于两个坏区间之间，可以暴力判断能否以左区间之后 \(20\) 个位置为起点，以右区间之前 \(20\) 个位置为终点，完成跳跃操作。 由于跳跃距离的变化是连续的，假设进行了 \(c\) 次跳跃操作，则能够跳跃的总距离范围是 \([a*c,b*c]\)，因此，只需找到一个跳跃次数 \(c\)，满足起点到终点的距离在 \(a*c\) 和 \(b*c\) 之间，即可判断能够从起点跳到终点。
• 对于跨越坏区间，只需要使用当前坏区间之前 \(20\) 个位置为起点，只进行一次跳跃，来跨越坏区间。

可以使用 \(set\) 或者 \(map\) 来记录当前位置是否能够被到达。

时间复杂度 \(o(m * 20 * 20 * logn)\)

code:

#include <bits/stdc++.h>

#define endl '\n'
#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 20010;

int n, m, a, b;
PII t[N];
set<int> s;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> a >> b;
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        t[i] = {l, r};
    }

    t[++m] = {n + 1, n + 1};
    s.insert(1);

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= 20; j++)
        {
            if (s.count(t[i].x - j)) continue;
            for (int k = 1; k <= 20; k++)
            {
                if (!s.count(t[i - 1].y + k)) continue;
                int x = t[i].x - j - t[i - 1].y - k;
                if (x < 0) continue;
                int c = x / a, r = x % a;
                if ((b - a) * c >= r) s.insert(t[i].x - j);
            }
        }
        for (int j = 1; j <= 20; j++)
        {
            if (!s.count(t[i].x - j)) continue;
            if (t[i].x - j <= t[i - 1].y) continue; 
            for (int k = a; k <= b; k++) s.insert(t[i].x - j + k);
        }
    }

    if (s.count(n)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

G. Simultaneous Kagamimochi 2

考虑优化二分。

对于第 \(i\) 个年糕，\(st[i]\) 记为 \(i\) 往后 \(st[i]\) 个数字，才会遇到第一个 \(j\)，满足 \(a[i] * 2 <= a[j]\)，可以用二分来维护。

在二分答案的过程中，区间会被分成 \((l,l + mid - 1)\) 和 \((l + mid, r)\) 两部分。 若要使 \(check\) 答案成立，左边部分所有的 \(st[i]\)，也就是左区间的最大 \(st[i]\) 需要满足小于等于 \(r - mid + 1 - l\)，即对于 \(i\)，最小满足 \(a[j] >= a[i] * 2\) 的 \(j\) 不能超过 \(r - mid + 1\)。

可以用 \(st\) 表来维护区间 \(st[i]\) 最大值。

时间复杂度 \(O(nlogn)\)

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 500010;

int n, m;
int a[N];
int st[N][25];

int query(int l, int r)
{
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        int l = i + 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (a[mid] / 2 < a[i]) l = mid + 1;
            else r = mid;
        }
        if (a[l] / 2 >= a[i]) st[i][0] = l - i;
        else st[i][0] = n + 1 - i;
    }

    for (int j = 1; j <= 22; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);

    cin >> m;
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        
        int ll = 0, rr = r - l + 1 >> 1;
        while (ll < rr)
        {
            int mid = ll + rr + 1 >> 1;
            if (query(l, l + mid - 1) <= r - (l + mid - 1)) ll = mid;
            else rr = mid - 1;
        }
        cout << ll << endl;
    }

    return 0;
}