Codeforces Round 791 (Div. 2)

A. AvtoBus

题目大意

巴士车队的所有巴士总共拥有 $n$ 只轮胎，巴士车队有两种巴士，一种是4只轮胎的，一种是6只轮胎的。

问这个车队拥有的巴士数量的最小值和最大值。不满足输出-1。

题目解析

首先判断是否满足，可以观察发现轮子数量需要满足以下两个条件：

• 轮子数量必须是偶数
• 轮子数量不小于$4$

首先来计算满足条件的最大值。 为了能让巴士车队的巴士数目最多，那么轮子数目为$4$的巴士越多越好。

$$Cnt_{cars} = \frac{n}{4}$$

如果$n \bmod 4 = 0$，就刚好能满足情况。
如果$n \bmod 4 = 2$，那么 $4$ 只轮子的巴士数目是 $\frac{n}{4} - 1$ ，$6$ 只轮子的巴士数目是 $1$ ，巴士总数是 $\frac{n}{4}$ 。

然后来计算满足条件的最小值。 这里我们希望轮子数目为6的巴士数目越多越好。

$$Cnt_{cars} = \frac{n}{6}$$

如果$n \bmod 6 = 0$，那么刚好能全部都是6个轮子的巴士。
如果$n \bmod 6 = 2$，那么 $6$ 只轮子的巴士的数目是 $\frac{n}{6} - 1$ ，$4$ 个轮子的巴士的数目是 $2$ ，巴士总数是 $\frac{n}{6} + 1$ 。
如果$n \bmod 6 = 4$，那么 $6$ 只轮子的巴士的数目是 $\frac{n}{6}$，$4$ 只轮子的巴士数目是 $1$ ，巴士总数是 $\frac{n}{6} + 1$ 。

参考代码

int main() {
    int t;
    cin >> t;
    while(t--){
        ll n;
        cin >> n;
        if(n % 2 == 1 or n < 4) cout << "-1\n";
        else{
            ll maxv = n / 4;
            ll minv = n / 6;
            if(n % 6) minv++;
            cout << minv << " " << maxv << '\n';
        }
    }
    return 0;
}

B. Stone Age Problem

题目大意

对于一个数组，有两种操作方式：

• 将第 $i$ 个位置的元素，修改为 $x$。
• 将数组中所有元素修改为 $x$。

对于每一次操作，计算数组中元素之和。

题目解析

对于数组中的每个位置，记录上次修改的时间和值。同时记录上次全局修改的时间和值。

对于操作1，比较 $i$ 位置修改的时间和全局修改的时间，然后选择最新的去获取元素差，从而更新数组中元素之和。

对于操作2，直接修改全局上次修改时间和值，并更新数组中元素之和。

参考代码

int main() {
    int n, q;
    cin >> n >> q;
    PLL pre{-1, 0}; // 上次全局修改时间和值
    vector<PLL> arr(n + 1, {0, 0}); //上次每个位置修改的时间和值
    ll sum = 0;
    for(int i = 1; i <= n; ++i){
        cin >> arr[i].second;
        sum += arr[i].second;
    }
    ll opx = 0;
    while(q--){
        ++opx;
        int op;
        cin >> op;
        if(op == 1){
            int idx;
            ll val;
            cin >> idx >> val;
            if(pre.first > arr[idx].first){
                sum += val - pre.second;
            }else{
                sum += val - arr[idx].second;
            }
            arr[idx] = {opx, val};
        }else{
            ll val;
            cin >> val;
            sum = val * n;
            pre = {opx, val};
        }
        cout << sum << endl;
    }
    return 0;
}

C. Rooks Defenders

题目大意

你有一个棋盘，棋盘大小是 $n \times n$。
然后有三种操作：

• 向棋盘中 $(x, y)$ 坐标位置放置一枚车。
• 将棋盘中 $(x, y)$ 坐标位置的车移除，保证这个坐标位置有一枚车。
• 给你一个子矩形，矩形用左上角坐标 $(x_1, y_1)$ 和右下角坐标 $(x_2, y_2)$ 表示。问棋盘上面的车的移动范围能不能攻击到这个矩形内的所有位置。

题目解析

分别用数组记录每一行和每一列一共有多少枚车。
当每一行（列）出现第一个车，或者最后一枚车消失的时候，将当前行（列）的车数目更新到树状数组或者线段树。
然后统计子矩阵所覆盖的行是不是全部能被车覆盖到 或者 每一列都能被 车 覆盖到。

参考代码

template<typename T>
struct FenWick {
    int N;
    vector<T> arr;
    FenWick(int sz): N(sz), arr(sz + 1, 0) {}
    void update(int pos, T val) {
        for (; pos <= N;pos |= (pos + 1)) {
            arr[pos] += val;
        }
    }
    // 获取 [1, pos] 的和
    T get(int pos) {
        T ret = 0;
        for (; pos > 0; --pos) {
            ret += arr[pos];
            pos &= (pos + 1);
        }
        return ret;
    }
    // 获取 [l, r] 的和
    T query(int l, int r) {
        return get(r) - get(l - 1);
    }
};
int main() {
    fastIO();
    int n, q;
    cin >> n >> q;
    FenWick<int> fwr(n), fwc(n);
    vector<int> r(n + 1, 0), c(n + 1, 0);
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            int x, y;
            cin >> x >> y;
            r[x]++;
            c[y]++;
            if(r[x] == 1) fwr.update(x, 1);   // 当 🚗 出现的时候
            if(c[y] == 1) fwc.update(y, 1);   // 当 🚗 出现的时候
        }else if(op == 2){
            int x, y;
            cin >> x >> y;
            r[x]--;
            c[y]--;
            if(r[x] == 0) fwr.update(x, -1);  // 当 🚗 消失的时候
            if(c[y] == 0) fwc.update(y, -1);  // 当 🚗 消失的时候
        }else{
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            if(fwr.query(x1, x2) == x2 - x1 + 1 or fwc.query(y1, y2) == y2 - y1 + 1){
                cout << "Yes\n";
            }else{
                cout << "No\n";
            }
        }
    }
    return 0;
}

D. Toss a Coin to Your Graph…

题目大意

有一个不包含自环的有向图，图上的每一个节点都拥有一个权值 $a_i$，问你从某个节点出发，经过 $k - 1$ 条单向边，经过的所有节点的最大值最小。

题目解析

二分一下最大值 $a_{max}$，然后判断在不经过权值超过最大值的节点情况下，能不能满足经过 $k - 1$ 条单向遍。

对于每次一次二分枚举 $a_{max}$ ，将权值超过 $a_{max}$ 的点和与它相连的边移除，判断剩余的图形是否存在节点数大于或者等于$k$的链，或者存在环。这个可以用拓扑排序解决一下。

参考代码

struct Node{
    int a, b;
    int val;
    bool operator < (const Node& arg) const{
        return val < arg.val;
    }
};
int main() {
    fastIO();
    int n, m;
    ll k;
    cin >> n >> m >> k;
    vector<PLL> arr(n);
    for(int i = 0; i < n; ++i){
        cin >> arr[i].first;
        arr[i].second = i;
    }
    vector<Node> nodes(m);
    for(auto& it: nodes){
        cin >> it.a >> it.b;
        it.a--;
        it.b--;
        it.val = max(arr[it.a].first, arr[it.b].first); //边的权值设定为两个端点的最大值
    }
    sort(itr(nodes));
    sort(itr(arr));
    // 二分的检查函数，检查取最小的cnt个元素的情况下是否满足
    auto&& check = [&](int cnt) -> bool{
        vector<int> vis(n, 0);
        vector<vector<int>> g(n); //图
        vector<int> ins(n, 0);  //有向图入度
        vector<int> dep(n, 1);  //包含当前位置的链的节点数目
        for(int i = 0; i < m; ++i){
            if(nodes[i].val <= arr[cnt - 1].first){
                g[nodes[i].a].push_back(nodes[i].b);
                ins[nodes[i].b]++;
            }else{
                break;
            }
        }
        queue<int> q;
        for(int i = 0; i < n; ++i){
            if(ins[i] == 0){
                q.push(i);
                vis[i] = 1;
            }
        }
        while(!q.empty()){
            auto it = q.front();
            q.pop();
            for(auto& nex: g[it]){
                ins[nex]--;
                dep[nex] = max(dep[nex], dep[it] + 1);
                if(ins[nex] == 0){
                    q.push(nex);
                    vis[nex] = 1;
                }
            }
        }
 
        for(int i = 0; i < n; ++i) if(ins[i]) return true;  // 存在环
        for(int i = 0; i < n; ++i) if(dep[i] >= k) return true; // 链的节点数目超过k
        return false;
    };
    int ans = n + 1;
    for(int i = (1 << 20); i; i >>= 1){
        if(ans - i > 0 and check(ans - i)) ans -= i;
    }
    if(ans > n) cout << -1 << endl;
    else cout << arr[ans - 1].first << endl;
    return 0;
}