牛客周赛70题解

本篇题解由 Null_Resot 提供。

观前阅读

以下是本文中用到的一些符号或表示

数组在区间中的最大值 的表示：

异或 符号：

数组在区间的异或和 的表示 ：

数组在区间的区间和 的表示

属于 符号:

非负整数 符号:

艾佛森括号：，如果表达式的结果为，那么，否则

A 小苯晨跑

题意

小苯生活在计算机网络世界中，网络空间中到处都是数据，小苯每次晨跑，风都会带着这些数据乱飞。

现在正在晨跑的小苯面前有四个数据，他想知道这些数据是否乱飞了，请你帮他确定吧。

（如果所有数据都相等，则认为数据没有乱飞，反之则乱飞了。）

思路

我们可以用四个元素两两之间相互判断是否相同，也可以用一个长度为的数组进行排序，判断一下头尾元素是否相同，也可以直接维护一下个元素之间的最大值和最小值是否相同

这里我选择用一个集合进行存储数据，因为集合有着唯一性的特性，所以如果四个元素都一样，那么集合的大小应该是，否则说明至少存在不一样的两个元素

代码

void solve() {
    std::set<int> s;
    for (int i = 1; i <= 4; i ++) {
        int x;
        std::cin >> x;
        s.insert(x);
    }
    if (s.size() == 1) std::cout << "NO\n";
    else std::cout << "YES\n";
}

B 小苯过马路

题意

小苯生活在遥远的 B 星球，这天他正在等红绿灯，已知 B 星球的交规是：红灯有 秒，绿灯有 秒，红灯和绿灯是交替亮灯的。

（红灯上的时间从 减少到 后，再过一秒灯就会变成绿色，同时灯显示的时间也会变成 ；绿灯也同理。）

已知目前红绿灯颜色为 ，灯显示的时间为 ，小苯过马路需要花费的时间为 。

遵守交规的小苯想知道，从此刻开始到他走到马路对面，最少经过多少秒，请你帮他算一算吧。（小苯一旦开始过马路就不会停下脚步。）

思路

分类讨论：

• 如果当前是绿灯
  • 如果当前剩余的时间我们可以直接走到马路对面，那么直接走就可以了，用时为
  • 如果当前剩余时间不够走到马路对面的话，我们需要等下一轮绿灯亮起的时候再走，所用时为（等待秒到绿灯结束+等待秒红灯结束+走路秒）
• 如果当前是红灯，那么等待当前红灯结束后直接走到马路对面就可以了，所用时（等待秒红灯结束+走路秒）

代码

void solve() {
    int x, y, k, t;
    char c;
    std::cin >> x >> y >> k >> t >> c;
    int ans = t;
    if (c == 'R') ans += k;
    if (c == 'G' && k < t) ans += k + x;
    std::cout << ans << "\n";
}

C 小苯的字符串染色

题意

小苯有一个长度为 的字符串 ，其中有一些字符是黑色的，其余则为白色，他希望你可以给 涂色，使得涂完后的 是纯白色的。
具体的涂色操作：
选择一个长度为奇数的区间 同时 是奇数，接着将区间内的字符按照：白黑白黑白... 的方式涂色，即白色开头、白色结尾、同时黑白交替的样式。

小苯限制你最多进行 次涂色操作，请你构造一个合法涂色方案，使得涂色完后的字符串是全白色的吧，注意你不必最小化操作次数。

（注意，已经涂好颜色的地方依然可以被后续的涂色覆盖。）

思路

注意到不必最小化操作次数，这类题一般要从尽可能多地使用操作次数，并且每次操作都要让影响的区间范围尽可能小这方面出发

每次要求操作范围必须是奇数，那么最小的操作范围就是了，并且这样子我们可以保证把这个区间内的字符变成白色

所以我们可以直接遍历字符串，如果当前位是黑色，那么我们直接就操作当前位所在的长度为一的区间，那么当前位就会被涂成白色

因为我们最多操作次（即整个字符串都是黑色），所以符合题目要求最多次的操作次数限制，该做法合法

代码

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    std::cout << std::count(s.begin(), s.end(), '1') << "\n";
    for (int i = 0; i < n; i ++) if (s[i] == '1')
        std::cout << i + 1 << " " << i + 1 << "\n";
}

D 小苯的能量项链

题意

小苯有一个含有 颗珠子的“能量项链”，珠子排成一排，其中第 颗珠子的能量为 。

但是这个项链并不稳定，如果项链的珠子个数不少于 个，则它即将发生“崩坏”，即：除了第一颗珠子和最后一颗珠子以外的其余所有珠子都将销毁，最终只留下第一颗和最后一颗珠子。

小苯现在希望项链在“崩坏”后保留尽可能多的能量，为此他可以在崩坏前执行以下的操作：
去掉项链的第一颗珠子（也就意味着项链原本的第二颗珠子将会变成第一颗）。
去掉项链的最后一颗珠子（也就意味着项链原本的倒数第二颗珠子将会变成最后一颗）。

两种操作各自均需要花费 秒时间，而现在距离项链发生“崩坏”仅剩 秒，小苯想知道，他最多可以保留住多少能量，请你帮他算一算吧。

思路

首先如果，因为，所以我们不需要去进行任何操作，直接输出总和即可，接下来思考的情况

对于求一段最优连续子区间/求符合条件连续子区间个数的问题有个很经典的思考方向——枚举左/右端点，根据题意去求右/左端点的位置/数量。

对于本题也是一样，我们认为连续子区间的两端的值的总和最大为最优

那么我们思考枚举区间的左端点，当我们目前枚举的左端点的位置为，考虑右端点的可能会出现的位置——因为我们最多删个，而当前左端点为说明我们已经删除了个，所以最多再删除个，那么右端点可能的位置为

此外，因为我们要保证区间不能为空（对于本题，我们规定区间长度不能小于，因为左端点的值加上一个正数肯定会更优），所以右端点至少在左端点的位置，所以右端点可能的位置为

因为我们已经固定好了左端点的位置，所以区间左端点的贡献是固定的，我们要想让这段合法的区间的值最大，就需要求出保证右端点合法的情况下，右端点最大的值，即

这一部分其实就是求后缀最大值，我们可以维护一个数组，表示区间中最大的元素值，转移为，那么右端点的取值便是

这样子我们可以在的情况下得到当左端点为时最大的答案了，最后我们的枚举左端点，对于所有答案取一个最大值，便是我们要求的答案

代码

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n + 1), mx(n + 2);
    for (int i = 1; i <= n; i ++) std::cin >> a[i];
    for (int i = n; i >= 1; i --) mx[i] = std::max(mx[i + 1], a[i]);

    if (n == 1) {
        std::cout << a[1] << "\n";
        return ;
    }

    int ans = a[1] + a[n];
    for (int i = 1; i <= std::min(n - 1, k + 1); i ++) 
        ans = std::max(ans, a[i] + mx[std::max(i + 1, n - (k - (i - 1)))]);
    std::cout << ans << "\n";
}

E 小苯的最短路

题意

小苯有一个 个点的无向完全图，编号从 到 ，其中 号点和 号点之间的边权为 。

他想知道从 号点出发到达所有点的最短路，请你帮他算一算吧。（其中 表示按位异或运算。）

（但为了避免输出数据量过大，你只需要输出到达所有点的最短路的异或和即可。）

思路

结论+结论题

首先我们可以确定，从出发到达任何一点的最短路的路径就是直接从到达目标点，而不是经过某个中转点在到达目标点（见结论）

而我们的总异或和为

因为异或有结合律性质，所以有

前半部分根据结论可以通过分类讨论得到，后半部分根据的奇偶性可以直接得到，两部分异或一下就是我们这道题的答案

结论1：

• 当时，
• 当时，
• 当时，
• 当时，

结论：

结论证明：

• 当时，首先对于四个数，其四个数的异或值为。从开始每四个数分成一组，总共分成组，对于任意一组第组，其值为，因为，所以的不同在二进制中不会影响到前两位二进制，即四个数的二进制位是

  xxx...xxx 00
  xxx...xxx 01
  xxx...xxx 10
  xxx...xxx 11
  

  其中xxx...xxx是的二进制。可以发现四个数的前部分全部一样吗，所以异或和是，而四个数的二进制的后面两位的异或和本质上是的异或和为。

  所以当时，

• 鉴于上述的证明对于时，等价于分组后，最后一组的值为，其中

  二进制位为

  xxx...xxx 00
  xxx...xxx 01
  xxx...xxx 10
  

  可以发现前两个数的异或和为，因为最后一个数是偶数，所以异或一相当于加一，所以最终答案为

• 对于的两种情况与上文同理

结论证明：

首先证明，令为的二进制的第位，，为的二进制的第位。

接下来规定，加法不会发生二进制进位操作，即，而不是（二进制运算）

• 当
  • 
  • 
  • 
  • 
• 当
  • 
  • 
  • 

可以发现只有当所有的 或 时才能等于，如果有任何一位，那么有，所以

因为，所以有

代码

void solve() {
    int n;
    std::cin >> n;
    if (n % 4 == 0) {
        std::cout << n << "\n";
    } else if (n % 4 == 1) {
        std::cout << "0\n";
    } else if (n % 4 == 2) {
        std::cout << n + 1 << "\n";
    } else {
        std::cout << "1\n";
    }
}

F 小苯的优雅好序列

题意

小苯认为满足以下任一条件的序列 是优雅的。
。

对于所有 ，都存在 ，使得 或 。

小苯认为一个长度为 的数组 是好数组，当且仅当 所有的连续子数组都优雅。即对于所有 ， 都是一个优雅的序列。

现在小苯有一个数组 和正整数 ，他想知道有多少个不超过 的正整数 ，都有： 是一个好数组，请你帮他算一算吧。

思路

首先如果所有元素的值都一样，那么他们相互之间都是整除关系，对于任意不超过 的正整数 都有是一个好数组，那么有个数字，总和是

接下来我们考虑存在不同元素的情况

如果对于任意的都有 或 的话，那么数组是一个好数组

因为对于一个子区间，当时，长度为一的数组本身就是一个好数组，当时，对于都存在与构成整除关系，对于，存在与构成整除关系，该关系可以推广到任何包含该区间的所有区间

然后我们考虑两个不同的元素，令，设存在 使得并且，即

所以如果要想加上某一个数使得两个不同的元素成为倍数关系，那么就需要保证较小的数加上的和是两个元素的差的因数

我们可以选择相邻的两个不同元素，因为我们一开始的证明就是要求任意两个相邻元素都有整除关系，而推式子过程中选择的两个数也应该是有相邻关系，选的两个数的差的因子是能让这两个数满足他们之间加上这个数会满足整除关系，所以如果选的两个数不相邻的话其实和我们之前的证明没什么关系的，求出他们的差，然后枚举的所有因子，如果当前的因子满足的话，就用一次的枚举，暴力让所有元素都加上，判断是否满足所有相邻元素都有整除关系即可

但是我们的值域是，直接暴力枚举因子再嵌套一层的枚举判断不会超时吗？实际上并不会，因为内的数字中因子数最多的数的因子数也只有个，所以实际上会进行枚举判断的次数不会超过次，远远到不了的数量级，所以可以通过本题

代码

void solve() {
    i64 n, k;
    std::cin >> n >> k;
    std::vector<i64> a(n);
    std::set<i64> s;
    for (auto &i : a) {
        std::cin >> i;
        s.insert(i);
    }
 
    if (s.size() == 1) {
        std::cout << k << " " << k * (k + 1) / 2 << "\n";
        return ;
    }
 
    int x, y;
    for (int i = 0; i < n - 1; i ++) if (a[i] != a[i + 1]) {
        x = a[i];
        y = a[i + 1];
        break;
    }
    if (x > y) std::swap(x, y);
    int d = y - x;
     
    auto check = [&](int add) {
        if (add > k || add <= 0) return false;
 
        auto b = a;
        for (auto &i : b) i += add;
 
        for (int i = 1; i < n; i ++) if (std::max(b[i], b[i - 1]) % std::min(b[i], b[i - 1])) return false;
        return true;
    };
 
    i64 cnt = 0, sum = 0;
    for (int i = 1; i * i <= d; i ++) if (d % i == 0) {
        if (check(i - x)) cnt ++, sum += i - x;
        if (i * i != d && check(d / i - x)) cnt ++, sum += d / i - x;
    }
 
    std::cout << cnt << " " << sum << "\n";
}

G 小苯的树上操作

题意

小苯有一个 个点 条边的无向无根树，但其点权中可能存在负数。

现在如果树非空，则小苯可以对树进行一些“删点”操作任意次（两种都是任意次），具体的：

小苯可以选择任意一个度数恰好为 的节点，从树中直接删除该点和连接该点的边。
小苯可以选择任意一个度数恰好为 的节点，从树中删除该点，并将该点连接的两个邻点连接起来。

小苯想知道，他最大可以将树的点权和变为多少，请你帮他算一算吧。
（注意：空树的点权视为 ）。

思路

定义为以为根的子树，通过若干次删除操作可以得到的最大子树和（可以删除节点）

考虑一棵以为根节点的子树，其第个儿子节点为

为了更一般的思考，我们令根节点的父亲为，这样所有实际上的节点都有父亲了（是虚点）

如果保留节点，那么首先有的贡献，对于子树的选取，如果就一定选，否则不选，所以如果保留节点，最大子树和为，其中表示的儿子节点的集合，是艾佛森括号

如果不保留节点，首先要保证的度数为，因为有一条是连接父亲的边，那么要么是把整棵子树都删掉，要么是保留的最多一个儿子子树。最大子树和为

最后两种情况取一个，就可以转移到了

很遗憾我们得到的并不是我们想要的答案，因为如果我们选择删掉根节点的话，其实是可以最多保留两棵子树，这样答案就有可能是了，其中分别是根节点的两个不同的儿子节点，并且均大于

但这也仅限于删除根节点的情况，如果对于删掉其他点直接考虑的话也许会很麻烦，好在我们已经知道了如果是根节点的话该如何计算答案了，所以我们应该想到一个算法——换根dp，这样我们只需要让每个节点都作为根去计算一次答案，取所有答案的最大值，就是我们最终要求的答案了

首先考虑当前根不变的情况下对答案的计算：

• 第一种可能是不删除根节点，那么我们只需要尽可能地把所有的子树都选上即可，这部分的总和是
• 第二种可能是删掉根节点，那么我们需要至少保留值前大的子树，当然我们也可以一个都不保留，我们可以先遍历一边子树，用一个可重集合把所有的存起来，并且规定这个可重集合是按降序排序的，这部分的最大总和是可重集合中的前两个值对取的总和
• 二者取最大值，然后维护所有答案的最大值即可，ans = std::max({ans, sum, *s.begin() + (s.size() > 1 ? *std::next(s.begin()) : 0ll)});

接下来考虑转移：

• 假设我们要把根从转移到
• 那么红色区域内我们要作为的一个新的子树去思考，这里我们引入一个新的参数——up，表示红色区域内的最大子树和（对标的定义）
• 对于新的根，如果保留新的根，我们依旧先遍历一遍原本的所有子树，取值大于的所有子树，然后红色区域内也作为子树判断一下，如果我们就把这个新子树也选上，反之不选。这部分的总和是
• 如果不保留新的根，我们依旧是那可重集合把所有子树的值存起来，同理红色区域内也是个子树，所以也要把存入到可重集合中去，然后取前二大即可

考虑的维护：

• 回到根从转移到的过程中，首先如果保留的话，那么作为新子树的最大的子树和就是减掉之前之前作为子树对最大子树和的贡献，即
• 如果不保留的话，因为要让度数为，所以最多只能留下一个除去子树外的值最大的一个子树，那么可以先让可重集合先删除子树的值避免造成影响，然后用可重集合的最大值作为进行转移即可
• 最后两者取便能维护出

时间复杂度，是可重集合带来的。实际上可重集合也是可以优化掉的，只需要维护最大值次大值也能写，这样时间复杂度能降到，不过写起来可能就麻烦点

代码

void solve() {
    int n;
    std::cin >> n;
    std::vector<i64> a(n + 1);
    for (int i = 1; i <= n; i ++) std::cin >> a[i];
    std::vector go(n + 1, std::vector<int>());
    for (int i = 1; i < n; i ++) {
        int u, v;
        std::cin >> u >> v;
        go[u].emplace_back(v);
        go[v].emplace_back(u);
    }

    std::vector<i64> dp(n + 1);
    auto dfs = [&](auto &&dfs, int u, int fa) ->void {
        i64 max = 0, sum = a[u];
        for (auto v : go[u]) {
            if (v == fa) continue;
            dfs(dfs, v, u);
            sum += std::max(0ll, dp[v]);
            max = std::max(max, dp[v]);
        }

        dp[u] = std::max(max, sum);
    };
    dfs(dfs, 1, 1);

    i64 ans = 0;
    auto dfs2 = [&](auto &&dfs2, int u, int fa, i64 up) ->void {
        std::multiset<i64, std::greater<>> s;
        s.insert(std::max(0ll, up));
        i64 sum = std::max(0ll, up) + a[u];
        for (auto v : go[u]) {
            if (v == fa) continue;
            s.insert(std::max(0ll, dp[v]));
            sum += std::max(0ll, dp[v]);
        }

        ans = std::max({ans, sum, *s.begin() + (s.size() > 1 ? *std::next(s.begin()) : 0ll)});

        for (auto v : go[u]) {
            if (v == fa) continue;
            s.erase(std::max(0ll, dp[v]));
            dfs2(dfs2, v, u, std::max(sum - std::max(0ll, dp[v]), s.empty() ? 0ll : *s.begin()));
            s.insert(std::max(0ll, dp[v]));
        }
    };
    dfs2(dfs2, 1, 1, 0ll);
    std::cout << ans << "\n";
}