20230831 巨人网络 笔试 AK

AK了，九点半再发。。。

T1 魔鬼C++字符串处理 + 拓扑排序

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int> ;

pii getab(string &s) {
    int left = 0, right = 0;
    pii ans;
    int n = s.size();
    int i = 0;
    for(; i < n; ++i) {
        if(s[i] == ',') {
            ans.first = left;
            break;
        } else {
            left = left * 10 + s[i] - '0';
        }
    }
    i += 2;
    for(; i < n; ++i) {
        if(s[i] == '}') {
            ans.second = right;
            break;
        } else {
            right = right * 10 + s[i] - '0';
        }
    }
    return ans;
}

int main() {
    string s;
    getline(cin, s);
    s = s.substr(1, s.size() - 2);
    stringstream ss(s);
    vector<pii> ve;
    map<int, int> in_deg;
    map<int, vector<int>> g;
    string str;

    while(getline(ss, str, '{')) {
        if(!str.empty()) {
            pii tp = getab(str);
            int a = tp.first;
            int b = tp.second;
            ++in_deg[b];
            if(in_deg.find(a) == in_deg.end()) {
                in_deg[a] = 0;
            }
            ve.push_back(make_pair(a, b));
            g[a].push_back(b);
        }
    }

    queue<int> q;
    for(auto &&[x,y]: in_deg) {
        if(y == 0) {
            q.push(x);
        }
    }

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for(int y: g[x]) {
            if(--in_deg[y] == 0) {
                q.push(y);
            }
        }
    }

    int flag = true;
    for(auto &&[x, y]: in_deg) {
        if(y) {
            flag = false;
            break;
        }
    }
    if(flag) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;   
}

T2 线段树 + map

注意几个点：

• 线段树区间操作需要左闭右开，因为观察样例可以发现：1->3买了票 且 4->5买了票，实际上这个时候是可以买3->4的票的
• 观察样例，退(a, b)的票时候只能退恰好购买的是(a, b)这个pair的票，否则就退票失败

不过还是想骂，题意说得不太清楚，完全只能看样例猜题意。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct SegTree {
    struct Node {
        ll maxh, tg;
        Node(): maxh(0), tg(0) {}
    };

    #define ls (i<<1)
    #define rs (i<<1|1)
    vector<Node> tr;

    SegTree() = default;
    SegTree(const int &N): tr((N + 1) << 2) {}
    
    void push_down(int i, int l, int r) {
        if(!tr[i].tg) return;
        ll k = tr[i].tg;
        tr[ls].maxh += k;
        tr[rs].maxh += k;
        tr[ls].tg += k;
        tr[rs].tg += k;
        tr[i].tg = 0;
    }
    
    void push_up(int i) {
        tr[i].maxh = max(tr[ls].maxh, tr[rs].maxh);
    }

    void add_range(int i, int l, int r, int L, int R, int k) {
        if (l >= L && r <= R) {
            tr[i].tg += k;
            tr[i].maxh += k;
            return;
        }
        push_down(i, l, r);
        int mid = (l + r) >> 1;
        if(mid >= L) add_range(ls, l, mid, L, R, k);
        if(mid + 1 <= R) add_range(rs, mid + 1, r, L, R, k);
        push_up(i);
    }

    ll getmax(int i, int l, int r, int L, int R) {
        if (l >= L && r <= R) {
            return tr[i].maxh;
        }
        push_down(i, l, r);
        int mid = (l + r) >> 1;
        ll ret = LLONG_MIN;
        if(mid >= L) ret = max(ret, getmax(ls, l, mid, L, R));
        if(mid + 1 <= R) ret = max(ret, getmax(rs, mid + 1, r, L, R));
        return ret;
    }
};


void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    SegTree tr(n);
    map<pii, ll> ma;
    int a, b, c;
    char ch;
    for(int i = 0; i < q; ++i) {
        cin >> ch;
        cin >> a >> b;
        a++;
        if(ch == 'Q') {
            cout << m - tr.getmax(1, 1, n, a, b) << '\n';
        } else if(ch == 'B') {
            cin >> c;
            ll rem = m - tr.getmax(1, 1, n, a, b);
            if(rem >= c) {
                cout << "OK!\n";
                tr.add_range(1, 1, n, a, b, c);
                ma[make_pair(a, b)] += c;
            } else {
                cout << "Fail!\n";
            }
        } else if(ch == 'R') {
            cin >> c;
            if(ma.find(make_pair(a, b)) != ma.end() && ma[make_pair(a, b)] >= c) {
                cout << "OK!\n";
                tr.add_range(1, 1, n, a, b, -c);
                ma[make_pair(a, b)] -= c;
            } else {
                cout << "Fail!\n";
            }
        }
    }
}

int main() {

    cin.tie(nullptr)->sync_with_stdio(false);
    solve();

    return 0;
}