牛客周赛41

A 小红接雨水

小红在数轴上搭起了 3 个宽度为 1 的紧挨着的矩形柱子，高度从左到右分别是 a, b, c。小红想知道，当雨水量足够的时候，最多可以接多少单位面积的水？

void solve() {
    int a, b, c;cin >> a >> b >> c;
    if (min(a, c) - b <= 0)cout << "0\n";
    else cout << min(a, c) - b << '\n';
}

B 小红的排列构造

构造一个排列 $p$ 要求这个排列与给定的排列 $a$ ，$a_i\ne p_i$ 的个数恰好等于 $k$。

拙劣的构造，将后面 $k$ 个需要不同的下标翻转即可。

void solve() {
    int n, k;cin >> n >> k;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    if (k > n) {
        cout << "-1\n";return;
    }
    if (n == 1 && k == 1) {
        cout << "-1\n";return;
    }
    vector<int>p(n - k + 1);
    for (int i = 1;i <= n - k;i++) {
        p[i] = a[i];
    }
    vector<int> o;
    for (int i = n - k + 1;i <= n;i++) {
        o.push_back(a[i]);
    }
    reverse(o.begin(), o.end());
    if (o.size() & 1) {
        swap(o[o.size() / 2], o[o.size() / 2 + 1]);
    }
    for (int i = 0;i < o.size();i++) {
        p.push_back(o[i]);
    }
    vector<int>ans;
    for (int i = 1;i < p.size();i++) {
        if (p[i])ans.push_back(p[i]);
    }
    if (ans.size() < n) {
        cout << "-1\n";return;
    }
    for (auto i : ans)cout << i << " ";
    cout << '\n';
}

rotate 函数：rotate(begin, ro_begin,ro_end),这里代表的是从 begin 开始作为翻转的起点，将迭代器为 ro_begin 位置到 ro_end 位置的元素放到最前面，而这之前的元素放到这之后。

C++ rotate用法及代码示例 - 纯净天空

若 begin 就为该数组的 a.begin()，则 a.begin() + 1, a.begin() + k 代表将这个范围内的元素向左移动 1 位

void solve() {
    int n, k;cin >> n >> k;vector<int> a(n);
    for (int i = 0;i < n;i++)cin >> a[i];
    if (k > n || k == 1) {
        cout << "-1\n";return;
    }
    if (k == 0) {
        for (int i = 0;i < n;i++)cout << a[i] << " \n"[i == n - 1];return;
    }
    rotate(a.begin(), a.begin() + 1, a.begin() + k);

    for (int i = 0;i < n;i++)cout << a[i] << " \n"[i == n - 1];
}

等价于：

void solve() {
    int n, k;cin >> n >> k;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    if (k > n || k == 1) {
        cout << "-1\n";return;
    }
    if (k == 0) {
        for (int i = 1;i <= n;i++)cout << a[i] << " \n"[i == n];return;
    }
    rotate(a.begin() + 1, a.begin() + 2, a.begin() + k + 1);

    for (int i = 1;i <= n;i++)cout << a[i] << " \n"[i == n];
}

C 小红的循环移位

小红拿到了一个数字串，她每次操作可以使得其向左循环移动一位。

小红想知道，使得该数字串变成 4 的倍数，需要最少操作多少次？（可以包含前导零）

只需要考虑最后两位即可，特判一下前两个，后面依次模拟移动即可。

void solve() {
    string s;cin >> s;int n = s.size();s = ' ' + s;
    if (((s[n - 1] - '0') * 10 + s[n]) % 4 == 0) {
        cout << "0\n";return;
    }
    if (((s[n] - '0') * 10 + s[1]) % 4 == 0) {
        cout << "1\n";return;
    }
    int ans = 1;
    for (int i = 1;i < n;i++) {
        ans++;
        if (((s[i] - '0') * 10 + s[i + 1]) % 4 == 0) {
            cout << ans << '\n';return;
        }
    }
    cout << "-1\n";
}

D 小红的好串

小红定义一个字符串是“好串”，当且仅当该该字符串在长度和它相等的字符串中，"red"子序列的数量是最多的。

现在小红拿到了一个字符串，她有多次询问，每次询问一个区间，你需要回答将该区间对应的子串修改为好串的最小修改次数（每次修改可以修改任意一个字符）。

Solution

前缀和

这个题目我的思路是对的，但是细节出了问题。

代码：

void solve() {
    int n, q;cin >> n >> q;string s;cin >> s;s = ' ' + s;
    vector<int> pr(n + 1), pe(n + 1), pd(n + 1);
    for (int i = 1;i <= n;i++) {
        pr[i] = pr[i - 1] + (s[i] == 'r');
        pe[i] = pe[i - 1] + (s[i] == 'e');
        pd[i] = pd[i - 1] + (s[i] == 'd');
    }
    auto query = [&](int l, int r, char c) ->int {
        if (c == 'r') return r - l + 1 - (pr[r] - pr[l - 1]);
        if (c == 'e') return r - l + 1 - (pe[r] - pe[l - 1]);
        if (c == 'd') return r - l + 1 - (pd[r] - pd[l - 1]);
        };
    while (q--) {
        int l, r;cin >> l >> r;
        if (r - l + 1 < 3) {
            cout << "0\n";continue;
        }
        int x = (r - l + 1) / 3, y = (r - l + 1) % 3;
        int ans = 1e9;
        if (y == 0) {
            ans = query(l, l + x - 1, 'r') + query(l + x, l + x * 2 - 1, 'e') + query(l + x * 2, r, 'd');
        } else if (y == 1) {
            ans = min(ans, 
            query(l, l + x, 'r') + query(l + x + 1, l + x * 2, 'e') + query(l + x * 2 + 1, r, 'd'));
            ans = min(ans, 
            query(l, l + x - 1, 'r') + query(l + x, l + x * 2, 'e') + query(l + x * 2 + 1, r, 'd'));
            ans = min(ans, 
            query(l, l + x - 1, 'r') + query(l + x, l + x * 2 - 1, 'e') + query(l + x * 2, r, 'd'));
        } else {
            ans = min(ans, 
            query(l, l + x, 'r') + query(l + x + 1, l + x * 2 + 1, 'e') + query(l + x * 2 + 2, r, 'd'));
            ans = min(ans, 
            query(l, l + x, 'r') + query(l + x + 1, l + x * 2, 'e') + query(l + x * 2 + 1, r, 'd'));
            ans = min(ans, 
            query(l, l + x - 1, 'r') + query(l + x, l + x * 2, 'e') + query(l + x * 2 + 1, r, 'd'));
        }
        cout << ans << '\n';
    }
}

E/F 小红的树上赋值

小红拿到了一棵有根树，根节点为 1 号节点，其中一些节点被染成了红色。她希望你给每个节点都赋一个权值（权值在$[l,r]$区间内），满足所有红点的子树权值和为 0。
小红希望最终所有节点的绝对值之和尽可能大。

一行输出 $n$ 个整数，代表每个节点的赋值情况。如果有多种合法的树都能达成绝对值之和最大，给出任意一个方案即可。

• easy：$l=-1,r=1$
• hard：$-{10}^9\le l\le -1,1\le r\le {10}^9$

Solution

Easy version

思路：由于每个红色系节点的子树权值和为 0，则可以将红色节点和其父节点的连接断开，对于单独的红色节点构成的一个小树来单独考虑，若这个小树的节点个数为偶数，则一定是 $-1,1$ 各一半，为奇数则是有一个 0，其余 $-1,1$ 各一半。

对这个小树有：只有根节点是红色节点，其余全为白色节点。

thisislike：

void solve() {
    int n, l, r;cin >> n >> l >> r;string s;cin >> s;s = ' ' + s;
    vector<vector<int>>g(n + 1), f(n + 1);
    for (int i = 1;i < n;i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>ans(n + 1);
    auto dfs = [&](auto self, int x, int fa = -1)->void {
        f[x].push_back(x);ans[x] = 1;
        for (auto y : g[x]) {
            if (y == fa)continue;
            self(self, y, x);
            if (f[x].size() < f[y].size()) {
                swap(f[x], f[y]);
            }
            while (f[y].size()) {
                f[x].push_back(f[y].back());
                f[y].pop_back();
            }
        }
        if (s[x] == 'R') {
            int cnt = 0;
            while (f[x].size() - cnt > 1) {
                cnt++;
                int u = f[x].back();
                ans[u] = -1;
                f[x].pop_back();
            }
            if (f[x].size() - cnt)ans[f[x].back()] = 0;
            f[x].clear();
        }
        };
    dfs(dfs, 1);
    for (int i = 1;i <= n;i++)cout << ans[i] << " \n"[i == n];
}

(待更 $\dots$)