USACO2023-12月 银组题解分享

2024-02-21 13:19:13 浏览数 (1)

大家好！我是小码匠。

放假到年前还是比较Happy，旅行间隙温习了DP。

节后初三开始白天刷题，晚上写作业。作业还有很多没搞定，┭┮﹏┭┮。

很久没发题解了，今天上午老码农给我安排的模拟赛，USACO 2023 December 银组的3道题。

总体还算比较顺利，用时不到3小时AC掉了3道题。

下面分享代码，代码中关键地方有注释说明。

题解我就不详写了。

Problem 1. Bovine Acrobatics

洛谷地址：https://www.luogu.com.cn/problem/P9977

USACO：

  • https://usaco.org/index.php?page=viewproblem2&cpid=1350
  • 官方题解：https://usaco.org/current/data/sol_prob1_silver_dec23.html

代码

代码语言：javascript复制
// 题目: Problem 1. Bovine Acrobatics
// 链接: https://www.usaco.org/index.php?page=viewproblem2&cpid=1350
// 题解: https://www.usaco.org/current/data/sol_prob1_silver_dec23.html
// -- 洛谷: https://www.luogu.com.cn/problem/P9977
#include <bits/stdc  .h>

using namespace std;

const int MAX_NUM = 2e5   5;
struct cow {
    int w;
    long long num;
} a[MAX_NUM];
bool cmp (cow x, cow y) {
    return x.w < y.w;
}
long long b[MAX_NUM];
void best_coder() {
    int n, k;
    long long m;
    cin >> n >> m >> k;
    for (int i = 0; i < n;   i) {
        cin >> a[i].w >> a[i].num;
    }
    sort(a, a   n, cmp);

    int l = 0;
    long long ans = 0;
    for (int r = 0; r < n;   r) {
        while (l < n && a[r].w - a[l].w >= k) {
            m  = b[l];
              l;
        }
        b[r] = min(m, a[r].num); // b[r] 表示可以放置多少只第r种奶牛
        m -= b[r]; // m表示当前可以放置奶牛的塔
        ans  = b[r];
    }
    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 2. Cycle Correspondence

洛谷地址：https://www.luogu.com.cn/problem/P9978

USACO：

  • https://www.usaco.org/index.php?page=viewproblem2&cpid=1351
  • 官方题解：https://usaco.org/current/data/sol_prob2_silver_dec23.html

代码

代码语言：javascript复制
// 题目: Problem 2. Cycle Correspondence
// 链接: https://www.usaco.org/index.php?page=viewproblem2&cpid=1351
// 题解: https://www.usaco.org/current/data/sol_prob2_silver_dec23.html
// -- 洛谷: https://www.luogu.com.cn/problem/P9978
#include <bits/stdc  .h>

using namespace std;

const int MAX_NUM = 5e5   5;
struct node{
    int pos;
    bool b;
} appear[MAX_NUM];
int a[MAX_NUM], b[MAX_NUM], c[MAX_NUM], d[MAX_NUM];

void best_coder() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k;   i) {
        cin >> a[i];
        appear[a[i]].b = true;
        appear[a[i]].pos = i;
    }

    for (int i = 0; i < k;   i) {
        cin >> b[i];
        if (appear[b[i]].b) {
            int u = appear[b[i]].pos;
              c[(i   u) % k]; // 正着算一下要走几步
              d[(k - i - 1   u) % k]; // 把b翻转过来再算一下
        }
        appear[b[i]].b = true;
    }

    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < k;   i) {
        ans = max(ans, c[i]);
        cnt = max(cnt, d[i]);
    }
    ans = max(ans, cnt);
    for (int i = 1; i <= n;   i) {
        if (!appear[i].b) {
              ans;
        }
    }
    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. Target Practice

洛谷地址：https://www.luogu.com.cn/problem/P9979

USACO：

  • https://www.usaco.org/index.php?page=viewproblem2&cpid=1352
  • 官方题解：https://usaco.org/current/data/sol_prob3_silver_dec23.html

代码

代码语言：javascript复制
// 题目: Problem 3. Target Practice
// 链接: https://www.usaco.org/index.php?page=viewproblem2&cpid=1352
// 题解: https://www.usaco.org/current/data/sol_prob3_silver_dec23.html
// -- 洛谷: https://www.luogu.com.cn/problem/P9979
#include <bits/stdc  .h>

using namespace std;

unordered_map<int, bool> target; // 靶子
unordered_map<int, int> num[7]; // 第一维对应偏移量，第二维代表位置，第三维代表在这个位置开枪的一共几次
set<int> pos[7]; // 第一维对应偏移量，第二维代表开过枪的位置

void best_coder() {

    int t, c;
    cin >> t >> c;
    for (int i = 0; i < t;   i) {
        int x;
        cin >> x;
        target[x] = true;
    }
    string s;
    cin >> s;
    int now = 0;
    int ans = 0;
    for (int i = 0; i < c;   i) {
        if (s[i] == 'L') {
            --now;
        } else if (s[i] == 'R') {
              now;
        } else {
            for (int j = -2; j < 3;   j) { // 先把偏移后的存入对应数组
                if (target[now   j]) {
                      num[j   2][now   j];
                    pos[j   2].insert(now   j);
                }
            }
        }
    }
    ans = max(ans, (int) pos[2].size()); // 一个都不改的情况记录一下
    num[2].clear();
    pos[2].clear();
    now = 0;
    for (int i = 0; i < c;   i) {
        if (s[i] == 'L') {
            int cnt = pos[3].size()   (target[now] && !pos[2].count(now) && !pos[3].count(now));
            // L->F的情况中，偏移量是向右移1，计入这个靶子的条件是前面没有打过这个靶子，然后后面也不会打到这个靶子
            ans = max(ans, (int) pos[2].size()   max(cnt, (int) pos[4].size()));
            --now;
        } else if (s[i] == 'R') {
            int cnt = pos[1].size()   (target[now] && !pos[2].count(now) && !pos[1].count(now));
            // R->F的情况同理
            ans = max(ans, (int) pos[2].size()   max(cnt, (int) pos[0].size()));
              now;
        } else {
            for (int j = -2; j < 3;   j) {
                if (j != 0) {
                    pos[j   2].erase(now);
                    if (--num[j   2][now   j] <= 0) {
                        pos[j   2].erase(now   j);
                    }
                }
            }
            ans = max(ans, (int) (pos[2].size()   max(pos[1].size(), pos[3].size())));
            if (target[now]) {
                  num[2][now];
                pos[2].insert(now);
            }
        }
    }
    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;
}
cin int size 效率 https

0 人点赞