【2024暑110】ACM暑期第五次测验（个人赛）题解

A - 快速幂

Solution

由于 $p o w (A, B)$ 非常大，无法直接计算。我们如何在不实际计算它们的情况下进行比较？

首先，我们将找到 $p o w (A, C)$ 的符号。如果 $A$ 为负且 $C$ 为奇数，则它为负数；否则为非负数

如果 $p o w (A, C)$ 和 $p o w (B, C)$ 的符号相同，直接比较 $| A |$ 和 $| B |$ 即可

Code

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

int main(){
    int a, b, c; cin >> a >> b >> c;
    if (c % 2 == 0)
        cout << (abs(a) < abs(b) ? "<" : abs(a) == abs(b) ? "=" : ">") << endl;
    else
        cout << (a > b ? ">" : a == b ? "=" : "<") << endl;
    return 0;
}

B - 存钱

Solution

签到题，直接模拟即可

C - Imbalanced XiaoMo

Question

给出一个序列 $a_{i}$ ，需要在 $a_{i}$ 中插入一个数 $x$ ，使得 $a_{i} - a_{i - 1} (2 \leq i \leq n)$ 的最大值最小，其中 $x$ 是序列 ${d}$ 和 ${f}$ 中各取一个数的加和

Solution #1

我们想要最小化最大值，那么肯定需要把最大的间隙缩小，如果最大的间隙有两个，那么最大的间隙就是答案，否则能缩小最大间隙

思考怎样缩小最大间隙才能使得最大值最小，肯定是对半分最小的间隙，假设 $m i d = (a_{i} + a_{i - 1}) / 2$ ，则需要，找到最接近的 $m i d$ 的 $f_{j} + d_{k}$

这是一个经典问题，我们可以用二分或者双指针解决

Code #1

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int INF = 1e18;
void solve() {
    int n, m, k; cin >> n >> m >> k;
    vector<int> a(n + 1), d(m + 1), f(k + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> d[i];
    for (int i = 1; i <= k; i++) cin >> f[i];
    pii mx1 = {-1,0}, mx2 = {-1,0};
    for (int i = 1; i < n; i++) {
        int x = a[i + 1] - a[i];
        if (x > mx1.first) { mx2 = mx1; mx1 = {x, i}; }
        else if (x > mx2.first) { mx2 = {x, i}; }
    }
    if (mx1.first == mx2.first) {
        cout << mx1.first << '\n';
        return ;
    }
    // 把 pos1 的位置拆开
    int mid = (a[mx1.second] + a[mx1.second + 1]) / 2;
    sort (d.begin() + 1, d.end());
    sort (f.begin() + 1, f.end());
    int ret = mx1.first;
    for (int i = 1; i <= m; i++) {

        auto check = [&](int pos) {
            if (pos < 1 || pos > k) return INF;
            int x = d[i] + f[pos];
            if (!(x > a[mx1.second] && x < a[mx1.second + 1])) return INF;
            return max (x - a[mx1.second], a[mx1.second + 1] - x);
        };

        int pos = lower_bound(f.begin() + 1, f.end(), mid - d[i]) - f.begin();
        ret = min (ret, check(pos));
        ret = min (ret, check(pos - 1));
        ret = min (ret, check(pos + 1));
    }
    cout << max (mx2.first, ret) << '\n';
}

signed main() {
    int t; cin >> t;
    while (t--) solve();
}

Solution #2

“使得最大值最小”是一个经典的二分答案模型，我们计算出在一个题都不添加的情况下的不平衡性 $s$ ，二分最终答案的范围为 $1 \leq a n s \leq s$ 。

问题就变成了能否通过添加一道题使得最终的不平衡性小于等于 $x$ 。考虑所有的 $2 \leq i \leq n$ 且 $a_{i} - a_{i - 1} > x$ 。如果这样的 $i$ 有大于 1 个，显然添加一个题目无法使得最终的不平衡性减少到 $x$ 及以下。如果没有这样的 $i$ ，显然一定可以的。难点就在于这样的 $i$ 恰好有一个。

如果对于这个 $i$ ，有 $a_{i} - a_{i - 1} > 2 x$ ，那么就算恰好能够添加一道题使得它的难度在这段区间的正中间，最终的不平衡性也是大于 $x$ 的，直接 pass 掉。否则，我们就需要判断是否能找到一对 $u$ 和 $v (1 \leq u \leq m 且 1 \leq v \leq k)$ 使得 $a_{i} - x \leq d_{u} + f_{v} \leq a_{i - 1} + x$ 。我们可以枚举 $u$ ，在二分出最小的大于等于 $a_{i} - x$ 的 $d_{u} + f_{v}$ 是否小于等于 $a_{i - 1} + x$ 。若能有一个 $u$ 使得该问题的答案为“是”，显然就是可以的，如果“一个”都没有就不行。

Code #2

#include <bits/stdc++.h>
#define N 110000
#define M 220000
#define K 220000
#define int long long
using namespace std;

int t, n, m, k, a[N], d[M], f[K];

bool judge(int x);

signed main() {
    scanf("%lld", &t);
    while (t--) {
        scanf("%lld%lld%lld", &n, &m, &k);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= m; i++) scanf("%d", &d[i]);
        sort(d + 1, d + 1 + m);
        for (int i = 1; i <= k; i++) scanf("%d", &f[i]);
        sort(f + 1, f + 1 + k);
        
        int s = 0;
        for (int i = 2; i <= n; i++) 
            s = max(s, a[i] - a[i - 1]);
        
        int l = 0, r = s + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (judge(mid) == false)
                l = mid;
            else
                r = mid;
        }
        printf("%lld\n", r);
    }
    return 0;
}

bool judge(int x) {
    int id = 0;
    for (int i = 2; i <= n; i++) {
        if (a[i] - a[i - 1] > x) {
            if (id != 0) 
                return false;
            else 
                id = i;
        }
    }
    if (id == 0) 
        return true;
    if (a[id] - a[id - 1] > 2 * x) 
        return false;
    
    int mbl = a[id] - x, mbr = a[id - 1] + x;
    bool flag = false;
    
    for (int i = 1; i <= m; i++) {
        int l = 0, r = k + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (d[i] + f[mid] < mbl)
                l = mid;
            else
                r = mid;
        }
        if (l != k && d[i] + f[l + 1] <= mbr) {
            flag = true;
            break;
        }
    }
    return flag;
}

D - dijikstra

Solution

由于边权都相同，考虑使用 bfs 得到最短路

我们在 bfs 时，需要记录下两个值：起点到 $i$ 的最短路 $d$ 和走到 $d$ 的方案数 $c$

对于 $i$ 的下一个节点 $j$ 如果满足 $d_{i} + 1 = d_{j}$ 则， $i \to j$ 是一条走到 $j$ 的最短路，所以 $c_{j} = c_{j} + c_{i}$

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int TT = 100003;
using pii = pair<int, int>;

int main() {
    ios::sync_with_stdio(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> vis(n + 1, 0);
    vector<pii> dis(n + 1, {0, 0});
    queue<int> q;
    vis[1] = 1;  q.push(1); dis[1] = {0, 1};

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                auto [d, c] = dis[u];
                auto &[d_, c_] = dis[v];
                d_ = d + 1; c_ = c;
                q.push(v);
            }
            else {
                auto [d, c] = dis[u];
                auto &[d_, c_] = dis[v];
                if (d + 1 == d_) c_ = (c_ + c) % TT;
            }
        }
    }

    for (int i = 1; i <= n; i++) 
       cout << dis[i].second << '\n';

    return 0;
}

E - 约数最大值

Solution

有点类似于 PTA 题，for 循环枚举 $[l, r]$ 之间的所有数 $x$ ，然后使用 $O (\sqrt{x})$ 的复杂度来找约数个数，总时间复杂度为 $O ((r - l) \sqrt{x})$