USACO 2023 February Contest, Bronze

[USACO23FEB] Hungry Cow B

题目描述

Bessie 是一头饥饿的奶牛。每天晚餐时，如果谷仓中有干草，她会吃掉一捆干草。为了防止 Bessie 挨饿，有些天 Farmer John 会在早晨（晚餐之前）送来一些干草。具体地说，在第 $d_{i}$ 天，Farmer John 送来了 $b_{i}$ 捆干草（ $1 \leq d_{i} \leq 10^{14}, 1 \leq b_{i} \leq 10^{9}$ ）。

请计算 Bessie 在前 $T$ 天内共吃掉了多少捆干草。

输入格式

第一行包含两个整数 $N$ 和 $T$ （ $1 \leq N \leq 10^{5}, 1 \leq T \leq 10^{14}$ ）。

接下来的 $N$ 行每行包含两个整数 $d_{i}$ 和 $b_{i}$ 。保证 $1 \leq d_{1} < d_{2} < \dots < d_{N} \leq T$ 。

输出格式

输出 Bessie 在前 $T$ 天内吃掉的干草总数。

注意，本题中涉及的整数可能非常大，可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

样例 1 的解释

第 $1$ 天早晨到达 $2$ 捆干草。Bessie 在第 $1$ 天晚餐时吃掉 $1$ 捆，在第 $2$ 天晚餐时吃掉 $1$ 捆。在第 $3 \dots 5$ 天，没有干草供 Bessie 吃。在前 $5$ 天中，Bessie 共吃掉 $2$ 捆干草。

样例 2 的解释

第 $1$ 天早晨到达 $2$ 捆干草。Bessie 在第 $1$ 天和第 $2$ 天各吃掉 $1$ 捆。在第 $3$ 天和第 $4$ 天，没有干草供 Bessie 吃。第 $5$ 天早晨到达 $10$ 捆干草。Bessie 在第 $5$ 天晚餐时吃掉 $1$ 捆。在前 $5$ 天中，Bessie 共吃掉 $3$ 捆干草。

样例 3 的解释

第 $1$ 天早晨到达 $10$ 捆干草。Bessie 在第 $1 \dots 4$ 天各吃掉 $1$ 捆。第 $5$ 天早晨又到达 $10$ 捆干草，此时谷仓中共有 $16$ 捆干草。Bessie 在第 $5$ 天晚餐时再吃掉 $1$ 捆。在前 $5$ 天中，Bessie 共吃掉 $5$ 捆干草。

评分

输入 $4 - 7$ ： $T \leq 10^{5}$
输入 $8 - 13$ ：无额外限制。

输入输出样例 #1

输入 #1

1 5
1 2

输出 #1

输入输出样例 #2

输入 #2

2 5
1 2
5 10

输出 #2

输入输出样例 #3

输入 #3

2 5
1 10
5 10

输出 #3

解题思路

按照送草的时间顺序处理每次送草
对于每次送草，我们需要计算从上次送草到这次送草期间Bessie能吃掉多少干草
Bessie每天只能吃一捆草，所以两次送草之间最多能吃的草是这段时间的天数
但如果谷仓中的草不够，那么只能吃现有的草
因此，两次送草之间能吃的草 = min(当前谷仓中的草，两次送草之间的天数)
最后处理从最后一次送草到第t天的情况，计算方式类似
这个解法高效地处理了题目中可能存在的大数据范围（天数和草的数量都可能很大），时间复杂度是O(n)，其中n是送草的次数。

代码示例

c++

#include<bits/stdc++.h>
using namespace std;
long long n,t,sum,ans,pos,d[100010],b[100010];
int main(){
    // 读入 n 和 t，n表示送草次数，t表示总天数
    scanf("%lld%lld",&n,&t);
    // d[i]表示第i次送草的日期，b[i]表示第i次送草的数量
    // sum表示当前谷仓中剩余的干草数量
    // ans表示Bessie已经吃掉的干草数量
    for(long long i=1;i<=n;i++){
        scanf("%lld%lld",&d[i],&b[i]);
        // 计算从上次送草到这次送草期间能吃掉的最大干草数
        // 最多能吃掉的草是min(当前谷仓中的草，两次送草之间的天数)
        pos=min(sum,d[i]-d[i-1]);
        // 更新谷仓中剩余的草和已经吃掉的草
        sum-=pos;  // 减去吃掉的草
        ans+=pos;  // 增加已吃草的总数
        sum+=b[i]; // 加上这次送来的草
    }
    // 处理最后一次送草后到第t天的情况
    // 最多能吃掉的草是min(剩余的草，从最后一次送草到第t天的天数)
    // 注意这里是t-d[n]+1，因为包括第d[n]天本身也可以吃草
    printf("%lld",ans+min(sum,t-d[n]+1));
    return 0;
}

[USACO23FEB] Stamp Grid B

题目描述

盖章绘画是一幅黑白画，绘制在一个 $N \times N$ 的画布上，其中某些格子被涂黑，而其他格子为空白。它可以用一个 $N \times N$ 的字符数组表示（ $1 \leq N \leq 20$ ）。如果数组的第 $i$ 行第 $j$ 列的值为 *，说明该格子被涂黑；如果为 .，则说明该格子为空白。

Bessie 想要完成一幅盖章绘画，因此 Farmer John 借给了她一块 $K \times K$ （ $1 \leq K \leq N$ ）的盖章，以及一块空的 $N \times N$ 画布。Bessie 可以将盖章顺时针旋转 $90^{\circ}$ ，并在画布上的任意位置盖章，只要盖章完全在画布范围内即可。形式化地说，盖章时，Bessie 选择整数 $i, j$ ，满足 $i \in [1, N - K + 1]$ 且 $j \in [1, N - K + 1]$ ；对于每个 $(i^{'}, j^{'})$ ，其中 $1 \leq i^{'}, j^{'} \leq K$ ，画布上的格子 $(i + i^{'} - 1, j + j^{'} - 1)$ 会被涂黑，如果盖章在 $(i^{'}, j^{'})$ 处有墨迹。Bessie 可以在每次盖章之前旋转盖章。一旦画布上的某个格子被涂黑，就会保持涂黑状态。

Farmer John 想知道，Bessie 是否可以用他的盖章完成她想要的盖章绘画。对于每个 $T$ （ $1 \leq T \leq 100$ ）个测试用例，帮助 Farmer John 回答这个问题。

输入格式

第一行包含一个整数 $T$ ，表示测试用例的数量。

每个测试用例以一个整数 $N$ 开始，接下来是 $N$ 行，每行包含由 * 和 . 构成的字符串，表示 Bessie 想要的盖章绘画。接下来的行包含一个整数 $K$ ，随后是 $K$ 行，每行包含由 * 和 . 构成的字符串，表示 Farmer John 的盖章。

相邻的测试用例之间用空行分隔。

输出格式

对于每个测试用例，输出一行 YES 或 NO。

样例 1 的解释

在第一个测试用例中，Bessie 可以按以下顺序完成盖章：

在 $(1, 1)$ 处盖章
在 $(1, 2)$ 处盖章
在 $(2, 1)$ 处盖章

在第二个测试用例中，Bessie 可以按以下顺序完成盖章：

在 $(2, 2)$ 处盖章
在 $(2, 1)$ 处盖章
顺时针旋转 $90^{\circ}$
顺时针旋转 $90^{\circ}$
在 $(1, 2)$ 处盖章

在第三个测试用例中，无法涂黑中间格子，因此无法完成绘画。

在第四个测试用例中，Bessie 可以按以下顺序完成盖章：

顺时针旋转 $90^{\circ}$
在 $(1, 1)$ 处盖章
在 $(1, 2)$ 处盖章
在 $(2, 2)$ 处盖章

输入输出样例 #1

输入 #1

4

2
**
*.
1
*

3
.**
.**
***
2
.*
**

3
...
.*.
...
3
.*.
...
...

3
**.
.**
..*
2
.*
*.

输出 #1

YES
YES
NO
YES

解题思路：

基本策略是枚举盖章的所有可能旋转方向和位置，记录每次盖章能涂黑的格子。
对每种旋转方向（共4种，旋转0°、90°、180°、270°）：
- 对每个可能的起始位置(i,j)尝试盖章
- 检查盖章是否合法：盖章上的黑点只能对应目标绘画中的黑点（不能把应该是白色的格子涂黑）
- 如果合法，则标记这些格子已被涂黑
尝试所有可能的盖章后，检查目标绘画中的所有黑点是否都已被标记为涂黑。

这个方法的关键点是：

盖章可以重复使用
一旦格子被涂黑就保持涂黑状态
盖章必须完全在画布范围内
只有当盖章上的黑点对应到目标绘画中的黑点时，才能在该位置盖章
顺时针旋转90°
以你给出的3×3矩阵为例：
```
1 2 3
4 5 6
7 8 9
```
1
2
3
旋转90度后变成：
```
7 4 1
8 5 2
9 6 3
```
1
2
3
让我们验证几个点：
- 左上角 (1,1) 的元素"1"，新位置为 (1,3)，即 (y,m-x+1) = (1,3-1+1) = (1,3)
- 右上角 (1,3) 的元素"3"，新位置为 (3,3)，即 (y,m-x+1) = (3,3-1+1) = (3,3)
- 左下角 (3,1) 的元素"7"，新位置为 (1,1)，即 (y,m-x+1) = (1,3-3+1) = (1,1)
- 中心点 (2,2) 的元素"5"，新位置为 (2,2)，即 (y,m-x+1) = (2,3-2+1) = (2,2)
矩阵旋转的图形理解
想象一个坐标系，原点在矩阵的左上角：
- x轴向下，表示行号
- y轴向右，表示列号
当矩阵顺时针旋转90度时：
1. 原本的行变成列，所以新的第一个坐标是原来的y
2. 原本的第一行变成最右列，第二行变成倒数第二列...
所以新的第二个坐标需要做变换：m-x+1
所以公式 (x,y) -> (y,m-x+1) 正是捕捉了这种旋转关系，确保了每个元素都旋转到了正确的位置。

代码示例

c++

#include <iostream>
using namespace std;
int T, n, k;
// a数组存储目标盖章绘画
// c数组存储当前的盖章
// d数组存储我们已经涂黑的格子
// t数组用于临时存储旋转后的盖章
char a[25][25], c[25][25], d[25][25], t[25][25];

/**
 * @description 将盖章顺时针旋转90度
 */
void change() {
    // 旋转90度的算法：将行列坐标进行变换
    // 新行 = 旧列，新列 = k - 旧行 + 1
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) t[i][j] = c[k - j + 1][i];
    }
    // 将旋转后的结果复制回c数组
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) c[i][j] = t[i][j];
    }
}

/**
 * @description 尝试在(x,y)位置盖章
 * @param {int} x - 盖章左上角的行坐标
 * @param {int} y - 盖章左上角的列坐标
 */
void paint(int x, int y) {
    // 首先检查：如果盖章会涂黑一个不能涂黑的格子，则不能盖章
    for (int i = x; i <= x + k - 1; i++) {
        for (int j = y; j <= y + k - 1; j++) 
            if (c[i - x + 1][j - y + 1] == '*' && a[i][j] != '*') return;
    }
    
    // 执行盖章操作，将盖章上有墨迹的格子对应的画布格子涂黑
    for (int i = x; i <= x + k - 1; i++) {
        for (int j = y; j <= y + k - 1; j++) 
            if (c[i - x + 1][j - y + 1] == '*') {
                d[i][j] = '*'; // 记录已涂黑的格子
            }
    }
}

/**
 * @description 检查是否所有目标格子都已涂黑
 */
void check() {
    // 检查目标绘画中的所有黑格子是否都已被涂黑
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) if (a[i][j] == '*' && d[i][j] != '*') {
            // 如果有格子应该是黑色但没有被涂黑，则无法完成
            cout << "NO" << "\n";
            return;
        }
    }
    // 所有目标格子都已涂黑，可以完成
    cout << "YES" << "\n";
}

int main() {
    cin >> T; // 读入测试用例数量
    while (T--) {
        // 读入目标绘画的大小和内容
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> a[i][j]; // 读入目标绘画
                d[i][j] = '.';  // 初始化已涂黑格子数组
            }
        }
        
        // 读入盖章的大小和内容
        cin >> k;
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= k; j++) cin >> c[i][j];
        }
        
        // 尝试4种旋转方向
        for (int i = 1; i <= 4; i++) {
            change(); // 旋转盖章
            // 尝试在画布上所有可能的位置盖章
            for (int i = 1; i <= n - k + 1; i++) {
                for (int j = 1; j <= n - k + 1; j++) paint(i, j);
            }
        }
        
        // 检查是否成功完成
        check();
    }
    return 0;
}

[USACO23FEB] Watching Mooloo B

题目描述

贝茜喜欢看 Mooloo 的演出。因为她是一只忙碌的奶牛，她计划在接下来的 $N (1 \leq N \leq 10^{5})$ 天去看演出。因为 Mooloo 提供了订阅服务，她想要使她花费的钱最少。

Mooloo 有一个有趣的订阅服务系统：若要在此之后的连续 $d$ 天看演出，则在订阅时需要花费 $d + K (1 \leq K \leq 10^{9})$ 个单位价格。你可以随时订阅；若本次订阅已经过期，你可以根据需要订阅多次。基于以上条件，请计算出贝茜最少要花费多少个单位价格，才能完成她的计划。

输入格式

第一行输入两个正整数 $N$ 和 $K$ 。

第二行输入 $N$ 个正整数，表示在这些天里，贝茜会看 Mooloo 的演出： $1 \leq d_{1} < d_{2} < \dots < d_{N} \leq 10^{14}$ 。

输出格式

请注意，此问题中可能需要使用 64 位整数数据类型（如 C 或 C++ 中的 long long）。

样例 #1 解释

贝茜在第 $7$ 天时，购买了 $3$ 天的订阅，共花费 $d + K = 3 + 4 = 7$ 个单位价格。

样例 #2 解释

贝茜在第 $1$ 天时，购买了 $1$ 天的订阅，花费 $d + K = 1 + 3 = 4$ 个单位价格；在第 $10$ 天时，也购买了 $1$ 天的订阅，花费 $d + K = 1 + 3 = 4$ 个单位价格。贝茜一共花费了 $8$ 个单位价格。

translated by liyuanchen2021

输入输出样例 #1

输入 #1

2 4
7 9

输出 #1

输入输出样例 #2

输入 #2

2 3
1 10

输出 #2

解题思路

这道题的思路是：

贝茜需要在特定的几天观看演出，我们需要计算最小的订阅成本。
订阅系统的成本是：连续d天的订阅费用为d+K。
关键问题是判断什么时候应该延长现有订阅，什么时候应该购买新的订阅。

代码的核心逻辑是：

如果两次演出的间隔天数不超过K，那么延长现有订阅比购买新订阅更划算。延长的成本是间隔的天数。
如果间隔大于K，那么购买新订阅更划算。新订阅的成本是1+K（1是第一天的成本，K是固定成本）。

具体实现中：

外层循环i表示当前考虑的演出天（初始索引）。
内层循环j表示尝试延长订阅覆盖的演出天。
tmp记录当前订阅可以覆盖到哪一天（索引）。
当决定购买新订阅时，累加基本成本(1+K)，并更新i=tmp来跳过已经覆盖的天数。

这种贪心策略确保了在每个决策点上都选择了最优解，从而得到全局最优解——最小的总订阅成本。

代码示例

c++

#include<iostream>
using namespace std;
long long n,k,a[100001],ans,tmp;
int main(){
    // 输入n和k，n表示贝茜计划看演出的天数，k是订阅系统的固定成本
    cin>>n>>k;
    // 输入贝茜计划看演出的n天
    for(int i=1;i<=n;i++) cin>>a[i];
    
    // 遍历每一天
    for(int i=1;i<=n;i++){
        // tmp用于记录当前订阅可以覆盖到哪一天（索引）
        tmp=i; 
        // 从下一天开始，检查是否应该延长当前订阅
        for(int j=i+1;j<=n;j++){
            // 如果两次演出的间隔小于等于k，则延长订阅比重新购买更划算
            if(a[j]-a[j-1]<=k){
                // 延长订阅的成本是两次演出之间的天数差
                ans+=a[j]-a[j-1];
                // 更新当前订阅覆盖的最后一天
                tmp++;
            }
            else break; // 如果间隔大于k，重新购买更划算，跳出循环
        }
        // 每次新订阅的基本成本：1（第一天）+ k（固定成本）
        ans++;
        ans+=k;
        // 更新i为当前订阅覆盖的最后一天，下次循环从这之后开始考虑
        i=tmp;
    }
    
    // 输出最小花费
    cout<<ans;
}

USACO 2023 February Contest, Bronze ​

[USACO23FEB] Hungry Cow B ​

题目描述 ​

输入格式 ​

输出格式 ​

样例 1 的解释 ​

样例 2 的解释 ​

样例 3 的解释 ​

评分 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

输入输出样例 #2 ​

输入 #2 ​

输出 #2 ​

输入输出样例 #3 ​

输入 #3 ​

输出 #3 ​

解题思路 ​

代码示例 ​

[USACO23FEB] Stamp Grid B ​

题目描述 ​

输入格式 ​

输出格式 ​

样例 1 的解释 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

解题思路： ​

矩阵旋转的图形理解 ​

代码示例 ​

[USACO23FEB] Watching Mooloo B ​

题目描述 ​

输入格式 ​

输出格式 ​

样例 #1 解释 ​

样例 #2 解释 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

输入输出样例 #2 ​

输入 #2 ​

输出 #2 ​

解题思路 ​

代码示例 ​

USACO 2023 February Contest, Bronze

[USACO23FEB] Hungry Cow B

题目描述

输入格式

输出格式

样例 1 的解释

样例 2 的解释

样例 3 的解释

评分

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

输入输出样例 #3

输入 #3

输出 #3

解题思路

代码示例

[USACO23FEB] Stamp Grid B

题目描述

输入格式

输出格式

样例 1 的解释

输入输出样例 #1

输入 #1

输出 #1

解题思路：

矩阵旋转的图形理解

代码示例

[USACO23FEB] Watching Mooloo B

题目描述

输入格式

输出格式

样例 #1 解释

样例 #2 解释

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

解题思路

代码示例