第 101 次训练 · 题解 ¶

共八题（A–H），难度从入门到数据结构压轴逐级递进。
每题附 C++、Java、Python 参考实现。

题目总览 ¶

题号	分值	洛谷 ID	题目	核心知识点
A	1	U722360	嗯对	字符串拼接、输入输出
B	1	U722380	嗯对2	数位和、整除性质
C	2	U724371	嘉豪的盯盘	时间换算、取模
D	2	U724372	嘉豪的密码	字符串循环移位
E	2	U724373	嘉豪的全对	前缀和、区间查询
F	3	U724375	嘉豪的组队	哈希表、两数之和
G	4	U724376	嘉豪的爬楼	两维 DP、滚动数组
H	5	U724463	嘉豪的低谷	单调栈、贡献法

A题 · 嗯对（1 分） ¶

项目	内容
洛谷 ID	U722360
标签	模拟、字符串、输入输出
复杂度	$O(\text{总长度})$

题目大意 ¶

给定 $N$ 行字符串，按输入顺序首尾相连拼成一行输出。

思路 ¶

循环读入 $N$ 行字符串，依次累加拼接到结果串末尾，最后一次性输出。注意 $N$ 最大 $10^{18}$，用 long long 存储（实际数据总长度不超过 $2\times10^7$，正常读入即可）。

参考代码 ¶

C++ ¶

#include <iostream>
#include <string>
using namespace std;

int main() {
    long long N;
    cin >> N;

    string ans;
    for (long long i = 0; i < N; i++) {
        string s;
        cin >> s;
        ans += s;
    }
    cout << ans << endl;
    return 0;
}

Java ¶

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();

        StringBuilder ans = new StringBuilder();
        for (long i = 0; i < N; i++) {
            ans.append(sc.next());
        }
        System.out.println(ans);
    }
}

Python ¶

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    print(''.join(data[1:1 + n]))

if __name__ == "__main__":
    main()

B题 · 嗯对2（1 分） ¶

项目	内容
洛谷 ID	U722380
标签	数论、整除
复杂度	$O(K)$

题目大意 ¶

给定一个 $K$ 位数字串 $S$，判断它代表的数字是否是 $9$ 的倍数。

思路 ¶

一个数能被 $9$ 整除，当且仅当其各位数字之和能被 $9$ 整除。由于 $K$ 可达 $10^6$，不能把整串转成整数，直接遍历字符累加数位和，再判断 sum % 9 == 0。

参考代码 ¶

C++ ¶

#include <iostream>
#include <string>
using namespace std;

int main() {
    long long K;
    string S;
    cin >> K >> S;

    long long sum = 0;
    for (char c : S) sum += (c - '0');

    cout << (sum % 9 == 0 ? "Yes" : "No") << endl;
    return 0;
}

Java ¶

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long K = sc.nextLong();
        String S = sc.next();

        long sum = 0;
        for (char c : S.toCharArray()) {
            sum += (c - '0');
        }
        System.out.println(sum % 9 == 0 ? "Yes" : "No");
    }
}

Python ¶

import sys

def main():
    data = sys.stdin.read().split()
    s = data[1]
    print("Yes" if sum(ord(c) - 48 for c in s) % 9 == 0 else "No")

if __name__ == "__main__":
    main()

C题 · 嘉豪的盯盘（2 分） ¶

项目	内容
洛谷 ID	U724371
标签	时间换算、取模、格式化输出
复杂度	$O(1)$

题目大意 ¶

给定 24 小时制时间 HH:MM 和分钟数 $m$，求 $m$ 分钟后的时间。

思路 ¶

换算成总分钟数：total = HH * 60 + MM + m，再对一天（$1440$ 分钟）取模，输出 total/60 与 total%60，补前导零。

参考代码 ¶

C++ ¶

#include <cstdio>

int main() {
    int HH, MM, m;
    scanf("%d:%d", &HH, &MM);
    scanf("%d", &m);

    int total = HH * 60 + MM + m;
    total %= 1440;

    printf("%02d:%02d\n", total / 60, total % 60);
    return 0;
}

Java ¶

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String t = sc.next();
        int m = sc.nextInt();

        String[] parts = t.split(":");
        int HH = Integer.parseInt(parts[0]);
        int MM = Integer.parseInt(parts[1]);

        int total = (HH * 60 + MM + m) % 1440;
        System.out.printf("%02d:%02d%n", total / 60, total % 60);
    }
}

Python ¶

import sys

def main():
    data = sys.stdin.read().split()
    hh, mm = map(int, data[0].split(':'))
    m = int(data[1])
    total = (hh * 60 + mm + m) % 1440
    print(f"{total // 60:02d}:{total % 60:02d}")

if __name__ == "__main__":
    main()

D题 · 嘉豪的密码（2 分） ¶

项目	内容
洛谷 ID	U724372
标签	字符串、循环移位、取模
复杂度	$O(

题目大意 ¶

把字符串 $S$ 的每个小写字母在字母表内循环后移 $k$ 位，z 后移回到 a。

思路 ¶

对每个字符 $c$，c' = (c - 'a' + k) % 26 + 'a'。注意 $k$ 可达 $10^9$，先 k %= 26 再运算。

参考代码 ¶

C++ ¶

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    long long k;
    cin >> s >> k;

    int shift = k % 26;
    for (char& c : s) {
        c = (c - 'a' + shift) % 26 + 'a';
    }
    cout << s << endl;
    return 0;
}

Java ¶

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        long k = sc.nextLong();

        int shift = (int)(k % 26);
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            sb.append((char)('a' + (c - 'a' + shift) % 26));
        }
        System.out.println(sb);
    }
}

Python ¶

import sys

def main():
    data = sys.stdin.read().split()
    s = data[0]
    k = int(data[1])
    shift = k % 26
    print(''.join(chr((ord(c) - 97 + shift) % 26 + 97) for c in s))

if __name__ == "__main__":
    main()

E题 · 嘉豪的全对（2 分） ¶

项目	内容
洛谷 ID	U724373
标签	前缀和、区间查询
复杂度	$O(n + q)$

题目大意 ¶

$n$ 个数 $a_1,\dots,a_n$，$q$ 次询问区间 $[l,r]$ 的和。

思路 ¶

预处理前缀和 pre[i] = a[1] + ... + a[i]，询问回答 pre[r] - pre[l-1]。注意用 64 位整数。

参考代码 ¶

C++ ¶

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<ll> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << '\n';
    }
    return 0;
}

Java ¶

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        long[] pre = new long[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + Long.parseLong(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            sb.append(pre[r] - pre[l - 1]).append('\n');
        }
        System.out.print(sb);
    }
}

Python ¶

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    n = int(next(it))
    q = int(next(it))

    pre = [0] * (n + 1)
    for i in range(1, n + 1):
        pre[i] = pre[i - 1] + int(next(it))

    out = []
    for _ in range(q):
        l = int(next(it))
        r = int(next(it))
        out.append(str(pre[r] - pre[l - 1]))
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == "__main__":
    main()

F题 · 嘉豪的组队（3 分） ¶

项目	内容
洛谷 ID	U724375
标签	哈希表、两数之和、组合计数
复杂度	$O(n)$

题目大意 ¶

$n$ 个数中选两个下标 $(i<j)$，问有多少对满足 $a_i + a_j = K$。

思路 ¶

哈希表统计每个值的出现次数。遍历每个不同的 $x$，令 $y = K - x$：

$x < y$：贡献 cnt[x] * cnt[y]；
$x = y$：贡献 cnt[x] * (cnt[x] - 1) / 2。

只处理 $x \le y$ 以免重复计数。

参考代码 ¶

C++ ¶

#include <iostream>
#include <unordered_map>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll K;
    cin >> n >> K;

    unordered_map<ll, ll> cnt;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        cnt[x]++;
    }

    ll ans = 0;
    for (auto& [x, cx] : cnt) {
        ll y = K - x;
        if (cnt.count(y)) {
            if (x < y) ans += cx * cnt[y];
            else if (x == y) ans += cx * (cx - 1) / 2;
        }
    }
    cout << ans << endl;
    return 0;
}

Java ¶

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        long K = Long.parseLong(st.nextToken());

        Map<Long, Long> cnt = new HashMap<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            long x = Long.parseLong(st.nextToken());
            cnt.put(x, cnt.getOrDefault(x, 0L) + 1);
        }

        long ans = 0;
        for (Map.Entry<Long, Long> e : cnt.entrySet()) {
            long x = e.getKey(), cx = e.getValue();
            long y = K - x;
            if (cnt.containsKey(y)) {
                if (x < y) {
                    ans += cx * cnt.get(y);
                } else if (x == y) {
                    ans += cx * (cx - 1) / 2;
                }
            }
        }
        System.out.println(ans);
    }
}

Python ¶

import sys
from collections import Counter

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    K = int(data[1])
    cnt = Counter(map(int, data[2:2 + n]))

    ans = 0
    for x, cx in cnt.items():
        y = K - x
        if y not in cnt:
            continue
        if x < y:
            ans += cx * cnt[y]
        elif x == y:
            ans += cx * (cx - 1) // 2
    print(ans)

if __name__ == "__main__":
    main()

G题 · 嘉豪的爬楼（4 分） ¶

项目	内容
洛谷 ID	U724376
标签	动态规划、爬楼梯变体、滚动数组
复杂度	$O(n)$ 时间，$O(1)$ 空间

题目大意 ¶

$n$ 级台阶，每次跨 1 级或 2 级，但不能连续两次都跨 1 级，求走法总数（对 $10^9+7$ 取模）。

思路 ¶

“不能连续两个 1 级”意味着最后一步的类型会影响下一步，用两维 DP：

dp[i][0]：到达第 $i$ 级、最后一步跨 1 级的方案数；
dp[i][1]：到达第 $i$ 级、最后一步跨 2 级的方案数。

转移：

dp[i][0] = dp[i-1][1]（最后一步 1 级，前一步必须 2 级）；
dp[i][1] = dp[i-2][0] + dp[i-2][1]（最后一步 2 级，前一步任意）。

用滚动数组维护 dp[i-2] 与 dp[i-1] 两组状态。

参考代码 ¶

C++ ¶

#include <iostream>
using namespace std;

const long long MOD = 1'000'000'007LL;

int main() {
    int n;
    cin >> n;

    long long a0 = 0, a1 = 1; // dp[0]
    long long b0 = a1, b1 = 0; // dp[1]

    if (n == 0) { cout << 1 << endl; return 0; }
    if (n == 1) { cout << (b0 + b1) % MOD << endl; return 0; }

    for (int i = 2; i <= n; i++) {
        long long c0 = b1;
        long long c1 = (a0 + a1) % MOD;
        a0 = b0; a1 = b1;
        b0 = c0; b1 = c1;
    }
    cout << (b0 + b1) % MOD << endl;
    return 0;
}

Java ¶

import java.util.Scanner;

public class Main {
    static final long MOD = 1_000_000_007L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long a0 = 0, a1 = 1; // dp[0]
        long b0 = a1, b1 = 0; // dp[1]

        if (n == 0) { System.out.println(1); return; }
        if (n == 1) { System.out.println((b0 + b1) % MOD); return; }

        for (int i = 2; i <= n; i++) {
            long c0 = b1;
            long c1 = (a0 + a1) % MOD;
            a0 = b0; a1 = b1;
            b0 = c0; b1 = c1;
        }

        System.out.println((b0 + b1) % MOD);
    }
}

Python ¶

import sys

MOD = 10 ** 9 + 7

def main():
    n = int(sys.stdin.read())
    if n == 0:
        print(1)
        return

    a0, a1 = 0, 1      # dp[0]
    b0, b1 = a1, 0     # dp[1]
    if n == 1:
        print((b0 + b1) % MOD)
        return

    for i in range(2, n + 1):
        c0 = b1
        c1 = (a0 + a1) % MOD
        a0, a1 = b0, b1
        b0, b1 = c0, c1

    print((b0 + b1) % MOD)

if __name__ == "__main__":
    main()

H题 · 嘉豪的低谷（5 分） ¶

项目	内容
洛谷 ID	U724463
标签	单调栈、贡献法、子区间统计
复杂度	$O(n)$

题目大意 ¶

求所有连续子区间的最小值之和：

$$\sum_{l=1}^{n}\sum_{r=l}^{n}\min_{l\le i\le r}a_i$$

思路 ¶

不按子区间枚举，而是按”每个元素作为最小值”统计贡献。对位置 $i$：

$L_i$：左边第一个严格小于 $a_i$ 的位置；
$R_i$：右边第一个小于等于 $a_i$ 的位置。

以 $a_i$ 为最小值的子区间有 $(i-L_i)\times(R_i-i)$ 个，贡献 $a_i\times(i-L_i)\times(R_i-i)$。

用单调栈 $O(n)$ 求出所有 $L_i, R_i$。左边界用”严格小于”、右边界用”小于等于”，保证相等元素不重不漏。

参考代码 ¶

C++ ¶

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> L(n + 1), R(n + 1);
    stack<int> st;

    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        L[i] = st.empty() ? 0 : st.top();
        st.push(i);
    }

    while (!st.empty()) st.pop();
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.top()] > a[i]) st.pop();
        R[i] = st.empty() ? n + 1 : st.top();
        st.push(i);
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += a[i] * (i - L[i]) * (R[i] - i);
    }
    cout << ans << '\n';
    return 0;
}

Java ¶

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long[] a = new long[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) a[i] = Long.parseLong(st.nextToken());

        int[] L = new int[n + 1], R = new int[n + 1];
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (int i = 1; i <= n; i++) {
            while (!stack.isEmpty() && a[stack.peek()] >= a[i]) stack.pop();
            L[i] = stack.isEmpty() ? 0 : stack.peek();
            stack.push(i);
        }

        stack.clear();
        for (int i = n; i >= 1; i--) {
            while (!stack.isEmpty() && a[stack.peek()] > a[i]) stack.pop();
            R[i] = stack.isEmpty() ? n + 1 : stack.peek();
            stack.push(i);
        }

        long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += a[i] * (i - L[i]) * (R[i] - i);
        }
        System.out.println(ans);
    }
}

Python ¶

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [0] + [int(x) for x in data[1:1 + n]]

    L = [0] * (n + 1)
    R = [0] * (n + 1)

    stack = []
    for i in range(1, n + 1):
        while stack and a[stack[-1]] >= a[i]:
            stack.pop()
        L[i] = stack[-1] if stack else 0
        stack.append(i)

    stack = []
    for i in range(n, 0, -1):
        while stack and a[stack[-1]] > a[i]:
            stack.pop()
        R[i] = stack[-1] if stack else n + 1
        stack.append(i)

    ans = 0
    for i in range(1, n + 1):
        ans += a[i] * (i - L[i]) * (R[i] - i)

    print(ans)

if __name__ == "__main__":
    main()

总结 ¶

题号	分值	题目	核心知识点	关键易错点
A	1	嗯对	字符串拼接	$N$ 用 `long long`、输出不加多余换行
B	1	嗯对2	数位和整除	不能把整串转整数，用数位和
C	2	嘉豪的盯盘	时间换算	忘记 `% 1440`、不补前导零
D	2	嘉豪的密码	循环移位	忘记 `k %= 26` 导致溢出
E	2	嘉豪的全对	前缀和	未用 64 位整数、`pre[0]` 缺失
F	3	嘉豪的组队	哈希计数	去重（`x < y`）、相同值用组合数
G	4	嘉豪的爬楼	两维 DP	状态设计（最后一步类型）
H	5	嘉豪的低谷	单调栈 + 贡献法	相等元素左右边界去重

八道题从 1 分到 5 分，覆盖了：字符串拼接 → 整除性质 → 时间换算 → 循环移位 → 前缀和 → 哈希计数 → 动态规划 → 单调栈与贡献法，适合作为一次完整的入门到进阶训练。

第 101 次训练 · 题解 ¶

题目总览 ¶

A题 · 嗯对（1 分） ¶

题目大意 ¶

思路 ¶

参考代码 ¶

C++ ¶

Java ¶

Python ¶

B题 · 嗯对2（1 分） ¶

题目大意 ¶

思路 ¶

参考代码 ¶

C++ ¶

Java ¶

Python ¶

C题 · 嘉豪的盯盘（2 分） ¶

题目大意 ¶

思路 ¶

参考代码 ¶

C++ ¶

Java ¶

Python ¶

D题 · 嘉豪的密码（2 分） ¶

题目大意 ¶

思路 ¶

参考代码 ¶

C++ ¶

Java ¶

Python ¶

E题 · 嘉豪的全对（2 分） ¶

题目大意 ¶

思路 ¶

参考代码 ¶

C++ ¶

Java ¶

Python ¶

F题 · 嘉豪的组队（3 分） ¶

题目大意 ¶

思路 ¶

参考代码 ¶

C++ ¶

Java ¶

Python ¶

G题 · 嘉豪的爬楼（4 分） ¶

题目大意 ¶

思路 ¶

参考代码 ¶

C++ ¶

Java ¶

Python ¶

H题 · 嘉豪的低谷（5 分） ¶

题目大意 ¶

思路 ¶

参考代码 ¶

C++ ¶

Java ¶

Python ¶

总结 ¶

💬 评论 (0)