1923(EDUdiv2)

A. Moving Chips

一条彩带被分成 $n$ 个单元，从左到右依次编号为 $1$ 到 $n$ 。每个小格要么有一个芯片，要么是空闲的。

您可以执行以下任意次数（可能为零）的操作：选择一个筹码并将其移动到左边近的空闲单元格。您可以选择任何您想要的芯片，只要它的左边至少有一个空闲的单元格。移动筹码时，操作前所在的单元格会变成空闲单元格。

您的目标是移动芯片，使它们形成一个单一的块，它们之间没有任何空闲单元格。您最少需要进行多少次操作？

数第一个 1 和最后一个 1 中间有多少个 0 即可。

void solve() {
    int n;cin >> n;vector<int> a(n);for (auto& i : a)cin >> i;
    int j = 0, k = 0;
    for (int i = 0;i < n;i++) {
        if (a[i] == 1) {
            j = i;break;
        }
    }
    for (int i = 0;i < n;i++) {
        if (a[i] == 1) {
            k = i;
        }
    }
    int cnt = 0;
    for (int i = j;i <= k;i++) {
        if (a[i] == 0) {
            cnt++;
        }
    }
    cout << cnt << '\n';
}

B. Monsters Attack!

您正在玩一款电脑游戏。游戏的当前关卡可以用一条直线来模拟。你的角色位于这条直线的 $0$ 点。有 $n$ 个怪物试图杀死你的角色；其中 $i$ 个怪物的健康值等于 $a_{i}$ ，并且最初位于 $x_{i}$ 点。

每秒钟都会发生以下情况：

首先，你最多向怪物发射 $k$ 颗子弹。每颗子弹的目标正好是一个怪物，并使其生命值减少 $1$ 。对于每颗子弹，你可以任意选择目标（例如，你可以将所有子弹都射向一个怪物，也可以将所有子弹都射向不同的怪物，或者选择任何其他组合）。任何怪物都可以成为子弹的目标，不受其位置和其他因素的影响；
然后，所有健康值为 $0$ 或更低的活着的怪物死亡；
然后，所有活着的怪物向您移动 $1$ 点（在您左边的怪物坐标增加 $1$ ，在您右边的怪物坐标减少 $1$ ）。如果有怪物接近你的角色（移动到 $0$ 点），你就输了。

你能在杀死所有 $n$ 只怪物的同时，不让任何一只怪物靠近你的角色吗？

容易知道，坐标的正负没用，所以可以直接取绝对值，从最小坐标贪心即可。

这段代码赛时因为没有开 ll 被 hack 了

#define int long long
void solve() {
    int n, k;cin >> n >> k;vector<pair<int, int>> a(n);
    for (int i = 0;i < n;i++)cin >> a[i].second;
    for (int i = 0;i < n;i++) {
        int m;cin >> m;
        a[i].first = abs(m);
    }
    sort(a.begin(), a.end());
    int cnt = 0;
    int i = 0;
    for (int time = 0;time <= n;time++) {
        cnt += k;
        while (i < n && a[i].first - time > 0 && cnt >= a[i].second) {
            cnt -= a[i].second;
            i++;
        }
        if (i == n)break;
        if (time == n) {
            cout << "NO\n";return;
        }
    }
    cout << "YES\n";
}

C. Find B

如果存在一个长度为 $m$ 的整数数组 $b$ 且以下条件成立，那么长度为 $m$ 的数组 $a$ 就被认为是好数组：

$\sum_{i = 1}^{m} a_{i} = \sum_{i = 1}^{m} b_{i}$ ;
从 $1$ 到 $m$ 的每个索引 $i$ 都是 $a_{i} \neq b_{i}$ ；
从 $1$ 到 $m$ 的每个索引 $i$ 的 $b_{i} > 0$ 。

给你一个长度为 $n$ 的数组 $c$ 。数组中的每个元素都大于 $0$ 。

你必须回答 $q$ 个查询。在 $i$ -th 查询中，你必须确定子数组 $c_{l_{i}}, c_{l_{i} + 1}, \dots, c_{r_{i}}$ 是否是好数组。

Solution

可以发现当 $n$ 为偶数时，最少的满足情况 $b : 1, 1, 1, \dots 2, 2, 2, \dots$ 如果再多一定能满足条件，再少一定不能满足条件 (因为 1 的个数大于了一半的区间大小，无论如何变一定会有 1 重复)

当 $n$ 为奇数时，最小的满足情况 $b : 1, 1, 1, \dots, 2, 2, 2 \dots 2$ 如果再多一定能满足条件，再少一定不能满足条件 (因为 1 或者 2 1的个数大于了一半的区间大小，无论如何变一定会有 1 重复)

#define int long long
void solve() {
    int n, q;cin >> n >> q;vector<int> a(n + 1), pre(n + 1), cnt1(n + 1);for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)pre[i] = pre[i - 1] + a[i];
    for (int i = 1;i <= n;i++)cnt1[i] = cnt1[i - 1] + (a[i] == 1);

    while (q--) {
        int l, r;cin >> l >> r;
        if (r == l) {
            cout << "NO\n";continue;
        }
        if (cnt1[r] - cnt1[l - 1] + r - l + 1 > pre[r] - pre[l - 1]) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
}

Hack 数据: 5 1 1 1 1 1

while (q--) {
        int l, r;cin >> l >> r;
        if (r == l) {
            cout << "NO\n";continue;
        }
        int cnt = (r - l + 1) / 2 + (r - l + 1);
        if ((r - l + 1) % 2 == 0) {
            if (cnt <= pre[r] - pre[l - 1]) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        } else {
            if (cnt + 1 <= pre[r] - pre[l - 1]) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }

D. Slimes

$n$ 个史莱姆排成一行，编号为 $1 - n$ ，第 $i$ 个的粘液大小是 $a_{i}$

每秒钟都会发生以下情况正好有一个黏液吃掉它的一个邻居，并按照被吃邻居的大小来增加自己的大小。只有当一个粘液的体积严格大于它的邻居时，它才能吃掉它的邻居。如果没有严格意义上比它的邻居大的粘液，这个过程就结束了。