2024 北京市赛

K - 乘二

题目描述

你有 \(n\) 个数 \(a_1, a_2,... , a_n\)，现在你要操作 k 次，每次操作为选择一个数 \(a_i\)，将 \(a_i\) 乘 2。现在需要求出 \(k\) 次操作之后，所有数的和最小是多少。

由于答案可能很大，你只需要输出其对 \(10^9 + 7\) 取模的结果即可。

输入

第一行输入两个数 \(n, k(1 \leq n \leq 2 \times 10^5, 0 \leq k \leq 10^9)\)。第二行输入 \(n\) 个整数，第 \(i\) 个整数表示 \(ai(1 \leq ai \leq 10^9)\)。

输出

输出一行一个整数，表示 \(k\) 次操作后所有数之和最小值对 \(10^9 + 7\) 取模的结果。注意是最小值对 \(10^9 + 7\) 取模，而不是对 \(10^9 + 7\) 取模后的最小值。

题解

总体来说是一道比较简单的签到题，但是由于太久没有训练还是出了很多莫名其妙的问题，包括但不限于快速幂板子敲出两个 bug ...

首先，最优解是显然的，我们可以每次选择最小值，对其乘 2，可以保证答案最小。

选择的次数在 \(10^9\) 的数量级，很容易想到：首先暴力模拟选择最小值并乘 2 的过程，直到 \(a_i\) 中的最小值大于等于 \(2 \times \max(a_i)\) 为止。此后的选择可以平均分配到每一个数上，因为所有数一起乘 2 并不改变数之间的大小关系。

对于 \(k \% n\) 次不足以将每个数乘 2 的余量，我们应该将其按照从小到大的顺序分配到前 \(k \% n\) 个数上。

这里有个关键的问题导致我们长时间没有通过：选择最小值并乘 2 时，我们使用的是优先队列进行模拟；在处理余量时，我们仍然使用了优先队列，但因为处理余量时我们同时对超过 \(10^9 + 7\) 的值取模，破坏了正确的大小关系，导致对余量的处理出现了错误。

发现这一问题后，我们考虑在暴力模拟结束之后将数从优先队列中取出，按顺序放在数组中，再进行余量的分配。

AC 代码

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

#define int long long
const int mod = 1e9 + 7;

int qpow(int a, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) ans = (ans * a) % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return ans;
}

void solve() {
    int n, k;
    cin >> n >> k;
    int maxn = -1;
    priority_queue<int, vector<int>, greater<int>> Q;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        maxn = max(num, maxn);
        Q.push(num);
    }
    while (k-- && Q.top() < maxn) {
        int num = Q.top() * 2;
        Q.pop();
        Q.push(num);
    } 
    vector<int> tmp(n);
    for (int i = 0; i < n; i++) {
        tmp[i] = Q.top();
        Q.pop();
    }
    k++;
    int loop = k / n;
    k = k % n;
    for (int i = 0; i < k; i++) {
        tmp[i] = tmp[i] * 2 % mod;
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum = (sum + tmp[i]) % mod;
    }
    sum = sum * qpow(2, loop) % mod;
    cout << sum << '\n';
} 

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--) {
        solve();
    }
}

D - 树

题目描述

五一假期到了，Alice 和 Bob 都到了城市 P 旅游，城市 P 中有 n 个景点，而这 n 个景点之间的道路构成了一棵树。

Alice 的旅行规划中，有 \(c\) 个目标景点，一开始，Alice 会直接出现在景点 \(a_1\)，然后顺着最短路，沿着城市 \(P\) 中的道路到达 \(a_2\)（她同样会路过最短路上的其它景点），然后再从 \(a_2\) 前往 \(a_3\)，......，最后 Alice 抵达 \(a_c\) 过后，她会直接离开城市 \(P\)。

Bob 同样也来到了城市 \(P\)，在整个五一期间，他和 Alice 在 \(m\) 个景点相遇过，其中第 \(i\) 次是在景点 \(b_i\) 相遇。

Bob 想要知道，Alice 在五一期间最少定下了多少个目标景点，也即可能的 c 的最小值。Bob 的记忆已经比较模糊了，所以他会修改多次数组 b，你需要给出每一次修改后的最小的可能的 c。

输入

第一行两个正整数 \(n, m, q\)，表示树的节点数，序列 \(b\) 的长度，以及修改个数。

下面 \(n - 1\) 行，每行两个正整数 \(u_i, v_i\)，依次描述了树的每一条边。

下面一行 \(m\) 个正整数表示数组 \(b\)。

下面 \(q\) 行，每行两个正整数 \(p_i, w_i\)，表示将 \(b_{p_i}\) 修改为 \(w_i\)。

\(1 \leq n, m, q \leq 2 \times 10^5\), \(3 \leq n\)

\(1 \leq u_i, v_i, w_i \leq n\), \(1 \leq p_i \leq m\)。

对于任意时刻，\(\forall 1 \leq i < m : b_i \neq b_{i+1}\)。

输出

一共 \(q\) 行，每行一个正整数表示答案。

题解

如果 Bob 和 Alice 相遇，共有两种可能，一种是 Alice 的目标就是这个景点，另一种是这个景点恰好在 Alice 上一个目标到下一个目标的路径上。

因此实际上我们只需要使用数组 \(b\) 的长度减去连续三元组共路径的数量即可，因为连续三元组在同一链上可以消去中间元素，认为其是路过的景点。

修改 \(b\) 数组时只需要考虑包括修改元素的三个三元组即可。

判断三元组是否共链，可以使用 LCA，设三元组分别是 \(b_i, b_{i+1}, b_{i+2}\)，记 \(left = lca(b_i, b_{i+1})\)，\(right = lca(b_{i+1}, b_{i+2})\) 以及 \(mid = lca(b_i, b_{i+2})\)，如果 \(left = b_{i+1}\) 且 \(mid = right\) 或者 \(right = b_{i + 1}\) 且 \(mid = left\)；则说明这三个点共链。return (x == b && y == z) || (x == z && y == b);

AC 代码

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

#define int long long
const int mod = 1e9 + 7;



signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--) {
        solve();
    }
}