USACO银组2024-01月题解分享：T1最难， T3小学奥数，360太恶心

小码匠

发布于 2024-02-21 13:20:07

1650

发布于 2024-02-21 13:20:07

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好！我是小码匠。

今天上午继续模拟赛：USACO 2024 January。

赛前老码农又提醒我，先把三道题题面阅读定开题顺序。

去年平时模拟赛和线上赛参加的比较少，比赛感觉有些差，看题就往正解方面思考。

日常训练：想正解；
比赛：得分第一位。

今天耗时大约3.5小时AC掉这3道题。

看完题面，直观感觉：

T1、T3：难度相当；
T2：相对简单。

T3

我上来先开T1，坐在电脑前呆呆的思考。

过了20分钟，老码农过来提醒我，要不要先看看其他题

（赛后他说，他提前看的题解，感觉T1比较难，担心我又死扣T1）。

听人劝吃饱饭，我又对着T3发呆，突然开窍了，这不就是小学奥数的抽屉原理。

之后T3打的比较顺利，一次A掉。

题面：https://www.luogu.com.cn/problem/P10136

题解：代码中关键地方加了注解

AC代码

// 题目: Cowlendar
// 链接: https://usaco.org/index.php?page=viewproblem2&cpid=1376
// 题解:
// -- 洛谷: https://www.luogu.com.cn/problem/P10136
// -- USACO:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll; // 官方还是很良心的
const int MAX_NUM = 1e4 + 5;
int n, len = 0;
ll a[MAX_NUM];

bool check(ll x) {
    unordered_set<ll> s;
    for (int i = 0; i < len; ++i) {
        s.insert(a[i] % x);
    }
    return s.size() <= 3;
}

void best_coder() { // 因为L最多只有三个可能性，根据鸽巢原理最小的4个数就能算出所有的答案
    cin >> n;
    unordered_map<ll, bool> appear;
    for (int i = 0; i < n; ++i) {
        ll x;
        cin >> x;
        if (appear[x]) {
            continue;
        }
        a[len++] = x;
        appear[x] = true;
    }

    sort(a, a + len);
    if (len <= 3) { // 去重后如果只有三个可能值那么只要不超过L的最大值，一定都可以满足条件2
        ll L = a[0] / 4;
        cout << (1 + L) * L / 2;
        return;
    }

    unordered_set<ll> ans;
    for (int i = 0; i < 4; ++i) { // 鸽巢原理嘛
        for (int j = i + 1; j < 4; ++j) {
            ll L = a[j] - a[i];
            for (ll k = 1; k * k <= L; ++k) {
                if (L % k) {
                    continue;
                }
                if (k * 4 > a[0]) {
                    break;
                }
                if (check(k)) {
                    ans.insert(k);
                }


                if ((L / k) * 4 > a[0]) {
                    continue;
                }
                if (check(L / k)) {
                    ans.insert(L / k);
                }
            }
        }
    }

    ll cnt = 0;
    for (auto i: ans) {
        cnt += i;
    }
    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;
}

T2

继续开T2，东搞西搞，搞了1个小时，今天比较顺利，也是一次AC掉。

不得不吐槽老码农，其实树形DP去年他就安排我学过，主要是中间没再温习，我是金鱼的记忆，到现在忘得一干二净，给老码农打差评。

// 题目: Potion Farming
// 链接: https://usaco.org/index.php?page=viewproblem2&cpid=1375
// 题解:
// -- 洛谷: https://www.luogu.com.cn/problem/P10135
// -- USACO:
#include <bits/stdc++.h>

using namespace std;
const int MAX_NUM = 1e5 + 5;
int dp[MAX_NUM], father[MAX_NUM], dep[MAX_NUM], p[MAX_NUM], cnt[MAX_NUM], leaf = 0, deepest = 0;
vector<int> g[MAX_NUM], dep_g[MAX_NUM];

void dfs(int u, int fa) { // dfs找每个节点的父亲节点，深度，和树的深度
    dep[u] = dep[fa] + 1;
    deepest = max(deepest, dep[u]);
    dep_g[dep[u]].push_back(u);
    father[u] = fa;
    bool flag = true;

    for (auto i: g[u]) {
        if (i == fa) {
            continue;
        }
        dfs(i, u);
        flag = false;
    }

    if (flag) {
        ++leaf; // 判断有几个叶子节点
        ++dp[u]; // 有几条路线走这个点
    }
}

void best_coder() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 1);

    for (int i = 0; i < leaf; ++i) {
        ++cnt[p[i]];
    }

    int ans = 0;
    do {
        for (auto i: dep_g[deepest]) {
            ans += min(cnt[i], dp[i]); // 如果这个点会出现的药水小于经过这个点的方案数那么能拿到所有药水，而剩下经过这个点就没有贡献了，反之亦然
            dp[i] -= min(cnt[i], dp[i]);
            dp[father[i]] += dp[i]; // 把剩余走这条线的方案数累计到他的父亲节点一样
        }
    } while (--deepest);
    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;
}

T1

在T1上遇到了点麻烦，一开始想到用线段树，后来感觉太麻烦了，再说USACO的银组考纲里也没有线段树，估计用其他算法也能搞定。罚坐了20分钟后，想了个贪心做法。

中间老码农给我拿了3个士力架安慰我被虐的小心灵，算你有心。

这道题我提交了3次：

第一次：这个锅不是我的，360太恶心了，把我的代码当成病毒了，给我删了。气得我直接提交，就华丽丽的一个测试点都没过；

第二次：重启了CLion后，继续调试。测试样例都过了，充分利用USACO的规则，继续提交，悲剧，只过了2个点，就是测试用例的2个点；

第三次：对着代码做静态检查，结果发现74行少了个=号，果断加上

        if (c[p[i].h] <= max_1 && !zero[p[i].h]) {

非常给面子。

// 题目: Cowmpetency
// 链接: https://usaco.org/index.php?page=viewproblem2&cpid=1374
// 题解:
// -- 洛谷: https://www.luogu.com.cn/problem/P10134
// -- USACO:
#include <bits/stdc++.h>

using namespace std;

const int MAX_NUM = 2e5 + 5;
int c[MAX_NUM];
struct node {
    int a, h;
} p[MAX_NUM];
int ans[MAX_NUM];
bool zero[MAX_NUM];

bool cmp(node x, node y) {
    return x.a < y.a;
}

int n, q, C;

bool f() {
    cin >> n >> q >> C;
    for (int i = 1; i <= n; ++i) {
        zero[i] = false;
        cin >> c[i];
        if (!c[i]) {
            zero[i] = true;
            c[i] = 1;
        }
    }
    for (int i = 1; i <= q; ++i) {
        cin >> p[i].a >> p[i].h;
    }

    sort(p + 1, p + q + 1, cmp);

    for (int i = 1; i <= q; ++i) {
        if (p[i].h == p[i - 1].h) {
            continue;
        }
        if (p[i].a < p[i - 1].h) { // 区间如果重叠且不是包含关系那么一定没有解
            return false;
            /*  a[i]---------------h[i]
             *      |_____________| ->中间的一定<= a[i] < h[i]
             *            a[j]---------------h[j] ->所以a[j] < h[i]，但是要求h[j]是第一个大于a[j]的数所以如果h[i] != h[j]那么一定不满足要求
             */
        }

        int max_1 = -1, max_2 = -1, last = 0;
        for (int j = p[i - 1].h; j <= p[i].a; ++j) {
            max_1 = max(max_1, c[j]);
            if (zero[j]) {
                last = j;
            }
        }

        for (int j = p[i].a + 1; j < p[i].h; ++j) {
            max_2 = max(max_2, c[j]);
        }
        if (max_1 < max_2) {
            if (!last) {
                return false;
            }
            c[last] = max_2;
            max_1 = max_2;
            /*  h[i]---------------a[j]---------------h[j]
             *      |-最大值为max_1-|   |-最大值为max_2-| ->max_2 <= a[j], max_1 < h[j]
             * 如果max_1比max_2小，那么使max_1至少为max_2即可（要保证字典序最小）
             */
        }
        if (c[p[i].h] <= max_1 && !zero[p[i].h]) {
            return false;
        } else if (zero[p[i].h]) {
            c[p[i].h] = max_1 + 1;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (c[i] > C) {
            return false;
        }
    }

    return true;
}

void best_coder() {
    int t;
    cin >> t;
    while (t--) {
        if (f()) {
            for (int i = 1; i <= n; ++i) {
                cout << c[i] << " ";
            }
        } else {
            cout << -1;
        }
        cout << '\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;
}