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)\)了。

当然因为是可合并的,树链剖分将一个路径剖分成若干条轻链和重链合并也不是不行

神奇的代码
#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;
}



热门相关:流鱼无恙   贪婪   野兽女孩   劳拉性爱伴侣   目标螺柱