USACO 2024 December Contest 青铜级 题解

USACO 2024 December Contest 青铜级

1.Roundabout Rounding

描述

奶牛 Bessie 回到学校了！她开始做她的数学作业，在作业中她被要求将正整数四舍五入到 10 的幂。

要将一个正整数 a 四舍五入到最接近的 10b，其中 b 为正整数，Bessie 首先找到从右往左数第 b 个数位。令 x 为这个数位。

如果 x≥5，Bessie 将 a 增加 10b。

然后，Bessie 将从右侧开始直至第 b 个数位的所有数位均设置为 0。

例如，如果 Bessie 想要将 456 四舍五入到最接近的 102（百位），Bessie 会首先找到从右往左数第 2 个数位 5。这意味着 x=5。然后由于 x≥5，Bessie 将 a 增加 100。最后，Bessie 将 a 中从右侧开始直至第 2 个数位的所有数位设置为 0，结果为 500。

但是，如果 Bessie 将 446 四舍五入到最接近的 102，她将得到 400。

在看了 Bessie 的作业后，Elsie 认为她已经发明了一种新的舍入方式：链式舍入。要链式舍入到最接近的 10b，Elsie 将首先舍入到最接近的 101，然后舍入到最接近的 102
，以此类推，直至舍入到最接近的 10b。

Bessie 认为 Elsie 是错误的，但她太忙于数学作业，无法确认她的怀疑。她请你计算出存在多少个不小于 2 且不超过 N 的整数 x（1≤N≤109），使得将 x 四舍五入到最接近的 10P 与链式舍入到最接近的 10P 的结果不同，其中 P 是满足 10P≥x 的最小整数。

输入描述

输入的第一行包含一个整数 T（1≤T≤105），为测试用例的数量。以下是 T 个测试用例。

每个测试用例的输入仅有一行，包含一个整数 N。输入保证同一测试点中的所有 N 各不相同。

输出描述

输出 T 行，第 i 行包含第 i 个测试用例的答案。每行包含一个整数，表示存在多少个不小于 2 且不超过 N 的整数在使用两种舍入方法时会得到不同的结果。

用例输入 1 

4
1
100
4567
3366

用例输出 1 

0
5
183
60

样例解释

考虑样例中的第二个测试用例。48 应当被计算在内，因为 48 链式舍入到最接近的 102 是 100（48→50→100），但 48 四舍五入到最接近的 102 是 0。

在第三个测试用例中，48 和 480 是两个被计算在内的整数。48 链式舍入到 100 而不是 0，480 链式舍入到 1000 而不是 0。但是，67 不被计算在内，因为它链式舍入到 100，与 67 四舍五入到最接近的 102 相同。

测试点性质

• 测试点 1：样例。
• 测试点 2-4：N≤103。
• 测试点 5-7：N≤106。
• 测试点 8-13：没有额外限制。

以下是USACO官网给出的答案

#include <iostream>
#include <vector>

//determines the length of the intersection of [a, b] with [c, d]
int isect(int a, int b, int c, int d) {
    int lb = std::max(a, c);
    int ub = std::min(b, d);
    return std::max(0, ub - lb + 1);
}

int solve(int n) {
    int is = 5, ie = 49;
    int tp = 1;
    int ans = 0;
    while (tp < 100000000) {
        tp *= 10;
        is += 4 * tp;
        ie = 5 * tp - 1;
        ans += isect(is, ie, 2, n);
    }
    return ans;
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        int n;
        std::cin >> n;
        std::cout << solve(n) << "\n";
    }
}

2.Farmer John's Cheese Block

描述

Farmer John 有一块立方体形状的奶酪，它位于三维坐标空间中，从 (0,0,0) 延伸至 (N,N,N)（2≤N≤1000）。Farmer John 将对他的奶酪块执行一系列 Q（1≤Q≤2⋅105）次更新操作。

对于每次更新操作，FJ 将从整数坐标 (x,y,z) 到 (x+1,y+1,z+1) 处切割出一个 1×1×1 的奶酪块，其中 0≤x,y,z<N。输入保证在 FJ 切割的位置上存在一个 1×1×1 的奶酪块。由于 FJ 正在玩牛的世界，当下方的奶酪被切割后，重力不会导致上方的奶酪掉落。

在每次更新后，输出 FJ 可以将一个 1×1×N 的砖块插入奶酪块中的方案数，使得砖块的任何部分都不与剩余的奶酪重叠。砖块的每个顶点在全部三个坐标轴上均必须具有整数坐标，范围为 [0,N]。FJ 可以随意旋转砖块。

输入描述

输入的第一行包含 N 和 Q。

以下 Q 行包含 x，y 和 z，为要切割的位置的坐标。

输出描述

在每次更新操作后，输出一个整数，为所求的方案数。

用例输入 1

2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0

用例输出 1

0
0
1
2
5

样例解释

在前三次更新操作后，[0,1]×[0,2]×[0,1] 范围的 1×2×1 砖块与剩余的奶酪不重叠，因此它贡献了答案。

测试点性质

• 测试点 1：样例。
• 测试点 2-4：N≤10 且 Q≤1000。
• 测试点 5-7：N≤100 且 Q≤1000。
• 测试点 8-16：没有额外限制。

以下是USACO官网给出的答案

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n, q;
    cin >> n >> q;
 
    vector<vector<vector<int>>> cnt(3, vector<vector<int>>(n, vector<int>(n, n)));
    int ans = 0;
 
    while (q--){
        int x, y, z;
        cin >> x >> y >> z;
 
        for (auto [dim, a, b] : {array<int, 3>{0, y, z}, array<int, 3>{1, x, z}, array<int, 3>{2, x, y}})
            if (!(--cnt[dim][a][b]))
                ans++;
        
        cout << ans << "\n";
    }
}

3.It's Mooin' Time

描述

Farmer John 正在试图向 Elsie 描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。他说「竞赛中我最喜欢的部分是 Bessie 说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。

Elsie 仍然不理解，所以 Farmer John 将竞赛以文本文件形式下载，并试图解释他的意思。竞赛被定义为一个长度为 N（3≤N≤20000）的小写字母字符串。一种哞叫一般地定义为子串 ci​cj​cj​，其中某字符 ci​ 之后紧跟着 2 个某字符 cj​，且 ci​=cj​。根据 Farmer John 的说法，Bessie 哞叫了很多，所以如果某种哞叫在竞赛中出现了至少 F（1≤F≤N）次，那可能就是 Bessie 发出的。

然而，Farmer John 的下载可能损坏，文本文件可能存在至多一个字符与原始文件不同。将可能的误差考虑在内，输出所有可能是 Bessie 发出的哞叫，按字典序顺序排序。

输入描述

输入的第一行包含 N 和 F，表示字符串的长度以及 Bessie 的哞叫的频次下限。

第二行包含一个长度为 N 的小写字母字符串，表示竞赛。

输出描述

输出可能是 Bessie 发出的哞叫的数量，以下是按字典序排序的哞叫列表。每行输出一种哞叫。

用例输入 1 

10 2
zzmoozzmoo

用例输出 1 

1
moo

用例输入 2 

17 2
momoobaaaaaqqqcqq

用例输出 2 

3
aqq
baa
cqq

用例输入 3 

3 1
ooo

用例输出 3 

25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
zoo

样例 #1 解释

在这个样例中，任何字符变化都不会影响答案。唯一 Bessie 可能发出的哞叫是 moo。

样例 #2 解释

在这个样例中，位置 8（从零开始索引）的 a 可能是由 b 损坏导致的，这使得 baa 成为一种 Bessie 发出两次的可能的哞叫。此外，位置 11 的 q 可能是由 c 损坏导致的，这使得 cqq 成为一种 Bessie 可能的哞叫。aqq 可以通过将 c 换成 a 来达到。

测试点性质

• 测试点 1-3：样例。
• 测试点 4-8：N≤100。
• 测试点 9-13：没有额外限制。

以下是USACO官网给出的答案

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n, f;
    string S;
    cin >> n >> f >> S;
 
    map<string, int> occ;
    set<string> ans;
 
    auto chk = [&](int i){
        if (i < 0 or i + 2 >= n)
            return false;
            
        return (S[i] != S[i + 1] and S[i + 1] == S[i + 2]);
    };
    auto updPoint = [&](int i, int delta){
        if (!chk(i))
            return;
        
        string t = S.substr(i, 3);
 
        occ[t] += delta;
 
        if (occ[t] >= f)
            ans.insert(t);
    };
    auto updRange = [&](int i, int delta){
        updPoint(i - 2, delta);
        updPoint(i - 1, delta);
        updPoint(i, delta);
    };
 
    for (int i = 0; i < n; i++)
        updPoint(i, 1);
    
    for (int i = 0; i < n; i++){
        char temp = S[i];
 
        for (char c = 'a'; c <= 'z'; c++){
            updRange(i, -1);
            S[i] = c;
            updRange(i, 1);
        }
        updRange(i, -1);
        S[i] = temp;
        updRange(i, 1);
    }
    
    cout << ans.size() << "\n";
 
    for (auto s : ans)
        cout << s << "\n";
}