AtCoder Beginner Contest 308-有解無憂

這幾天在收拾東西搬家，先附上代碼，晚點補上題解
感覺這次FG都寫不太明白

A - New Scheme (abc308 A)

題目大意

給定八個數，問是否滿足以下要求：

不嚴格升序
每個數在\(100 \sim 675\)之間
每個數都是 \(25\)的倍數

解題思路

依次對每個數判斷是否符合這三個條件即可，

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    array<int, 8> a;
    for(auto &i : a)
        cin >> i;
    auto ok = [&](){
        for(int i = 0; i < 8; ++ i){
            if (i && a[i] < a[i - 1])
                return false;
            if (a[i] < 100 || a[i] > 675)
                return false;
            if (a[i] % 25)
                return false;
        }
        return true;
    };
    if (ok())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}

B - Default Price (abc308 B)

題目大意

<++>

解題思路

<++>

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    map<string, int> price;
    vector<string> a(n);
    for(auto &i : a)
        cin >> i;
    vector<string> col(m);
    for(auto &i : col)
        cin >> i;
    int ano;
    cin >> ano;
    for(auto &i : col){
        int p;
        cin >> p;
        price[i] = p;
    }
    int ans = 0;
    for(auto &i : a){
        if (price.find(i) == price.end())
            ans += ano;
        else 
            ans += price[i];
    }
    cout << ans << '\n';

    return 0;
}

C - Standings (abc308 C)

題目大意

<++>

解題思路

<++>

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<array<int, 2>> p(n);
    for(auto &i : p)
        cin >> i[0] >> i[1];
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int a, int b){
        LL l = 1ll * p[a][0] * (p[b][0] + p[b][1]);
        LL r = 1ll * p[b][0] * (p[a][0] + p[a][1]);
        return l != r ? l > r : a < b;
    });
    for(auto &i : id)
        cout << i + 1 << ' ';
    cout << '\n';

    return 0;
}

D - Snuke Maze (abc308 D)

題目大意

<++>

解題思路

<++>

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

array<int, 4> dx{1, -1, 0, 0};
array<int, 4> dy{0, 0, 1, -1};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> tu(h);
    for(auto &i : tu)
        cin >> i;
    string target = "snuke";
    vector<vector<vector<int>>> visit(h, vector<vector<int>>(w, vector<int>(target.size(), 0)));
    function<bool(int, int, int)> dfs = [&](int x, int y, int len){
        visit[x][y][len] = 1;
        if (tu[x][y] != target[len])
            return false;
        if (x == h - 1 && y == w - 1)
            return true;
        for(int i = 0; i < 4; ++ i){
            int nx = x + dx[i], ny = y + dy[i], nlen = (len + 1) % target.size();
            if (nx < 0 || nx >= h || ny < 0 || ny >= w || visit[nx][ny][nlen])
                continue;
            if (dfs(nx, ny, nlen))
                return true;
        }
        return false;
    };
    auto ok = [&](){
        return dfs(0, 0, 0);
    };
    if (ok())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}

E - MEX (abc308 E)

題目大意

<++>

解題思路

如果是找兩個字符，比如EX，我們可以從右往左統計每個X對應的陣列\(a\)的值，這樣對于此時的每一個 E，假設對應的陣列\(a\)的值是 \(e\)，那么所有 EX的組成的mex只有三種情況：

\(mex(e, 0)\)
\(mex(e, 1)\)
\(mex(e, 2)\)

此時以該E開始，右邊的所有X組成的EX，對答案的貢獻就分這三類，因此我們就記錄一下右邊有多少個是\(0\)的 X，\(1\)的 X，\(2\)的 X，然后乘以對應的mex值就是對答案的貢獻，

解決了EX，對于MEX，其實可以看成M和EX，只是這時候的EX有\(6\)種情況：

mex(M, 0, 0)
mex(M, 0, 1)
mex(M, 0, 2)
mex(M, 1, 1)
mex(M, 1, 2)
mex(M, 2, 2)

同樣我們就記錄EX分別是\(00,01,02,11,12,22\)這些情況的數量，再乘以對應的 mex值，就是該M對答案的貢獻，而統計EX 的數量就是剛剛的問題，

代碼里記錄\(00,01\)的情況用的二進制狀壓的方法，

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a)
        cin >> i;
    string s;
    cin >> s;
    array<int, 3> x{};
    array<LL, 8> ex{};
    map<int, int> tr{{0, 1}, {1, 2}, {2, 4}};
    map<int, int> mex;
    auto get_mex = [&](int x, int y, int z){
        set<int> candidate{0, 1, 2, 3};
        if (candidate.count(x))
            candidate.erase(x);
        if (candidate.count(y))
            candidate.erase(y);
        if (candidate.count(z))
            candidate.erase(z);
        return *candidate.begin();
    };
    for(int i = 0; i < 3; ++ i)
        for(int j = 0; j < 3; ++ j)
            for(int k = 0; k < 3; ++ k){
                mex[tr[i] | tr[j] | tr[k]] = get_mex(i, j, k);
            }
    LL ans = 0;
    for(int i = n - 1; i >= 0; -- i){
        if (s[i] == 'X'){
            x[a[i]] ++;
        }else if (s[i] == 'E'){
            for(int j = 0; j < 3; ++ j){
                int status = (tr[a[i]] | tr[j]);
                ex[status] += x[j];
            }
        }else{
            for(int j = 0; j < 8; ++ j){
                ans += mex[tr[a[i]] | j] * ex[j];
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

F - Vouchers (abc308 F)

題目大意

<++>

解題思路

兩種方向，分別按照商品價格的升序或降序依次考慮，

可以發現以升序方式考慮的話，先前考慮的優惠券同樣適用后面的商品，因此我們就可以從這些未使用且可使用的優惠券中選優惠力度最大的，

考慮是否存在反例，因為每個商品只能用一個優惠券，因此每次都只會從未使用中選最好的一個，當考慮一個新商品，同時還有更多的優惠券變得可使用時，這些優惠券不能代替先前的優惠券適用（不滿足最低價格），因此也替換不了，

感覺這個貪心貌似就對了，

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> p(n);
    for(auto &i : p)
        cin >> i;
    vector<array<int, 2>> coupon(m);
    for(auto &i : coupon)
        cin >> i[1];
    for(auto &i : coupon)
        cin >> i[0];
    priority_queue<array<int, 2>> best{};
    sort(p.begin(), p.end());
    sort(coupon.begin(), coupon.end(), [](const auto& a, const auto& b){
            return a[1] < b[1];
            });
    int pos = 0;
    LL ans = 0;
    for(auto &i : p){
        while(pos < m && coupon[pos][1] <= i){
            best.push(coupon[pos]);
            ++ pos;
        }
        int discout = 0;
        if (!best.empty()){
            discout = best.top()[0];
            best.pop();
        }
        ans += i - discout;
    }
    cout << ans << '\n';

    return 0;
}

G - Minimum Xor Pair Query (abc308 G)

題目大意

<++>

解題思路

不考慮修改，從陣列里選兩個異或值最小，我們可以遍歷由這n個數構成的trie數，我們選擇的兩個數盡量選擇同一邊的，如果某個節點下只有兩個數，且是該節點產生分歧的，此時就選擇這兩個數的異或者，作為一個備選答案，通過一次dfs就能得到，

考慮修改的話，我們發現上述產生答案的資訊是可以實時維護的，于是問題貌似就解決了？

具體來說，考慮一個節點\(u\)，左兒子(二進制下為\(0\))\(lson\)，右兒子(二進制下為\(1\))\(rson\) ，

如果\(u\)下只有兩個數，一個數在 \(lson\)子樹內，一個在 \(rson\)內，那以 \(u\)節點的子樹的最小異或值 \(ans_u = lson \oplus rson\)，一般我們要遍歷到葉子才知道這個\(lson,rson\)是多少，但為了減少時間復雜度，可以把這個資訊往上提到\(lson,rson\)處，這樣就不用遍歷到葉子，
如果\(lson\)下有至少兩個數，那么以\(u\)節點的子樹的最小異或值 \(ans_u = min(ans_u, ans_{lson})\)，而\(ans_{lson}\)是個子問題，
如果\(rson\)下有至少兩個數，那么以\(u\)節點的子樹的最小異或值 \(ans_u = min(ans_u, ans_{rson})\)，\(ans_{rson}\)同樣是個子問題，

對于葉子節點，如果該葉子對應兩個數，那么 \(ans_{leaf} = 0\)，否則為無窮大，

對于題意的增加和洗掉，這些資訊都可以在進行這些操作時\(O(1)\)維護，感覺就可以了，

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = (1 << 30) + 114514;
const int SZ = 2;
template<typename T, typename K>
struct Trie {
    struct node {
        K value;
        int ans;
        int vis_count;
        array<int, SZ> children;

        node(K val) : value(val) {
            vis_count = 0;
            fill(children.begin(), children.end(), 0);
            ans = inf;
        }
    };

    int cast(K val) {
        int ret = val;  
        assert(ret < SZ and ret >= 0);
        return ret;
    }

    vector<node> tree;

    Trie(K val) {
        tree.push_back(node(val));
    }

    void insert(int v, int pos, int cur, const T &sequence, bool remove = false) {

        if (remove) {
            tree[cur].vis_count -= 1;
        } else {
            tree[cur].vis_count += 1;
        }

        if (pos < sequence.size()){

            K value = https://www.cnblogs.com/Lanly/archive/2023/07/02/sequence[pos];
            if (tree[cur].children[cast(value)] == 0) {
                tree[cur].children[cast(value)] = (int) tree.size();
                tree.emplace_back(v);
            }

            insert(v, pos + 1, tree[cur].children[cast(value)], sequence, remove);

            if (tree[cur].vis_count == 1){
                int lson = tree[cur].children[cast(value)];
                int rson = tree[cur].children[cast(value) ^ 1];
                if (lson != 0 && tree[lson].vis_count != 0)
                    tree[cur].value = tree[lson].value;
                else 
                    tree[cur].value = tree[rson].value;
            }

            tree[cur].ans = inf;
            int lson = tree[cur].children[0], rson = tree[cur].children[1];
            if (lson != 0 && tree[lson].vis_count > 1)
                tree[cur].ans = min(tree[cur].ans, tree[lson].ans);
            if (rson != 0 && tree[rson].vis_count > 1)
                tree[cur].ans = min(tree[cur].ans, tree[rson].ans);
            if (lson != 0 && rson != 0 && tree[lson].vis_count == 1 && tree[rson].vis_count == 1)
                tree[cur].ans = tree[lson].value ^ tree[rson].value;
        }else{
            tree[cur].ans = inf;
            if (tree[cur].vis_count > 1)
                tree[cur].ans = 0;
        }
    }

    void remove(int v, const T& sequence) {
        insert(v, 0, 0, sequence, true);
    }

    int get_min(){
        return tree.front().ans;
    }

};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    Trie, int> tree(0);
    auto tr2bin = [](int x){
        array bin{};
        for(int i = 0; i < 30; ++ i){
            bin[i] = ((x >> (29 - i)) & 1);
        }
        return bin;
    };

    int q;
    cin >> q;
    while(q--){
        int op;
        cin >> op;
        if (op == 1){
            int x;
            cin >> x;
            tree.insert(x, 0, 0, tr2bin(x));
        }else if (op == 2){
            int x;
            cin >> x;
            tree.remove(x, tr2bin(x));
        }else{
            cout << tree.get_min() <<'\n';
        }
    }

    return 0;
}

Ex - Make Q (abc308 Ex)

題目大意

<++>

解題思路

<++>

神奇的代碼

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/556478.html

標籤：其他

上一篇：C++ 核心指南之資源管理（下）—— 智能指標最佳實踐

下一篇：返回列表