Codeforces Round 881 (Div. 3)-Toy模板网

这篇具有很好参考价值的文章主要介绍了Codeforces Round 881 (Div. 3)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

A - Sasha and Array Coloring (CF1843 A)

题目大意

给定一个数组，给每个元素涂色。求最大的代价。

代价为每个颜色的代价和。

每个颜色的代价为涂了该颜色的元素的极差。

解题思路

因为是极差，每个元素要么对答案有正的贡献，要么有负的贡献，要么无贡献。且正负贡献的个数要相同。

因为要最大值，自然就是想有正贡献的是最大的那些数，负贡献的是最小的那些数。

因此答案就是最大的那一半的和\(-\)最小的那一半的和。奇数的话中间多出来的一个无贡献。

神奇的代码

#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 t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto &i : a)
            cin >> i;
        sort(a.begin(), a.end());
        int ans = -accumulate(a.begin(), a.begin() + n / 2, 0) + accumulate(a.end() - n / 2, a.end(), 0);
        cout << ans << '\n';
    }

    return 0;
}

B - Long Long (CF1843 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 t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto &i : a)
            cin >> i;
        LL ans = 0;
        for(auto &i : a)
            ans += abs(i);
        int cnt = 0;
        bool neg = (a[0] < 0);
        for(auto &i : a){
            if (i > 0 && neg){
                cnt ++;
                neg = false;
            }else if (i < 0)
                neg = true;
        }
        cnt += neg;
        cout << ans << ' ' << cnt << '\n';
    }

    return 0;
}

C - Sum in Binary Tree (CF1843 C)

题目大意

给定一棵完全二叉树，点权为其标号。问从\(n\)号点开始，不断往父亲节点走，其点权和是多少。

解题思路

父亲节点的标号为\(\frac{n}{2}\)，因此直接模拟即可，走 \(\log\)次就走到根了。

神奇的代码

#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 t;
    cin >> t;
    while(t--){
        LL n;
        cin >> n;
        LL ans = 0;
        while(n){
            ans += n;
            n >>= 1;
        }
        cout << ans << '\n';
    }

    return 0;
}

D - Apple Tree (CF1843 D)

题目大意

给定一棵有根树。树上有两个苹果。每一时刻，每个苹果可以往其中一个儿子节点移动。最终移动到叶子处。

设两个苹果最终所处的叶子节点为\(a,b\)，问 \((a,b)\)的情况数。

解题思路

如果一个苹果在\(x\)节点，那么它能移动的叶子处就是以 \(x\)为根的叶子节点，如果有 \(a\)个叶子，那么该苹果的可移动到的叶子数就是 \(a\)。

现在有两个苹果，假设它们最终可移动到的叶子节点数分别为\(a,b\)，那最终的情况数就是 \(a \times b\)。

因此事先预处理\(son[x]\)表示以\(x\)为根的叶子数量，\(O(1)\)回答即可。

神奇的代码

#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 t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<vector<int>> edge(n);
        for(int i = 1; i < n; ++ i){
            int u, v;
            cin >> u >> v;
            -- u, -- v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        vector<int> son(n, 0);
        function<void(int, int)> dfs = [&](int u, int fa){
            bool leaf = true;
            for(auto &v : edge[u]){
                if (v == fa)
                    continue;
                leaf = false;
                dfs(v, u);
                son[u] += son[v];
            }
            son[u] += leaf;
        };
        dfs(0, 0);
        int q;
        cin >> q;
        while(q--){
            int u, v;
            cin >> u >> v;
            -- u, -- v;
            cout << 1ll * son[u] * son[v] << '\n';
        }
    }

    return 0;
}

E - Tracking Segments (CF1843 E)

题目大意

给定一个有\(n\)个\(0\)的数组\(a\)，以及 \(m\)个区间。

一个区间如果是好区间，则其间 \(1\)的个数严格大于 \(0\)的个数。

现依次进行 \(q\)次操作，每次操作将 \(a_x = 1\)。

问最早进行了多少次操作后，出现好区间。

解题思路

我们可以依次枚举\(q\)，得到操作后的数组，接下来就是判断每个区间是不是 好区间，即判断\(1\)的个数和 \(0\)的个数的大小关系。朴素判断是\(O(nm)\)，但我们可以事先对 \(1\)的个数求一遍数组\(a\)的前缀和，这样每个区间的判断都可以在\(O(1)\) 得出结果，判断的复杂度降为\(O(n + m)\)。

由于我们是枚举\(q\)的，此时时间复杂度为 \(O(q(n + m))\)，但可以发现 \(q\)与是否存在 好区间是一个单调的函数，即如果\(q=4\)存在 好区间，那么\(q > 4\)也一定存在好区间，因此我们可以二分这个 q，得到其临界点。

最终时间复杂度降为\(O((n + m)\log q)\)

神奇的代码

#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 t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        vector<array<int, 2>> seg(m);
        for(auto &i : seg){
            cin >> i[0] >> i[1];
            -- i[0], -- i[1];
        }
        int q;
        cin >> q;
        vector<int> pos(q);
        for(auto &i : pos){
            cin >> i;
            -- i;
        }
        auto check = [&](int x){
            vector<int> cnt(n, 0);
            for(int i = 0; i < x; ++ i)
                cnt[pos[i]] = 1;
            partial_sum(cnt.begin(), cnt.end(), cnt.begin());
            for(auto &[l, r] : seg){
                int one = cnt[r];
                if (l > 0)
                    one -= cnt[l - 1];
                int zero = r - l + 1 - one;
                if (one > zero)
                    return true;
            }
            return false;
        };
        int l = 0, r = q;
        while(l + 1 < r){
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid;
            else 
                l = mid;
        }
        if (!check(r))
            r = -1;
        cout << r << '\n';

    }

    return 0;
}

F1 - Omsk Metro (simple version) (CF1843 F1)

题目大意

给定一棵点权为\(1\) 或\(-1\)的树，点数为\(n\)。

给定\(q\)个询问\(u, v, k\)，依次回答从\(u \to v\)这条路径中，是否存在一个子区间，其和为 \(k\)。

该题\(u = 1\)

解题思路

子区间和可以转换成两个前缀和作差，那么在一般的问题里，我们可以枚举每个前缀和，若其值为\(x\)，那就看之前的前缀和是否有值为 \(x - k\)的。

很显然本题里，复杂度是\(O(nq)\)，无法通过。但本题有个奇特点为点权仅为\(1\)或 \(-1\)，这其间或许有什么性质。

容易发现，假设一个区间的最大字段和为 \(max\)，最小字段和为 \(min\)，那么 \([min, max]\)区间的数都可以取到，即都存在对应的子区间。因为点权仅为\(1\)或 \(-1\)，一个子区间左右扩张，其值只会加一或者减一，不会跳跃，而初始值为 \(0\)。

因此问题就转换成维护一个区间的子区间的最大值和最小值即可。这是一个简单的\(dp\)，即设 \(dp[i]\)表示以 \(i\)结尾的最大后缀和，然后再维护一个全局的最大值。最小值同理。

由于本题中 \(u = 1\)，因此可以直接从 \(1\)开始 \(dfs\)，维护这个 \(dp\)即可。撤销\(dp\)相当于回溯。

神奇的代码

#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 t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<vector<int>> edge(n + 1);
        vector<int> val(n + 1);
        vector<vector<int>> target(n + 1);
        vector<int> q;
        val[0] = 1;
        int cur = 1;
        for(int i = 0; i < n; ++ i){
            string op;
            cin >> op;
            if (op[0] == '+'){
                int v, x;
                cin >> v >> x;
                -- v;
                edge[v].push_back(cur);
                edge[cur].push_back(v);
                val[cur] = x;
                ++ cur;
            }else{
                int u, v, k;
                cin >> u >> v >> k;
                -- u, -- v;
                assert(u == 0);
                target[v].push_back(int(q.size()));
                q.push_back(k);
            }
        }
        vector<int> ans(q.size());
        function<void(int, int, int, int, int, int)> dfs = [&](int u, int fa, int maxx, int minn, int gmaxx, int gminn){
            for(auto &t : target[u]){
                ans[t] = (q[t] <= gmaxx && q[t] >= gminn);
            }
            for(auto &v : edge[u]){
                if (v == fa)
                    continue;
                int nmaxx = max({maxx + val[v], val[v], 0});
                int nminn = min({minn + val[v], val[v], 0});
                int ngmaxx = max(gmaxx, nmaxx);
                int ngminn = min(gminn, nminn);
                dfs(v, u, nmaxx, nminn, ngmaxx, ngminn);
            }
        };
        dfs(0, 0, 1, 0, 1, 0);
        for(auto &i : ans)
            if (i)
                cout << "YES" << '\n';
            else 
                cout << "NO" << '\n';
    }

    return 0;
}

F2 - Omsk Metro (hard version) (CF1843 F2)

题目大意

给定一棵点权为\(1\) 或\(-1\)的树，点数为\(n\)。

给定\(q\)个询问\(u, v, k\)，依次回答从\(u \to v\)这条路径中，是否存在一个子区间，其和为 \(k\)。

解题思路

本题\(u \neq 1\)。

在上一题中，我们将问题转换成维护一个区间的子区间的最大值和最小值。

注意到这个信息是可合并的。以最大值为例。

假设我们有一个左区间和一个右区间，现在我们要将其合并成一个大区间，并求其子区间的最大值。

那么该最大值只有三种情况：

左区间的最大值
右区间的最大值
左区间的最大后缀和+右区间的最大前缀和

因此我们只需要额外增加最大前缀和和最大后缀和这两个信息，我们就可以将两个区间合并，得到新区间的最大值。

而为了维护最大前缀和和最大后缀和，还需要区间和这个信息，因为新区间的最大前缀和有两种情况：

左区间的最大前缀和
左区间的区间和+右区间的最大前缀和

最大后缀和同理，因此我们只要维护一个区间的

最大值、最小值
最大前缀和、最小前缀和
最大后缀和、最小后缀和
区间和

这些信息，我们就可以将两个区间合并，得到一个大区间的信息。

可合并有什么用呢？

每次询问其实就是询问一个区间的最大子区间和和最小子区间和，因为这些区间的数量级是\(O(n^2)\)，我们不可能一一计算，而是通过只计算某些区间，这样其他区间都可以通过这些区间，以较少的代价合并得到。

回想下 \(st\)表，它可以 \(O(1)\)回答出任意一个区间的最值，但它预处理的复杂度只有 \(O(n\log n)\)，也就是说它可以通过计算 \(n\log n\)个区间的最值，然后以\(O(1)\)的代价通过这些计算好的区间，合并出任意区间的最值（注意最值这个信息也是可合并的）。而它用到的方法就是倍增。

同样，既然我们要维护的信息是可合并的，我们可以运用倍增的思想，即树上倍增，对于每个点，维护以这个点往父亲方向，一共\(2^j\)个点所组成的序列的信息，然后对于每个询问所对应的路径，通过 倍增的方式可以拆成\(\log\)个区间进行合并。

假设询问\(u \to v\)，因为在树上，我们可以在它们的\(lca\)点拆开，这样\(u \to lca\), \(v \to lca\)就是一条链，通过倍增合并得到其信息（跟倍增求lca是一样的），最后再将\(u \to lca\)和\(v \to lca\)合并（注意\(v \to lca\)信息的前后缀要反转过来）即得到\(u \to v\)的信息。

这样每次询问的复杂度就是\(O(\log n)\)了。

~~当然因为是可合并的，树链剖分将一个路径剖分成若干条轻链和重链合并也不是不行~~文章来源地址https://www.toymoban.com/news/detail-493743.html

神奇的代码

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

struct info{
    int max, premax, sufmax;
    int min, premin, sufmin;
    int sum;
};

info operator+(const info& a, const info& b){
    info c;
    c.max = max({a.max, b.max, a.sufmax + b.premax});
    c.premax = max(a.premax, a.sum + b.premax);
    c.sufmax = max(b.sufmax, b.sum + a.sufmax);
    c.min = min({a.min, b.min, a.sufmin + b.premin});
    c.premin = min(a.premin, a.sum + b.premin);
    c.sufmin = min(b.sufmin, b.sum + a.sufmin);
    c.sum = a.sum + b.sum;
    return c;
}

info reverse(const info& a){
    info c = a;
    swap(c.premax, c.sufmax);
    swap(c.premin, c.sufmin);
    return c;
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> val(n + 1);
        val[0] = 1;
        int cur = 1;
        vector<array<int, 3>> q;
        vector<vector<int>> fa(32, vector<int>(n + 1));
        vector<int> deep(n + 1);
        for(int i = 0; i < n; ++ i){
            string op;
            cin >> op;
            if (op[0] == '+'){
                int v, x;
                cin >> v >> x;
                -- v;
                val[cur] = x;
                fa[0][cur] = v;
                deep[cur] = deep[v] + 1;
                ++ cur;
            }else{
                int u, v, k;
                cin >> u >> v >> k;
                -- u, -- v;
                q.push_back({u, v, k});
            }
        }
        vector<vector<info>> up(32, vector<info>(n));
        for(int i = 0; i < n; ++ i){
            if (val[i] == 1){
                up[0][i] = info{1,1,1,0,0,0,1};
            }else{
                up[0][i] = info{0,0,0,-1,-1,-1,-1};
            }
        }
        for(int i = 1; i < 32; ++ i){
            for(int j = 0; j < n; ++ j){
                fa[i][j] = fa[i - 1][fa[i - 1][j]];
                if (fa[i - 1][j] != fa[i][j])
                    up[i][j] = up[i - 1][j] + up[i - 1][fa[i - 1][j]];
            }
        }
        auto find = [&](int u, int v){
            if (deep[u] < deep[v])
                swap(u, v);
            int dis = deep[u] - deep[v];
            info l{}, r{};
            for(int i = 0; i < 32; ++ i){
                if (dis & 1){
                    l = l + up[i][u];
                    u = fa[i][u];
                }
                dis >>= 1;
            }
            if (u == v){
                return l + reverse(up[0][u]);
            }
            for(int i = 31; i >= 0; -- i){
                if (fa[i][u] != fa[i][v]){
                    l = l + up[i][u];
                    r = r + up[i][v];
                    u = fa[i][u];
                    v = fa[i][v];
                }
            }
            int lca = fa[0][u];
            l = l + up[0][u];
            r = r + up[0][v];
            return l + up[0][lca] + reverse(r);
        };
        auto solve = [&](int u, int v, int k){
            auto res = find(u, v);
            return res.min <= k && k <= res.max;
        };

        for(auto &[u, v, k] : q)
            if (solve(u, v, k))
                cout << "YES" << '\n';
            else 
                cout << "NO" << '\n';
    }

    return 0;
}

到了这里，关于Codeforces Round 881 (Div. 3)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！