Codeforces Round 791 (Div. 2)

A. AvtoBus

题目大意

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

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

题目解析

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

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

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

Cntcars=n4Cnt_{cars} = \frac{n}{4}

如果nmod4=0n \bmod 4 = 0,就刚好能满足情况。
如果nmod4=2n \bmod 4 = 2,那么 44 只轮子的巴士数目是 n41\frac{n}{4} - 166 只轮子的巴士数目是 11 ,巴士总数是 n4\frac{n}{4}

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

Cntcars=n6 Cnt_{cars} = \frac{n}{6}

如果nmod6=0n \bmod 6 = 0,那么刚好能全部都是6个轮子的巴士。
如果nmod6=2n \bmod 6 = 2,那么 66 只轮子的巴士的数目是 n61\frac{n}{6} - 144 个轮子的巴士的数目是 22 ,巴士总数是 n6+1\frac{n}{6} + 1
如果nmod6=4n \bmod 6 = 4,那么 66 只轮子的巴士的数目是 n6\frac{n}{6}44 只轮子的巴士数目是 11 ,巴士总数是 n6+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

题目大意

对于一个数组,有两种操作方式:

  • 将第 ii 个位置的元素,修改为 xx
  • 将数组中所有元素修改为 xx

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

题目解析

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

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

对于操作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×nn \times n
然后有三种操作:

  • 向棋盘中 (x,y)(x, y) 坐标位置放置一枚
  • 将棋盘中 (x,y)(x, y) 坐标位置的移除,保证这个坐标位置有一枚
  • 给你一个子矩形,矩形用左上角坐标 (x1,y1)(x_1, y_1) 和右下角坐标 (x2,y2)(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…

题目大意

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

题目解析

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

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

参考代码

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;
}

Codeforces Round 791 (Div. 2)
https://dianhsu.com/2022/05/14/cf1679/
作者
Dian Hsu
发布于
2022年5月14日
许可协议