【杭电多校比赛记录】2025“钉耙编程”中国大学生算法设计春季联赛（6）

xjipSl

比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18822660
开题 + 补题情况

今天打完蓝桥杯，还是 ACM 赛制好玩啊~~
这场题相对而言比较简单，也是汲取了上次的教训，做题节奏放慢了，稍微细心了点，打出了历史最佳战绩，虽然还是不小心 WA 了两发。

1001 - 烤羊

签到题，枚举调料的使用，可以使用二进制枚举，注意选取的不能超过目的值。
点击查看代码（赛时代码写得依托）void solve(){    i64 k, a, b, c;std::cin >> k >> a >> b >> c;    if(a == k || b == k || c == k) {        std::cout << 0 << '\n';        return;    }    if(a + b == k || b + c == k || a + c == k) {        std::cout << 0 << '\n';        return;    }    if(a + b + c == k) {        std::cout << 0 << '\n';        return;    }    if(a + b + c < k) {        std::cout << k - a - b - c << '\n';        return;    }    auto get = [&](i64 x) -> i64 {        if(x > k)return inf64;        return k - x;    };    i64 ans = inf64;    if(a + b + c > k) {        ans = std::min(ans, get(a));        ans = std::min(ans, get(b));        ans = std::min(ans, get(c));        ans = std::min(ans, get(a + b));        ans = std::min(ans, get(a + c));        ans = std::min(ans, get(b + c));        ans = std::min(ans, get(a + b + c));        if(ans == inf64)ans = k;        std::cout << ans << '\n';        return;    }}1003 - 抹茶

连续区间贪心选取，很明显的双指针题。
点击查看代码void solve(){    int n;std::cin >> n;    std::vector<i64> a(n + 1), b(n + 1);    for(int i = 1;i <= n;i ++) {        std::cin >> a;    }    for(int i = 1;i <= n;i ++) {        std::cin >> b;    }    i64 ans = 0;    for(int i = 1, j = 0;i <= n;i = j + 1) {        while(j + 1 <= n && a[j + 1] + b[j + 1] == a + b) {            j ++;        }        i64 tmp = 0;        for(int k = i;k <= j;k ++) {            tmp += a[k] * (j - i + 1);        }        ans = std::max(ans, tmp);    }    std::cout << ans << '\n';}1007 - 双相

要想最大，肯定是优先选最大的，将两种颜色的分数分别放入两个优先队列，然后模拟选取，直到选不了一人无法移动为止。
点击查看代码void solve(){    int n;std::cin >> n;    std::vector<i64> a(n + 1);    std::string s;    for(int i = 1;i <= n;i ++)std::cin >> a;    std::cin >> s;    s = ' ' + s;    std::priority_queue<i64> r, b;    for(int i = 1;i <= n;i ++) {        if(s == 'R') {            r.push(a);        } else {            b.push(a);        }    }    i64 ans = 0;    int sum = 0;    while(true) {        sum ++;        if(sum & 1) {            if(!r.size()) {                break;            }            ans += r.top();            r.pop();        } else {            if(!b.size()) {                break;            }            ans += b.top();            b.pop();        }    }    std::cout << ans << '\n';}1008 - 天使

对于此题，我们可以先将范围缩小，假设只有三个使徒，考虑他们的结合顺序，不难发现：

\[a \times b + (a + b) \times c = a \times c + (a + c) \times b = b \times c + (b + c) \times a\]

因此，不管怎么结合，最后的答案都不会变化，结合后的又可以和其他的进行结合，那么，把这个结论推广到 \(n\) 个使徒同样成立。
因此不管怎么结合，最后的答案都一样。
所以，我们只需要从左到右结合算出答案，然后用 \(\sum_{i = 2}^n C_i^2\) 算出种类数即可。
点击查看代码（省略了取模类）Z C(Z n) {    return n * (n - 1) / 2;}void solve(){    int n;std::cin >> n;    std::vector<i64> a(n + 1);    for(int i = 1;i <= n;i ++)std::cin >> a;    Z ans = 0;    Z now = a[1];    for(int i = 2;i <= n;i ++) {        ans += now * a;        now += a;    }    Z sum = 1;    for(int i = n;i >= 2;i --) {        sum *= C(i);    }    std::cout << ans << ' ' << sum << '\n';}1002 - 英逃

首先需要观察出答案是具有单调性的。
为什么？
假设修改区间 \([l, r]\) 是可以达到题目要求的，那么对于 \([l - 1, r]\)，可以分析以下两种情况（区间 \([l, r + 1]\) 同理）：

• \(a_{l - 1} \geq \max_{i = l}^ra_i\)（如下图，黑色为修改前，红色为修改后，下同）：
  
  对于区间 \([l, r]\)，它们对代价的贡献无变化，仍为 \(0\)，但对于左边这个新增的 \(a_{l - 1}\)，由于相邻两个数的差值变为了 \(0\)，因此对代价的贡献变小了，那么如果修改区间 \([l, r]\) 能达到题目目的，修改区间 \([l - 1, r]\) 同样能达到题目目的。
  
• \(a_{l - 1} < \max_{i = l}^ra_i\)，此时继续分两种情况讨论：
  
  
  
  • \(a_{l - 2} \leq a_{l - 1}\)（如下图）：
    
    对于这种情况，我们可以发现，\(a_{l - 1}\) 和 \(\max_{i = l}^ra_i\) 的差值缩小了 \(\max_{i = l}^ra_i - a_{l - 1}\)，\(a_{l - 1}\) 和 \(a_{l - 2}\) 的差值增大了 \(\max_{i = l}^ra_i - a_{l - 1}\)，因此对代价的贡献无变化，那么如果修改区间 \([l, r]\) 能达到题目目的，修改区间 \([l - 1, r]\) 同样能达到题目目的。
    
  • \(a_{l - 2} > a_{l - 1}\)（如下图）：
    
    对于这种情况，我们可以发现，\(a_{l - 1}\) 和 \(\max_{i = l}^ra_i\) 的差值缩小了 \(\max_{i = l}^ra_i - a_{l - 1}\)，\(a_{l - 1}\) 和 \(a_{l - 2}\) 的差值缩小了 \(\max_{i = l}^ra_i - a_{l - 1}\)，因此对代价的贡献缩小了 \(2 \times (\max_{i = l}^ra_i - a_{l - 1})\)，那么如果修改区间 \([l, r]\) 能达到题目目的，修改区间 \([l - 1, r]\) 同样能达到题目目的。
    
  
  

因此，答案具有单调性，可以二分。
我们首先记录一下差分的绝对值以及差分的绝对值的前缀和，使用 ST 表来维护区间最值，然后进行二分答案，对每个二分到的区间长度，遍历所有可能的修改区间，更改修改后的代价总和，判断是否可能达到题目要求，在所有可能的答案中取最小即可。
点击查看代码void solve(){    int n;    i64 x;    std::cin >> n >> x;    std::vector<i64> a(n + 1);    for(int i = 1;i <= n;i ++)std::cin >> a;        std::vector<i64> d(n + 1);    for(int i = 2;i <= n;i ++) {        d = abs(a - a[i - 1]);    }        std::vector<i64> pre(n + 1);    for(int i = 2;i <= n;i ++) {        pre = pre[i - 1] + d;    }        if(pre[n] <= x) {        std::cout << 0 << '\n';        return;    }        std::vector<std::array<i64, 40>> st(n + 1);        for(int i = 1;i <= n;i ++) {        st[0] = a;    }        int mx = std::__lg(n);    for(int k = 1;k <= mx;k ++) {        for(int i = 1;i + (1 << (k - 1)) <= n;i ++) {            st[k] = std::max(st[k - 1], st[i + (1 << (k - 1))][k - 1]);        }    }    auto getmx = [&](int l, int r) -> i64 {        int s = std::__lg(r - l + 1);        return std::max(st[l], st[r - (1 << s) + 1]);    };        auto check = [&](i64 m) -> bool {        i64 tmp = pre[n];        for(int i = 1;i <= n - m + 1;i ++) {            tmp = pre[n];            tmp -= pre[i + m - 1] - pre;            if(i != 1)tmp -= abs(a - a[i - 1]);            if(i + m - 1 != n)tmp -= abs(a[i + m] - a[i + m - 1]);            i64 mx = getmx(i, i + m - 1);            if(i != 1)tmp += abs(mx - a[i - 1]);            if(i + m - 1 != n)tmp += abs(a[i + m] - mx);                        if(tmp <= x)return true;        }        return false;    };        int l = 0, r = n + 1;    while(l + 1 < r) {        int mid = l + r >> 1;        if(check(mid))r = mid;        else l = mid;    }    std::cout << r << '\n';}1010 - 章鱼

这题是很明显的换根 DP。
首先我们考虑一下，当一个点是一对点的 \(LCA\) 时，什么样的点对的 \(LCA\) 是它。

• 自己和自己的 \(LCA\) 都是自己。
  
• 对于这个点，它的子树（不包含父节点那个子树）中任选两个子树，两个子树中各自任选一个点，\(LCA\) 是它自己。
  
• 对于这个点，从它的子树（不包含父节点那个子树）中任选一个点，和这个点的 \(LCA\) 是它自己。
  

那么，思路也就出来了，对于每个结点为 \(LCA\) 时，逐个计算，当一个结点作为根时，除了根所在的这棵子树，对其他的子树按上述规则进行计数，对于每一棵子树，无论这棵子树哪个结点作为根，计算得到的答案都是相同的，因为都相当于是把这棵子树变成了父子树，这棵子树的结点都不可能和任何结点的 \(LCA\) 是当前结点。
换根 DP 足以解决这个问题。
点击查看代码void solve(){    int n;std::cin >> n;    std::vector<std::vector<int>> g(n + 1);    for(int i = 1;i < n;i ++) {        int u, v;std::cin >> u >> v;        g.push_back(v);        g[v].push_back(u);    }    std::vector<int> sz(n + 1);    auto dfs = [&](auto &&self, int st, int pre) -> void {        sz[st] = 1;        for(auto &i : g[st]) {            if(i == pre)continue;            self(self, i, st);            sz[st] += sz;        }    };    dfs(dfs, 1, 0);    std::vector<i64> ans(n + 1);    auto C = [](i64 n) -> i64 {        return n * (n - 1) / 2;    };    auto dfs1 = [&](auto &&self, int st, int pre) -> void {        int n = g[st].size();        std::vector<i64> szpre(n + 1), Cpre(n + 1);        for(int i = 1;i <= n;i ++) {            if(g[st][i - 1] == pre)szpre = szpre[i - 1] + sz[1] - sz[st];            else szpre = szpre[i - 1] + sz[g[st][i - 1]];            if(g[st][i - 1] == pre)Cpre = Cpre[i - 1] + C(sz[1] - sz[st]);            else Cpre = Cpre[i - 1] + C(sz[g[st][i - 1]]);        }        for(int i = 1;i <= n;i ++) {            ans[st] += (szpre - szpre[i - 1]) * (C(szpre[i - 1] + szpre[n] - szpre) - (Cpre[i - 1] + Cpre[n] - Cpre));            ans[st] += (szpre - szpre[i - 1]) * (szpre[i - 1] + szpre[n] - szpre);        }        ans[st] += sz[1] - 1;        ans[st] += C(szpre[n]) - Cpre[n];        for(auto &i : g[st]) {            if(i == pre)continue;            self(self, i, st);        }    };    dfs1(dfs1, 1, 0);    for(int i = 1;i <= n;i ++) {        ans += sz[1];        std::cout << ans << " \n"[i == n];    }}