526互联

[题解] AtCoder Beginner Contest 308 A~G

发布时间 2023-09-07 16:04:24作者: 芙兰朵露·斯卡蕾特

AtCoder Beginner Contest 308 A~G

A. New Scheme

void Main() {
    vector<i64> a(8);
    for (auto &x : a) cin >> x;
    if (!is_sorted(a.begin(), a.end()) && !all_of(a.begin(), a.end(), [](auto &x) { return x % 25 != 0 || !(100 <= x && x <= 675); })) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
    }
}

B. Default Price

void Main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (auto &x : a) cin >> x;
    map<string,int> mp;
    vector<string> b(m);
    for (int i = 0; i < m; i ++) {
        cin >> b[i];
    }
    i64 ans = 0, t = 0;
    cin >> t;
    for (int i = 0; i < m; i ++) {
        cin >> mp[b[i]];
    }
    for (int i = 0; i < n; i ++) {
        if (!mp.count(a[i])) {
            ans += t;
        } else {
            ans += mp[a[i]];
        }
    }
    cout << ans << '\n';
}

C. Standings

至少我用 long double 居然没过……

void Main() {
    int n;
    cin >> n;
    vector<array<i64,3>> a(n + 1);
    for (int i = 1; i <= n; i ++) {
        i64 x, y;
        cin >> x >> y;
        auto g = gcd(x, y + x);
        a[i] = {x / g, (x + y) / g, i};
    }
    sort(a.begin() + 1, a.end(), [](const auto &a, const auto &b) {
        auto x = a[0] * b[1], y = a[1] * b[0];
        if (x == y) {
            return a[2] < b[2];
        } else {
            return x > y;
        }
    });
    for (int i = 1; i <= n; i ++) {
        cout << a[i][2] << " \n"[i == n];
    }
}

D. Snuke Maze

搜一下就可以，但是要注意的是，如果可以重复走到以前的路，那么代表这里有个循环，也其实是不需要走多走循环也可以到达，因此需要一个 vis 标记一下。

void Main() {
    int n, m;
    cin >> n >> m;

    vector a(n + 2, vector<char>(m + 2));
    map<char,char> nex {
        {'s', 'n'}, {'n', 'u'}, {'u', 'k'}, {'k', 'e'}, {'e', 's'}
    };

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            char x;
            cin >> x;
            if (nex.count(x))
                a[i][j] = x;
        }
    }

    if (a[1][1] == 0) {
        cout << "No\n";
        return;
    }

    vector vis(n + 2, vector<bool>(m + 2));
    auto dfs = [&](auto &&dfs, int x, int y) -> void {
        if (x == n && y == m) {
            cout << "Yes\n";
            exit(0);
        }
        vis[x][y] = true;
        for (auto [nx, ny] : array<pair<int,int>,4>{pair{x + 1, y}, {x. 1, y}, {x, y + 1}, {x, y. 1}}) {
            if (!vis[nx][ny] && a[nx][ny] == nex[a[x][y]]) {
                dfs(dfs, nx, ny);
            }
        }
    };
    dfs(dfs, 1, 1);
    cout << "No\n";
}

E. MEX

显然是一个枚举一个点的套路题。

注意到，我们枚举的三个位置必须符合 MEX 这样的形式，那么我们可以枚举 E 的位置，这样问题就转化为枚举 E ，求前缀 M 和后缀 X 的组合有多少种，所以需要知道对于一个位置 E ，前缀有多少个 M ，后缀有多少个 X 。最后求遍 mex 算结果即可。

void Main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
    }
    string s;
    cin >> s;

    map<pair<char,int>, vector<i64>> pre, rep;
    for (auto c : {'M', 'E', 'X'}) {
        for (auto i : {0, 1, 2}) {
            pre[{c, i}].assign(n + 2, 0);
            rep[{c, i}].assign(n + 2, 0);
        }
    }

    for (int i = 0; i < n; i ++) {
        pre[{s[i], a[i]}][i + 1] = rep[{s[i], a[i]}][i + 1] = 1;
    }

    for (auto c : {'M', 'E', 'X'}) {
        for (auto i : {0, 1, 2}) {
            auto x = pair{c, i};
            for (int i = 1; i <= n; i ++) {
                pre[x][i] += pre[x][i - 1];
            }
            for (int i = n; i >= 1; i --) {
                rep[x][i] += rep[x][i + 1];
            }
        }
    }


    i64 ans = 0;
    for (int i = 2; i <= n - 1; i ++) {
        if (s[i - 1] == 'E') {
            auto tag = pair{s[i - 1], a[i - 1]};
            for (int j = 0; j < 3; j ++) {
                for (int k = 0; k < 3; k ++) {
                    auto cnt = pre[{'M', j}][i] * rep[{'X', k}][i];
                    array tmp {k, j, a[i - 1]};
                    sort(tmp.begin(), tmp.end());
                    int mex = 0;
                    for (auto x : tmp) mex += mex == x;
                    ans += cnt * mex;
                }
            }
        }
    }
    cout << ans << '\n';
}

F. Vouchers

贪心。

我们希望最后的花费最少，那么对于每张折扣券，找一个目前还未被使用的、价格最接近使用界限的商品使用即可。同时我们需要注意的是，我们希望折扣力度最大，那么我们就需要先按折扣价格最多的来算，尽量让这张券用上，力度小的，如果能用就用了，没法用就算了。

template <typename T, typename Compare = std::greater<T>>
using BinaryHeap = std::priority_queue<T, std::vector<T>, Compare>;

void Main() {
    int n, m;
    cin >> n >> m;
    multiset<i64> st;
    i64 ans = 0;
    for (int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        st.emplace(x);
        ans += x;
    }
    vector<pair<i64,i64>> b(m);
    for (int i = 0; i < m; i ++) {
        i64 x;
        cin >> x;
        b[i].second = x;
    }
    for (int i = 0; i < m; i ++) {
        i64 x;
        cin >> x;
        b[i].first = x;
    }
    sort(b.begin(), b.end());
    while (!b.empty()) {
        auto [d, l] = b.back();
        b.pop_back();
        auto it = st.lower_bound(l);
        if (it == st.end()) {
            continue;
        } else {
            ans -= d;
            st.extract(it);
        }
    }
    cout << ans << '\n';
}

G. Minimum Xor Pair Query

问目前的序列中任意两个数异或得到的最小异或和是多少。

有一个特殊的性质：对于一个序列来说，其任意两个数异或得到的最小值一定存在于其从小到大排序后相邻两项的异或和。如果注意到这个性质，那么就可以拿两个 multiset 做完这道题了。一个存序列，一个存结果，添加或删除的时候需要调整一下结果即可。

void Main() {
    int q;
    cin >> q;
    multiset<int> mst, ret;
    for (int i = 0; i < q; i ++) {
        int opt, x;
        cin >> opt;
        if (opt == 1) {
            cin >> x;
            auto pit = mst.lower_bound(x);
            if (pit != mst.end() && pit != mst.begin()) {
                ret.extract(*pit ^ *prev(pit));
            }
            auto it = mst.emplace(x);
            if (it != mst.begin()) {
                ret.emplace(*it ^ *prev(it));
            }
            if (next(it) != mst.end()) {
                ret.emplace(*it ^ *next(it));
            }
        } else if (opt == 2) {
            cin >> x;
            auto it = mst.lower_bound(x);
            if (it != mst.begin()) {
                ret.extract(*it ^ *prev(it));
            }
            if (next(it) != mst.end()) {
                ret.extract(*it ^ *next(it));
            }
            it = mst.erase(it);
            if (it != mst.end()) {
                if (it != mst.begin()) {
                    ret.emplace(*it ^ *prev(it));
                }
            }
        } else {
            cout << *ret.begin() << '\n';
        }
    }
}