The 1st Universal Cup. Stage 8: Slovenia

D. Deforestation

这道题出题人比较谜语人，对于一个分叉点，只能选择若干个儿子和父亲组成一组，剩下的儿子之间不能相互组合。所以从叶子节点开始贪心处理就好。对于一个父亲他有若干个儿子，就贪心的选择剩下部分更小的儿子。

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;

constexpr int inf = 1E18;


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int w;
    cin >> w;
    int res = 0;
    auto dfs = [&](auto &&self) -> int {
        int v, n;
        cin >> v >> n;
        vector<int> t(n);
        for (int x; auto &i: t)
            x = self(self), res += x / w, i = x % w;
        sort(t.begin(), t.end());
        int cnt = 0;
        for (auto i: t) {
            if (cnt + i <= w) cnt += i;
            else res++;
        }
        return v + cnt;
    };
    res += ( dfs(dfs) + w - 1 ) / w;
    cout << res << "\n";
    return 0;
}

E. Denormalization

因为每次除的数字相同，所以数组的比值并不会发生改变，只要先枚举出一个数，然后根据比值算出其他的数，然后验证一下最大公约数就好。但问题是枚举哪一个数呢？我通过罚时试出来枚举最大值，其他值会被卡精度

#include <bits/stdc++.h>

using namespace std;

using ldb = long double;
#define int long long
constexpr ldb eps = 1E-6;


int32_t main() {
    int n;
    cin >> n;
    vector<ldb> a(n);
    for (auto &i: a)
        cin >> i;

    int t = max_element(a.begin(), a.end()) - a.begin();
    for (int i = 0; i < n; i++)
        if( i != t ) a[i] /= a[t];
    a[t] = 1;
    vector<int> b(n);

    for (b[t] = 1; b[t] <= 10000; b[t]++) {
        int d = b[t];
        for (int i = 0; i < n; i++) {
            if (i == t) continue;
            ldb x = (ldb) b[t] * a[i];
            if (x - floor(x) < eps) b[i] = floor(x);
            else if (ceil(x) - x < eps) b[i] = ceil(x);
            else {
                d = -1;
                break;
            }
            d = gcd(d, b[i]);
        }
        if (d != 1) continue;
        for (auto i: b)
            cout << i << "\n";
        return 0;
    }
    return 0;
}

L. The Game

阅读题加模拟题，读懂之后很好写

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

int32_t main() {
    vi pile(98);
    for (auto &i: pile) cin >> i;
    reverse(pile.begin(), pile.end());
    vector<vi> que(4);
    que[0].push_back(1);
    que[1].push_back(1);
    que[2].push_back(100);
    que[3].push_back(100);
    vi hand;
    for (int i = 0; i < 8; i++)
        hand.push_back(pile.back()), pile.pop_back();
    while (true) {
        int op = -1;
        auto it = hand.begin();
        for (; it != hand.end(); it = next(it)) {
            if (que[0].back() > *it and que[0].back() - *it == 10) {
                op = 0;
                break;
            } else if (que[1].back() > *it and que[1].back() - *it == 10) {
                op = 1;
                break;
            } else if (que[2].back() < *it and *it - que[2].back() == 10) {
                op = 2;
                break;
            } else if (que[3].back() < *it and *it - que[3].back() == 10) {
                op = 3;
                break;
            }
        }
        if (op != -1) {
            que[op].push_back(*it);
            hand.erase(it);
        } else {
            it = hand.begin();
            auto jt = it;
            int deta = 1e9;
            for (int dd, opp; it != hand.end(); it = next(it)) {
                dd = 1e9, opp = -1;
                if (que[0].back() < *it and *it - que[0].back() < dd) {
                    dd = *it - que[0].back(), opp = 0;
                }
                if (que[1].back() < *it and *it - que[1].back() < dd) {
                    dd = *it - que[1].back(), opp = 1;
                }
                if (que[2].back() > *it and que[2].back() - *it < dd) {
                    dd = que[2].back() - *it, opp = 2;
                }
                if (que[3].back() > *it and que[3].back() - *it < dd) {
                    dd = que[3].back() - *it, opp = 3;
                }
                if (opp == -1) continue;
                if (dd < deta)
                    deta = dd, jt = it, op = opp;
            }
            if (op == -1) break;
            que[op].push_back(*jt);
            hand.erase(jt);
        }

        // 第二张
        op = -1;
        it = hand.begin();
        for (; it != hand.end(); it = next(it)) {
            if (que[0].back() > *it and que[0].back() - *it == 10) {
                op = 0;
                break;
            } else if (que[1].back() > *it and que[1].back() - *it == 10) {
                op = 1;
                break;
            } else if (que[2].back() < *it and *it - que[2].back() == 10) {
                op = 2;
                break;
            } else if (que[3].back() < *it and *it - que[3].back() == 10) {
                op = 3;
                break;
            }
        }
        if (op != -1) {
            que[op].push_back(*it);
            hand.erase(it);
        } else {
            it = hand.begin();
            auto jt = it;
            int deta = 1e9;
            for (int dd, opp; it != hand.end(); it = next(it)) {
                dd = 1e9, opp = -1;
                if (que[0].back() < *it and *it - que[0].back() < dd) {
                    dd = *it - que[0].back(), opp = 0;
                }
                if (que[1].back() < *it and *it - que[1].back() < dd) {
                    dd = *it - que[1].back(), opp = 1;
                }
                if (que[2].back() > *it and que[2].back() - *it < dd) {
                    dd = que[2].back() - *it, opp = 2;
                }
                if (que[3].back() > *it and que[3].back() - *it < dd) {
                    dd = que[3].back() - *it, opp = 3;
                }
                if (opp == -1) continue;
                if (dd < deta)
                    deta = dd, jt = it, op = opp;
            }
            if (op == -1) break;
            que[op].push_back(*jt);
            hand.erase(jt);
        }


        for (int i = 0; !pile.empty() and i < 2; i++)
            hand.push_back(pile.back()), pile.pop_back();
    }
    for (auto it: que) {
        for (auto i: it)
            cout << i << " ";
        cout << "\n";
    }
    for (auto i: hand)
        cout << i << " ";
    cout << "\n";
    reverse(pile.begin(), pile.end());
    for (auto i: pile)
        cout << i << " ";
    cout << "\n";
    return 0;
}