AtCoder Weekday Contest 0009 Beta题解（AWC 0009 Beta A-E）

Source

A - Total Shopping Amount

【题目来源】

【题目描述】

Takahashi is shopping at a supermarket.
高桥正在超市购物。

Takahashi has placed $K$ items in his shopping basket. Each item has a price tag, and the price of the $i$ -th item $\leq i \leq K)$ is $L_i$ yen.
高桥已在购物篮中放置了 $K$ 件商品。每件商品都有一个价格标签，第 $i$ 件商品（ $1 \leq i \leq K$ ）的价格为 $L_i$ 日元。

This supermarket is running a campaign where, at checkout, customers receive points equal to the remainder when the total amount is divided by a positive integer $M$ .
这家超市正在开展一项促销活动：在结账时，顾客获得的积分等于总金额除以一个正整数 $M$ 所得的余数。

That is, if the total sum of all item prices is $L_1 + L_2 + \cdots + L_K$ , the points Takahashi receives are the remainder when $S$ is divided by $M$ . Note that if $S$ is a multiple of $M$ , the points received are $0$ .
也就是说，如果所有商品价格的总和为 $S = L_1 + L_2 + ⋯ + L_K$ ，高桥获得的积分是 $S$ 除以 $M$ 的余数。注意，如果 $S$ 是 $M$ 的倍数，则获得的积分为 $0$ 。

Find the number of points Takahashi will receive.
求高桥将获得的积分数量。

【输入】

$K$ $M$
$L_1$ $L_2$ $\cdots$ $L_K$

The first line contains an integer $K$ representing the number of items in the shopping basket, and a positive integer $M$ used for the point calculation, separated by a space.
The second line contains $K$ integers $L_1, L_2, \ldots, L_K$ representing the prices of each item, separated by spaces.

【输出】

Print the number of points Takahashi will receive as an integer on a single line.

【输入样例】

3 100
150 80 45

【输出样例】

【解题思路】

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int k, m, ans;  // k: 数字个数，m: 模数，ans: 总和

int main()
{
    
      
    cin >> k >> m;  // 读入数字个数k和模数m
    
    for (int i = 1; i <= k; i++)  // 循环读取k个数字
    {
    
      
        int x;
        cin >> x;  // 读入第i个数字
        ans += x;  // 累加到总和
    }
    
    cout << ans % m << endl;  // 输出总和除以m的余数
    return 0;
}

【运行结果】

3 100
150 80 45
75

B - Dungeon Exploration

【题目来源】

AtCoder：B - Dungeon Exploration

【题目描述】

Takahashi challenges himself to explore a dungeon.
高桥挑战自己去探索一个地下城。

The dungeon has $N$ rooms arranged in a row. The $i$ -th room from the left contains $1$ monster. The $i$ -th monster has strength $H_i$ , and upon being defeated, it drops an item that restores $P_i$ health points.
地下城有 $N$ 个房间排成一行。从左数第 $i$ 个房间内有 $1$ 只怪物。第 $i$ 只怪物的力量为 $H_i$ ，被击败后会掉落一个恢复 $P_i$ 点生命值的物品。

Takahashi visits all rooms exactly once, from room $1$ to room $N$ in order of increasing room number. Takahashi’s initial health is $S$ . There is no upper limit on health.
高桥按房间编号递增的顺序访问所有房间各一次，从房间 $1$ 到房间 $N$ 。高桥的初始生命值为 $S$ 。生命值没有上限。

When visiting each room $i$ , the following rules are automatically applied. Takahashi has no choice in the matter.
当访问每个房间 $i$ 时，将自动应用以下规则。高桥对此没有选择权。

If his current health is greater than or equal to $H_i$ , Takahashi defeats the monster. First, his health decreases by $H_i$ , and immediately after, it recovers by $P_i$ . That is, the net change in health is $H_i + P_i$ . Since his health was at least $H_i$ just before the battle, it is guaranteed that his health is non-negative immediately after the $H_i$ decrease.
如果他的当前生命值大于或等于 $H_i$ ，高桥会击败怪物。首先，他的生命值减少 $H_i$ ，随后立即恢复 $P_i$ 。也就是说，生命值的净变化为 $H_i + P_i$ 。由于战斗前他的生命值至少为 $H_i$ ，保证在减少 $H_i$ 后其生命值非负。
If his current health is less than $H_i$ , Takahashi cannot defeat the monster and passes through the room. In this case, his health does not change.
如果他的当前生命值小于 $H_i$ ，高桥无法击败怪物并会穿过房间。这种情况下，他的生命值不变。

For each room where a monster was not defeated, Takahashi must pay a penalty of $C$ .
对于每个未击败怪物的房间，高桥必须支付 $C$ 的惩罚。

After visiting all $N$ rooms, determine the total penalty Takahashi must pay. That is, if the number of rooms where the monster was not defeated is $k$ , output $\times C$ .
访问完所有 $N$ 个房间后，确定高桥必须支付的总惩罚。也就是说，如果未击败怪物的房间数为 $k$ ，则输出 $k \times C$ 。

【输入】

$N$ $S$ $C$
$H_1$ $P_1$
$H_2$ $P_2$
$\vdots$
$H_N$ $P_N$

The first line contains $N$ representing the number of rooms, $S$ representing Takahashi’s initial health, and $C$ representing the penalty per room, separated by spaces.
From the 2nd line to the $(N + 1)$ -th line, information about each room is given over $N$ lines.
The $(1 + i)$ -th line contains the strength $H_i$ of the $i$ -th monster and the health recovery amount $P_i$ upon defeating that monster, separated by spaces.

【输出】

Output the total penalty Takahashi must pay, on a single line.

【输入样例】

【输出样例】

【解题思路】

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, s, c, ans;  // n: 物品数量，s: 初始容量/力量，c: 惩罚代价，ans: 总代价

signed main()
{
    
      
    cin >> n >> s >> c;  // 读入物品数量、初始容量/力量和惩罚代价
    
    for (int i = 1; i <= n; i++)  // 处理每个物品
    {
    
      
        int h, p;  // h: 需要消耗的容量/力量，p: 击败后获得的收益
        cin >> h >> p;  // 读入当前物品的消耗和收益
        
        if (s < h)  // 如果当前容量/力量不足以应对消耗
        {
    
      
            ans += c;  // 增加惩罚代价
        }
        else
        {
    
      
            s = s - h + p;  // 消耗h，获得p，更新当前容量/力量
        }
    }
    
    cout << ans << endl;  // 输出总代价
    return 0;
}

【运行结果】

C - Apple Harvest

【题目来源】

AtCoder：C - Apple Harvest

【题目描述】

Takahashi is working a part-time job harvesting apples at an orchard. The orchard has $N$ apples, each located at a different height on the tree.
高桥正在一家果园做采摘苹果的兼职工作。果园有 $N$ 个苹果，每个位于树上的不同高度。

The $i$ -th apple is at a height of $H_i$ centimeters from the ground. Takahashi’s height is $T$ centimeters, but by stretching on his toes, he can reach up to a maximum height of $T + K$ centimeters.
第 $i$ 个苹果距离地面的高度为 $H_i$ 厘米。高桥的身高是 $T$ 厘米，但通过踮起脚尖，他能够到的最大高度为 $T + K$ 厘米。

To harvest an apple, the apple’s height must be within his reach (at most $T + K$ centimeters). For apples he cannot reach, he would need to use a stepladder.
要收获一个苹果，该苹果的高度必须在他的可触及范围内（最多 $T + K$ 厘米）。对于他无法够到的苹果，他需要使用梯凳。

Since Takahashi finds using a stepladder troublesome, he wants to maximize the number of apples he can harvest by stretching alone. Fortunately, the trees in this orchard are planted in special mobile planters, and he can dig a hole of depth $D$ centimeters in the ground to sink an entire planter ( $D$ is any non-negative integer). When a tree is sunk, the heights of all its apples are uniformly reduced by $D$ .
由于高桥觉得使用梯凳很麻烦，他希望最大化仅通过踮脚就能收获的苹果数量。幸运的是，这个果园的树都种在特殊的可移动种植盆中，他可以在地面上挖一个深度为 $D$ 厘米的坑来降低整个种植盆（ $D$ 可以是任意非负整数）。当一棵树被降低时，其所有苹果的高度都会统一减少 $D$ 。

However, there is a constraint that the height of the lowest apple must not become less than $1$ centimeter. In other words, for all $i$ , the condition $H_i - D \geq 1$ must be satisfied.
然而，有一个约束条件：最低苹果的高度不得低于 $1$ 厘米。换言之，对于所有 $i$ ，必须满足条件 $H_i - D ≥ 1$ 。

Find the maximum number of apples Takahashi can harvest by stretching alone.
求高桥仅通过踮脚就能收获的最大苹果数量。

【输入】

$N$ $T$ $K$
$H_1$ $H_2$ $\ldots$ $H_N$

The first line contains the number of apples $N$ , Takahashi’s height $T$ , and the additional height $K$ he can reach by stretching, separated by spaces.
The second line contains the heights of each apple $H_1, H_2, \ldots, H_N$ , separated by spaces.

【输出】

Print the maximum number of apples Takahashi can harvest by stretching alone, in a single line.

【输入样例】

5 150 30
100 160 180 200 250

【输出样例】

【解题思路】

【代码详解】

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, t, k, minn = 1e9;  // n: 数量，t: 基础值，k: 附加值，minn: 最小值
int h[N], ans;  // h: 高度数组，ans: 符合条件的数量

int main()
{
    
      
    cin >> n >> t >> k;  // 读入数量、基础值和附加值
    for (int i = 1; i <= n; i++)
    {
    
      
        cin >> h[i];  // 读入每个高度
        minn = min(minn, h[i]);  // 更新最小值
    }
    
    int D = minn - 1;  // 计算偏移量D = 最小值-1
    
    for (int i = 1; i <= n; i++)
    {
    
      
        // 判断条件：t+k ≥ (h[i]-D)
        if (t + k >= h[i] - D)
        {
    
      
            ans++;  // 计数加1
        }
    }
    
    cout << ans << endl;  // 输出结果
    return 0;
}

【运行结果】

5 150 30
100 160 180 200 250
5

D - Planting Flower Seeds

【题目来源】

AtCoder：D - Planting Flower Seeds

【题目描述】

Takahashi is trying to plant $N$ flower seeds in his garden.
高桥正尝试在他的花园里种植 $N$ 粒花种。

Days are numbered as day $1$ , day $2$ , and so on. Starting from day $1$ , Takahashi decides for each day whether he can plant a seed or not.
日期编号为第 $1$ 天、第 $2$ 天，依此类推。从第 $1$ 天开始，高桥每天决定他是否能种植一粒种子。

According to the weather forecast, there are $M$ rainy periods scheduled. The $i$ -th rainy period lasts from day $L_i$ to day $R_i$ (inclusive). A day is a rainy day if it is included in at least one of the $M$ rainy periods. On rainy days, the ground is muddy and work cannot be done, so no seeds can be planted. On days that are not rainy, exactly $1$ seed is planted.
根据天气预报，有 $M$ 个雨天时段预定。第 $i$ 个雨天时段从第 $L_i$ 天持续到第 $R_i$ 天（包含两端）。如果一天包含在至少一个雨天时段中，则该天为雨天。在雨天，地面泥泞无法工作，因此不能种植任何种子。在非雨天，恰好种植 $1$ 粒种子。

Note that rainy periods may overlap with each other or one may be entirely contained within another. Even in such cases, any day that falls within any rainy period is treated as a rainy day.
注意，雨天时段可能相互重叠，或者一个时段可能完全包含在另一个时段内。即使在这些情况下，任何落在任一雨天时段内的日子都被视为雨天。

Since the rainy periods are finite, all days after the last rainy period ends will be sunny, and given enough days, all seeds will eventually be planted.
由于雨天时段是有限的，最后一个雨天时段结束后的所有日子都将是晴天，并且只要给足够的天数，所有种子最终都将被种植。

Determine on which day all $N$ seeds will have been planted.
确定在哪一天所有 $N$ 粒种子都将被种植完毕。

【输入】

$N$ $M$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

The first line contains an integer $N$ representing the number of seeds to plant and an integer $M$ representing the number of rainy periods, separated by a space.
The following $M$ lines provide information about each rainy period. The $(1 + i)$ -th line contains the start day $L_i$ and end day $R_i$ of the $i$ -th rainy period, separated by a space. This means it rains from day $L_i$ to day $R_i$ (inclusive).

【输出】

Print on a single line the day number on which all $N$ seeds have been planted.

【输入样例】

5 2
2 4
7 7

【输出样例】

【解题思路】

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 100005;
int n, m;  // n: 目标值/总天数，m: 区间数量
struct Node
{
    
      
    int l, r;  // 区间的左右端点
}a[N], b[N];  // a: 原始区间数组，b: 备用数组（未使用）

// 比较函数：先按左端点升序，再按右端点升序
bool cmp(Node x, Node y)
{
    
      
    if (x.l != y.l)
    {
    
      
        return x.l < y.l;
    }
    return x.r < y.r;
}

signed main()
{
    
      
    cin >> n >> m;  // 读入目标值和区间数量
    for (int i = 1; i <= m; i++)
    {
    
      
        cin >> a[i].l >> a[i].r;  // 读入每个区间
    }
    
    // 将区间按左端点排序
    sort(a + 1, a + m + 1, cmp);
    
    int st = 0, ed = 0, cnt = 0;  // st: 当前合并区间的起点，ed: 终点，cnt: 计数

    for (int i = 1; i <= m; i++)
    {
    
      
        if (a[i].l <= ed)  // 如果当前区间与已合并区间有重叠
        {
    
      
            ed = max(ed, a[i].r);  // 合并区间，更新右端点
        }
        else  // 如果当前区间与已合并区间不重叠
        {
    
      
            // 判断是否还能添加间隙
            if (cnt + (a[i].l - ed - 1) < n)
            {
    
      
                cnt += a[i].l - ed - 1;  // 增加间隙长度到计数
                st = a[i].l;  // 更新当前区间的起点
                ed = a[i].r;  // 更新当前区间的终点
            }
            else  // 如果不能再添加间隙
            {
    
      
                cout << n - cnt + ed << endl;  // 输出结果
                return 0;
            }
        }
    }
    cout << n - cnt + ed << endl;  // 输出最终结果
    return 0;
}

【运行结果】

E - Temperature Fluctuation Survey

【题目来源】

AtCoder：E - Temperature Fluctuation Survey

【题目描述】

Takahashi is working a part-time job at a weather observatory. His job is to analyze past temperature data.
高桥正在一家气象观测站做兼职工作。他的工作是分析过去的气温数据。

The observatory has temperature records for $N$ days. Each day is numbered from $1$ to $N$ , and the temperature on day $i$ was $A_i$ ℃.
观测站拥有 $N$ 天的气温记录。每天编号从 $1$ 到 $N$ ，且第 $i$ 天的气温为 $A_i$ ℃。

Takahashi’s supervisor asked him to investigate the temperature fluctuation range within specified periods. Here, the temperature fluctuation range of a certain period refers to the difference between the maximum and minimum temperatures within that period. For example, if the period consists of only 1 day, the fluctuation range is $0$ .
高桥的上司要求他调查指定时间段内的气温波动范围。此处，某个时间段的气温波动范围指该时间段内最高气温与最低气温的差值。例如，如果该时间段仅包含 $1$ 天，则波动范围为 $0$ 。

$Q$ queries are given. In the $i$ -th query ( $\ldots, Q$ ), two integers $L_i, R_i$ are specified. Takahashi must determine and report the temperature fluctuation range in the period from day $L_i$ to day $R_i$ (inclusive).
给出了 $Q$ 条查询。在第 $i$ 条查询（ $i = 1, 2, \dots, Q$ ）中，指定了两个整数 $L_i, R_i$ 。高桥必须确定并报告从第 $L_i$ 天到第 $R_i$ 天（包含两端）这段时间内的气温波动范围。

For each query, find the temperature fluctuation range within the specified period.
对于每条查询，求指定时间段内的气温波动范围。

【输入】

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

The first line contains an integer $N$ representing the number of days and an integer $Q$ representing the number of queries, separated by a space.
The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ representing the temperature on each day, separated by spaces.
The $i$ -th of the following $Q$ lines ( $\ldots, Q$ ) contains the start day $L_i$ and end day $R_i$ of the period for the $i$ -th query, separated by a space.

【输出】

Print $Q$ lines. The $i$ -th line ( $\ldots, Q$ ) should contain the answer to the $i$ -th query, that is, the difference between the maximum and minimum values among $A_{L_i}, A_{L_i+1}, \ldots, A_{R_i}$ , as an integer.

【输入样例】

5 3
20 18 25 22 19
1 3
2 5
4 4

【输出样例】

7
7
0

【解题思路】

【代码详解】

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, q;  // n: 数组长度，q: 查询次数
int a[N], w[N];  // a: 未使用，w: 原始数组

// 线段树节点
struct Node
{
    
      
    int l, r;  // 节点覆盖的区间[l, r]
    int dt, mn, mx;  // dt: 懒标记，mn: 区间最小值，mx: 区间最大值
}tr[N * 4];

// 上推操作：用子节点信息更新父节点
void pushup(int u)
{
    
      
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
    tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx);
}

// 下推操作：将父节点的懒标记传递给子节点
void pushdown(int u)
{
    
      
    auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    l.dt += root.dt, l.mn += root.dt;
    r.dt += root.dt, r.mn += root.dt;
    l.mx += root.dt;  
    r.mx += root.dt; 
    root.dt = 0;
}

// 构建线段树
void build(int u, int l, int r)
{
    
      
    if (l == r)
    {
    
      
        tr[u] = {
    
      l, r, 0, w[l], w[l]};
    }
    else
    {
    
      
        tr[u] = {
    
      l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

// 区间更新：在[l, r]区间上增加d
void update(int u, int l, int r, int d)
{
    
      
    if (tr[u].l >= l && tr[u].r <= r)  // 完全包含
    {
    
      
        tr[u].dt += d, tr[u].mn += d, tr[u].mx += d;
    }
    else
    {
    
      
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)
        {
    
      
            update(u << 1, l, r, d);
        }
        if (r > mid)
        {
    
      
            update(u << 1 | 1, l, r, d);
        }
        pushup(u);
    }
}

// 查询区间最小值
int query_mn(int u, int l, int r)
{
    
      
    if (tr[u].l >= l && tr[u].r <= r)  // 完全包含
    {
    
      
        return tr[u].mn;
    }
    else
    {
    
      
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 1e9;  // 初始化为大数
        if (l <= mid)
        {
    
      
            res = query_mn(u << 1, l, r);
        }
        if (r > mid)
        {
    
      
            res = min(res, query_mn(u << 1 | 1, l, r));
        }
        return res;
    }
}

// 查询区间最大值
int query_mx(int u, int l, int r)
{
    
      
    if (tr[u].l >= l && tr[u].r <= r)  // 完全包含
    {
    
      
        return tr[u].mx;
    }
    else
    {
    
      
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int res = -1e9;  // 初始化为小数
        if (l <= mid)
        {
    
      
            res = query_mx(u << 1, l, r);
        }
        if (r > mid)
        {
    
      
            res = max(res, query_mx(u << 1 | 1, l, r));
        }
        return res;
    }
}

int main()
{
    
      
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
    
      
        cin >> w[i];
    }
    build(1, 1, n);
    
    while (q--)
    {
    
      
        int l, r;
        cin >> l >> r;
        // 输出区间[l, r]的最大值与最小值的差
        cout << query_mx(1, l, r) - query_mn(1, l, r) << endl;
    }
    return 0;
}

【运行结果】

5 3
20 18 25 22 19
1 3
7
2 5
7
4 4
0