2025 YAC Round 5 题解

比赛大图来源：pixiv_id=128074109

PS：E 题数据较水，建议学习题解的正确做法。

A 小五的读心术

出题人：MarisaMagic

题意简述

给定两个整数 $x, k$，输出 $x - k$。

解题思路 （语法）

整数最大为 $10^{18}$，C++ 需要 long long。

x, k = map(int, input().split())
print(x - k)

B 小五的字符串

出题人：MarisaMagic

题意简述

给定一个长度为 $N$ 的字符串 $S$（$N$ 为 $3$ 的倍数），输出 $S_{\frac{N}{3} +1}S_{\frac{N}{3}+2} \dots S_{\frac{2N}{3} } S_1 S_2 \dots S_{\frac{N}{3}} S_{\frac{2N}{3} +1} S_{ \frac{2N}{3} +2} \dots S_N$。

解题思路 （字符串基础）

按照题意逐个输出字符串对应位置的字符即可。或者可以使用字符串切片解决。

n = int(input())
s = input().strip()
k = n // 3
print(s[k:2*k] + s[:k] + s[2*k:])

C 小五的因数分解

出题人：MarisaMagic

题意简述

给定一个正整数 $x$，按照图下要求输出质因数分解式：

• 质因数从小到大排列；
• 乘号用 * 表示，两个质因数之间的乘号左右各有一个空格；
• 当一个质数出现多次时，合并为指数形式，指数符号用 ^ 表示。

解题思路 （质因数分解）

采用 OI Wiki 质因数分解 中的朴素算法，依次输出每个质因子。如果指数 $t > 1$，额外输出 ^t。如果当前质因子除尽后，$x \neq 1$，表明当前质因子不是最后一个质因子，需要额外输出 *。时间复杂度 $\mathcal{O}(\sqrt x)$。

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

#define fastio ios::sync_with_stdio(false), cin.tie(0)
using ll = long long;

void marisa(){
    ll x; cin >> x;
    for(ll i = 2; i * i <= x; i ++ ){
        if(x % i == 0){
            int t = 0;
            while(x % i == 0){
                x /= i;
                t ++ ;
            }
            cout << i; // 输出质因子
            if(t > 1) cout << "^" << t;
            if(x != 1) cout << " * "; // 不是最后一个质因子
        }
    }
    if(x > 1) cout << x;
}

int main(){
    fastio;

    int T = 1; // cin >> T;
    while(T -- ) marisa();
    
    return 0;
}

D 小五的完全图

出题人：MarisaMagic

题意简述

给定一个 $n$ 个点的带权无向完全图。求对于每一条边 $(u, v)$，是否存在一个点对 $(x, y)$ 使得 $x \rightarrow y$ 的所有最短路都经过 $(u, v)$。

解题思路 （Floyd）

考虑对于边 $(u, v)$ 是否存在一条 $u \rightarrow v$ 的路径可以替换掉 $(u, v)$ 这条边（即存在一条 $u \rightarrow v$ 的路径长度 $\le g_{u,v}$）。

• 如果存在，那么任意从 $x$ 经过 $u,v$ 到 $y$ 的最短路径都不会选择经过 $(u, v)$ 这条边，而是选择 $u \rightarrow v$ 的一条较短路径。故此时答案为 $0$；
• 如果不存在，那么必然存在至少一个点对 $(x,y)$ 的路径经过边 $(u,v)$（最简单的就是取 $x = u, y = v$）。故此时答案为 $1$。

特别的，当 $u = v$ 时，答案默认为 $0$。时间复杂度 $\mathcal{O}(n^3)$

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

#define fastio ios::sync_with_stdio(false), cin.tie(0)

void marisa(){
    int n; cin >> n;
    vector<vector<int>> d(n + 1, vector<int>(n + 1));
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ ) cin >> d[i][j];
    for(int k = 1; k <= n; k ++ )
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            if(i == j){ cout << '0'; continue; } 
            bool ok = true;
            for(int k = 1; k <= n; k ++ ){
                if(k != i && k != j && d[i][k] + d[k][j] <= d[i][j]){
                    ok = false; // 存在一个路径可以替换 (i,j)
                    break;
                }
            }
            cout << (ok ? '1' : '0');
        }
        cout << "\n";
    }
}

int main(){
    fastio;

    int T = 1; // cin >> T;
    while(T -- ) marisa();
    
    return 0;
}

E 小五的数列查询

出题人：MarisaMagic

题意简述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。共 $q$ 次询问，每次询问 $[l, r]$ 区间内第一个 大于 $x$ 的数的位置。特别的，如果不存在，输出 $-1$。

解题思路 （线段树，线段树上二分）

这是一道 线段树上二分 的模板题。在线段树基础上实现一个 first_ge 函数用于找到区间 $[l, r]$ 内第一个大于 $x$ 的位置：

• 若当前节点区间和查询区间无交集 或者 当前区间最大值小于等于 $x$，则直接返回 -1；
• 若当前区间为单点区间且值大于 $x$，说明找到答案，返回该点位置；
• 否则，先递归查询左子树，若左子树存在满足条件的位置，返回答案；若左子树无答案，再递归查询右子树。

时间复杂度 $\mathcal{O}(n \log n)$。

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

#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mid (l + r >> 1)
#define ls (u << 1)
#define rs (u << 1 | 1)
const int N = 2e6 + 10;

int n, q, a[N], mx[N << 2];

inline void pushup(int u){
    mx[u] = max(mx[ls], mx[rs]);
}

void build(int u, int l, int r){
    if(l == r){
        mx[u] = a[l];
        return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}

int first_ge(int u, int l, int r, int ql, int qr, int x) {
    if(l > qr || r < ql || mx[u] <= x) return qr + 1;
    if(l == r) return l;
    int pos = first_ge(ls, l, mid, ql, qr, x);
    if(pos != qr + 1) return pos;
    return first_ge(rs, mid + 1, r, ql, qr, x);
}

void marisa(){
    cin >> n >> q;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    build(1, 1, n);

    for(int i = 0, l, r, x; i < q; i ++ ){
        cin >> l >> r >> x;
        int res = first_ge(1, 1, n, l, r, x);
        cout << (res == r + 1 ? -1 : res) << "\n";
    }
}

int main(){
    fastio;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}    

F 小五的宠物训练

出题人：MarisaMagic

题意简述

有 $n$ 个小怪 $a_1, a_2, \ldots, a_n$，第 $i$ 个小怪的战斗力为 $a_i$。阿空的初始耐力值为 $M$。

定义如下流程为一场训练：

• 从第 $1$ 个小怪开始，每个小怪依次对阿空进行攻击。第 $i$ 个小怪对阿空进行攻击，阿空的耐力值 $M$ 减去 $a_i$，然后这一轮的第 $i$ 个小怪的战斗力 $a_i$ 翻倍。在这一轮的第 $n$ 个小怪攻击完后，重新从第 $1$ 个小怪开始进行下一轮。
• 当 $M \le 0$ 时，本场训练立刻结束。

每场训练结束后，阿空的耐力值恢复为初始的 $M$，每个小怪的战斗力变为这场训练之前的 $a_i$。

共 $q$ 场训练，每场训练之前小五会对区间 $[l, r]$ 内的小怪提升 $d$ 点战斗力。对于每场训练，求阿空能够承受 多少次 小怪的攻击（不包括恰好使 $M \le 0$ 的一次）。

解题思路 （懒标记线段树，线段树上二分）

对于区间加操作，考虑采用懒标记线段树进行维护。每一场训练后战斗力均会翻倍，可以发现每场训练的总轮数不会很多（最多就是 $\log_{2} M$ 级别），故每次询问可以枚举能够承受的完整轮数 $t$。

经过 $t$ 轮后，假设剩余的耐力值为 $tmp$，在最后一轮中找到整个序列前缀和最后一个小于 $tmp$ 的位置 $pos$，最终 $t \times n + pos$ 就是答案。对于找到前缀和最后一个小于 $tmp$ 的位置 $pos$，我们可以采用 线段树上二分 找到第一个前缀和大于等于 $tmp$ 的位置，再减去 $1$ 即 $pos$。

时间复杂度 $\mathcal{O}(n \log n)$。

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

#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define mid (l + r >> 1)
#define ls (u << 1)
#define rs (u << 1 | 1)
using ll = long long;
const int N = 2e5 + 10;

int n, q;
ll M, a[N], sum[N << 2], add[N << 2];

inline void pushup(int u){
    sum[u] = sum[ls] + sum[rs];
}

inline void pushdown(int u, int l, int r){
    if(add[u]){
        add[ls] += add[u];
        add[rs] += add[u];
        sum[ls] += add[u] * (mid - l + 1);
        sum[rs] += add[u] * (r - mid);
        add[u] = 0;
    }
}

void build(int u, int l, int r){
    if(l == r){
        sum[u] = a[l];
        return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}

void range_add(int u, int l, int r, int ql, int qr, ll x){
    if(ql <= l && r <= qr){
        add[u] += x;
        sum[u] += x * (r - l + 1);
        return;
    }
    pushdown(u, l, r);
    if(ql <= mid) range_add(ls, l, mid, ql, qr, x);
    if(qr > mid) range_add(rs, mid + 1, r, ql, qr, x);
    pushup(u);
}

int first_geq(int u, int l, int r, ll x, int t){
    if(sum[u] * (1ll << t) < x) return n + 1;
    if(l == r) return l; // 找到满足条件的位置
    pushdown(u, l, r);
    int pos = first_geq(ls, l, mid, x, t); // 先在左子树查找 >= x
    if(pos != n + 1) return pos; // 不满足再在右子树查找 >= x - sum[ls]
    return first_geq(rs, mid + 1, r, x - sum[ls] * (1ll << t), t);
}

void marisa(){
    cin >> n >> q >> M;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    build(1, 1, n);

    for(int i = 0, l, r; i < q; i ++ ){
        ll d; cin >> l >> r >> d;
        range_add(1, 1, n, l, r, d);
        ll tmp = M, t = 0; // 枚举完整轮数
        for( ; sum[1] * (1ll << t) < tmp; t ++ ){ 
            tmp -= sum[1] * (1ll << t);
        } // 第一个前缀和 * (1 << t) 大于等于 tmp 的位置-1
        cout << t * n + first_geq(1, 1, n, tmp, t) - 1 << "\n";
    }
}

int main(){
    fastio;

    int T = 1; // cin >> T;
    while(T -- ){
        marisa();
    }

    return 0;
}