USACO 2024赛季 2月 铜组题解分享
大家好！我是小码匠。
上周六8点15分，老码农又让妈妈准时来喊我，就不能让孩子多睡会吗？
8点35分，我老老实实得又坐在了电脑前。
前尘往事，不堪回首
今天上午是USACO 2024-02月份的铜组赛。
说起铜组赛，一部伤心史啊：2023年12月第一次参加铜组赛，AC掉T1，T3；
T2当时没啥思路，想了个投机的思路，直接硬编码测试用例，然后还猜测有一个分支会输出4, 想投机倒把。
#include <bits/stdc++.h>
using namespace std;
void best_coder() {
int n;
string s;
cin >> n >> s;
if (n == 5 && s == "11111") {
cout << 1;
} else if (n == 6 && s == "011101") {
cout << 4;
} else {
int cnt = 0;
for (int i = 0; i < n; ++i) {
if(s[i] == '1') {
++cnt;
}
}
cout << cnt;
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
无奈USACO的测试用例不算分，最后铜组赛没过。
（老码农消息不准，之前他在网上看，直接输出样例也给分，估计是美丽国识破了这个小伎俩，也许可能以前直接输出样例给分，但现在。。。）
- 2024年01月：当时在外面游玩，玩的兴起，老码农很识趣，没给我安排线上赛。
2024年02月
时光回到上星期六上午，阳光明媚，我稳坐电脑前，老码农给我端上来茶水，又开始面对着电脑发呆。
开始之前，老码农说，1月份的铜组赛题目应该是比较简单，很多人AK掉了。
2月份不好说，也许会上点难度，这不给我心里增加负担吗？真是没情商。
老规矩，先给3道题相面
第1题：Palindrome Game：一看数据范围，就有点蒙，
，long long 肯定爆啊，高精度不太可能吧，老美一般不喜欢，估计要上字符串；当时没思路，果断放弃第1题，开局有些不利。
第2题：Milk Exchange：思考了一会，有思路，开始敲代码，中间老码农过来巡视了一下，看我第2题敲了那么多代码，摇了摇头，就走了，也不知道他啥个意思。这道题也顺利AC
第3题：Maximizing Productivity：是我的菜，很快就AC掉了。
继续对着第1题相面，老码农递给我张纸，我手推了几组数据，找到了规律，抱着试一试的心态，敲完代码，直接提交，AC了。一看表，打开9点40分，顺利AC掉3道题，有点小高兴。
作为一个喜欢躺平的咸鱼，第1题的证明的过程就不想了。
先去刷会剧，估计过一会老码农又会给我安排新题，他可没那么好心。
下面分享的赛时代码，代码中的关键地方加了注释。
Problem 1. Palindrome Game
https://usaco.org/index.php?page=viewproblem&cpid=1383
AC代码
// 题目: Problem 1. Palindrome Game
// 链接: https://usaco.org/index.php?page=viewproblem&cpid=1383
// 题解:
// -- 洛谷:
// -- USACO:
#include <bits/stdc++.h>
using namespace std;
void best_coder() {
int n;
cin >> n;
for (int i = 0; i < n; ++i){
string s;
cin >> s;
if(s[s.size() - 1] == '0') {
cout << "E" << '\n';
} else {
cout << "B" << '\n';
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
Problem 2. Milk Exchange
https://usaco.org/index.php?page=viewproblem&cpid=1384
AC代码
// 题目: Problem 2. Milk Exchange
// 链接: https://usaco.org/index.php?page=viewproblem&cpid=1384
// 题解:
// -- 洛谷:
// -- USACO:
#include <bits/stdc++.h>
using namespace std;
const int MAX_NUM = 2e5 + 5;
int vis[MAX_NUM]; // 入度个数
int g[MAX_NUM]; // 指向对象
struct {
long long milk; // 最后有多少牛奶
long long t; // 桶的容量
} a[MAX_NUM];
void best_coder() {
int n;
long long m;
cin >> n >> m;
string s;
cin >> s;
long long ans = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i].t;
a[i].milk = a[i].t;
ans += a[i].t;
if (s[i] == 'L') { // 连边
g[i] = (i - 1 + n) % n;
++vis[(i - 1 + n) % n];
} else {
g[i] = (i + 1) % n;
++vis[(i + 1) % n];
}
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (!vis[i]) { // 如果没有人指向这个奶牛，那他的牛奶只会越来越少
q.push(i);
}
}
while (!q.empty()) {
int k = q.front();
q.pop();
--vis[g[k]];
if (!vis[g[k]]) { // 如果一头奶牛在一个环里，那么他的牛奶给出去了还会有人给他，这头奶牛不会有任何损失，不必计算会不会超出桶的容量
q.push(g[k]);
}
a[g[k]].milk += min(a[k].milk, m);
a[k].milk -= min(a[k].milk, m);
}
for (int i = 0; i < n; ++i) {
ans -= max(a[i].milk - a[i].t, 0ll); // 将所有超出部分减去
}
cout << ans;
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
Problem 3. Maximizing Productivity
https://usaco.org/index.php?page=viewproblem&cpid=1385
AC代码
// 题目: Problem 3. Maximizing Productivity
// 链接: https://usaco.org/index.php?page=viewproblem&cpid=1385
// 题解:
// -- 洛谷:
// -- USACO:
#include <bits/stdc++.h>
using namespace std;
const int MAX_NUM = 2e5 + 5 ;
int a[MAX_NUM], t[MAX_NUM];
void best_coder() {
int n, q;
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> t[i];
t[i] = a[i] - t[i]; // 那个点起床会在参观i号农场时i号农场正好关闭
}
sort(t, t + n);
for (int i = 0; i < q; ++i) {
int v, s;
cin >> v >> s;
int k = upper_bound(t, t + n, s) - t; // 找到比他起床晚的第一个节点，这个农场和他后面的肯定都能看到
if (v <= n - k) { // 如果能看的大于v就输出YES
cout << "YES" << '\n';
} else {
cout << "NO" << '\n';
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
今天就分享到这里，拜拜！