ABC 98th 题单 · 详细题解 ¶

涵盖 AtCoder Beginner Contest 六道经典题目 + 一道附加题，从入门到进阶，逐题精讲。

目录 ¶

A题 · 五百元硬币 (ABC 150 A)
B题 · 自助取餐 (ABC 140 B)
C题 · 计票 (ABC 155 C)
D题 · 数字列队 (ABC 135 D)
E题 · 自助餐 (ABC 145 E)
F题 · 最小包围盒 (ABC 130 F)
G题 · 数学嘉豪

A题 · 五百元硬币 (ABC 150 A) ¶

项目	内容
来源	ABC 150 A — 500 Yen Coins
分数	100 分
标签	数学、条件判断

题目大意 ¶

高桥有 $K$ 枚 $500$ 日元硬币。判断总金额是否达到 $X$ 日元以上。若 $K \times 500 \ge X$ 输出 Yes，否则输出 No。

约束 ¶

$1 \le K \le 100$
$1 \le X \le 10^5$

思路 ¶

这是整场比赛的签到题。直接计算 $K \times 500$ 并与 $X$ 比较即可。时间复杂度 $O(1)$。

示例代码 ¶

Java ¶

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int X = sc.nextInt();
        System.out.println(K * 500 >= X ? "Yes" : "No");
    }
}

C++ ¶

#include <iostream>
using namespace std;

int main() {
    int K, X;
    cin >> K >> X;
cout << (K * 500 >= X ? "Yes" : "No") << endl;
    return 0;
}

Python ¶

k, x = map(int, input().split())
print("Yes" if k * 500 >= x else "No")

B题 · 自助取餐 (ABC 140 B) ¶

项目	内容
来源	ABC 140 B — Buffet
分数	200 分
标签	模拟、数组

题目大意 ¶

高桥依次吃了 $N$ 种菜，第 $i$ 道吃的是菜品 $A_i$。

吃菜品 $i$ 可获得基础满足度 $B_i$
额外奖励：若吃完菜品 $i$ 后紧接着吃菜品 $i+1$，额外获得 $C_i$

求总满足度。

约束 ¶

$2 \le N \le 20$
$A$ 是 $1 \sim N$ 的排列
$1 \le B_i, C_i \le 50$

思路 ¶

按顺序遍历 $A$：

累加每道菜的基础满足度 $B_{A_i}$
检查相邻两道菜：若 $A_i + 1 = A_{i+1}$，则额外加上 $C_{A_i}$

时间复杂度 $O(N)$。

注意：$A_i$ 是 1-indexed，代码中需减 1 转为 0-indexed。

示例代码 ¶

Java ¶

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextInt();
        int[] B = new int[N];
        for (int i = 0; i < N; i++) B[i] = sc.nextInt();
        int[] C = new int[N - 1];
        for (int i = 0; i < N - 1; i++) C[i] = sc.nextInt();

        int ans = 0;
        for (int i = 0; i < N; i++) {
            ans += B[A[i] - 1];
            if (i + 1 < N && A[i] + 1 == A[i + 1]) {
                ans += C[A[i] - 1];
            }
        }
        System.out.println(ans);
    }
}

C++ ¶

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N - 1);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];
    for (int i = 0; i < N - 1; i++) cin >> C[i];

    int ans = 0;
    for (int i = 0; i < N; i++) {
        ans += B[A[i] - 1];
        if (i + 1 < N && A[i] + 1 == A[i + 1]) {
            ans += C[A[i] - 1];
        }
    }
    cout << ans << endl;
    return 0;
}

Python ¶

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = 0
for i in range(n):
    ans += b[a[i] - 1]
    # 若吃完菜品 A[i] 后紧接着吃 A[i]+1，额外获得 C[A[i]]
    if i + 1 < n and a[i] + 1 == a[i + 1]:
        ans += c[a[i] - 1]
print(ans)

C题 · 计票 (ABC 155 C) ¶

项目	内容
来源	ABC 155 C — Poll
分数	300 分
标签	哈希表、排序、字符串

题目大意 ¶

有 $N$ 张选票，第 $i$ 张写有字符串 $S_i$。找出出现次数最多的所有字符串，按字典序升序每行输出一个。

约束 ¶

$1 \le N \le 2 \times 10^5$
$S_i$ 由小写英文字母组成，长度 $1 \sim 10$

思路 ¶

用 HashMap（C++ 用 map 或 unordered_map）统计每个字符串的出现次数——$O(N)$
遍历找出最大出现次数 maxCnt
收集所有次数等于 maxCnt 的字符串，排序后输出

时间复杂度 $O(N \log N)$（排序），但最多只有 $N$ 个不同字符串，实际很快。

为什么不能只维护最大值？ ¶

因为可能有多个字符串并列第一，必须全部输出。先统计完再筛选是最稳妥的做法。

示例代码 ¶

Java ¶

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Map<String, Integer> cnt = new HashMap<>();
        for (int i = 0; i < N; i++) {
            String s = sc.next();
            cnt.put(s, cnt.getOrDefault(s, 0) + 1);
        }

        int maxCnt = 0;
        for (int v : cnt.values()) maxCnt = Math.max(maxCnt, v);

        List<String> ans = new ArrayList<>();
        for (Map.Entry<String, Integer> e : cnt.entrySet()) {
            if (e.getValue() == maxCnt) ans.add(e.getKey());
        }
        Collections.sort(ans);
        for (String s : ans) System.out.println(s);
    }
}

C++ ¶

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

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

    int N;
    cin >> N;
    unordered_map<string, int> cnt;
    string s;
    for (int i = 0; i < N; i++) {
        cin >> s;
        cnt[s]++;
    }

    int maxCnt = 0;
    for (auto& p : cnt) maxCnt = max(maxCnt, p.second);

    vector<string> ans;
    for (auto& p : cnt) {
        if (p.second == maxCnt) ans.push_back(p.first);
    }
    sort(ans.begin(), ans.end());
    for (auto& str : ans) cout << str << '\n';

    return 0;
}

Python ¶

from collections import Counter

n = int(input())
cnt = Counter(input().strip() for _ in range(n))

max_cnt = max(cnt.values())
ans = sorted(s for s, c in cnt.items() if c == max_cnt)
print("\n".join(ans))

D题 · 数字列队 (ABC 135 D) ¶

项目	内容
来源	ABC 135 D — Digits Parade
分数	400 分
标签	动态规划、模运算

题目大意 ¶

给定字符串 $S$，每个字符为 0~9 或 ?。将每个 ? 替换为任意数字后得到一个整数（允许前导零）。

求有多少种替换方式使得到的整数 $\bmod 13 = 5$。答案对 $10^9+7$ 取模。

约束 ¶

$|S| \le 10^5$

思路 ¶

这是经典的数位 DP / 模运算 DP。

状态定义 ¶

设 $dp[i][r]$ 表示：考虑前 $i$ 个字符，组成的数除以 $13$ 余 $r$ 的方案数。

状态转移 ¶

对于第 $i$ 个字符 $S[i]$：

若 $S[i]$ 是数字 $d$（0~9）：
$$dp[i+1][(r \times 10 + d) \bmod 13] \mathrel{+}= dp[i][r]$$
若 $S[i]$ 是 ?：
对 $d = 0 \sim 9$ 分别做上述转移：
$$dp[i+1][(r \times 10 + d) \bmod 13] \mathrel{+}= dp[i][r]$$

初始化 ¶

$dp[0][0] = 1$（空串的值为 0，余数为 0）

答案 ¶

$dp[|S|][5]$，即全部字符处理完后，余数为 5 的方案数。

复杂度 ¶

状态数：$O(|S| \times 13)$
转移：$O(1)$（数字）或 $O(10)$（?）
总复杂度：$O(|S| \times 13 \times 10) \approx 1.3 \times 10^7$，在时限内完全可行。

空间优化 ¶

由于 $dp[i+1]$ 只依赖 $dp[i]$，可以用滚动数组把空间从 $O(13 \times |S|)$ 降到 $O(13)$。

示例代码 ¶

Java ¶

import java.util.Scanner;

public class Main {
    static final int MOD = 1_000_000_007;

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

        long[] dp = new long[13];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            long[] ndp = new long[13];
            char c = S.charAt(i);

            if (c == '?') {
                for (int d = 0; d <= 9; d++) {
                    for (int r = 0; r < 13; r++) {
                        int nr = (r * 10 + d) % 13;
                        ndp[nr] = (ndp[nr] + dp[r]) % MOD;
                    }
                }
            } else {
                int d = c - '0';
                for (int r = 0; r < 13; r++) {
                    int nr = (r * 10 + d) % 13;
                    ndp[nr] = (ndp[nr] + dp[r]) % MOD;
                }
            }
            dp = ndp;
        }

        System.out.println(dp[5]);
    }
}

C++ ¶

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

const int MOD = 1'000'000'007;

int main() {
    string S;
    cin >> S;
    int n = S.size();

    vector<long long> dp(13, 0);
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        vector<long long> ndp(13, 0);
        char c = S[i];

        if (c == '?') {
            for (int d = 0; d <= 9; d++) {
                for (int r = 0; r < 13; r++) {
                    int nr = (r * 10 + d) % 13;
                    ndp[nr] = (ndp[nr] + dp[r]) % MOD;
                }
            }
        } else {
            int d = c - '0';
            for (int r = 0; r < 13; r++) {
                int nr = (r * 10 + d) % 13;
                ndp[nr] = (ndp[nr] + dp[r]) % MOD;
            }
        }
        dp = move(ndp);
    }

    cout << dp[5] << endl;
    return 0;
}

Python ¶

MOD = 1_000_000_007

s = input().strip()

# dp[r] = 当前已处理前缀中，数值模 13 余 r 的方案数
dp = [0] * 13
dp[0] = 1

for ch in s:
    ndp = [0] * 13
    digits = range(10) if ch == '?' else [int(ch)]
    for d in digits:
        for r in range(13):
            nr = (r * 10 + d) % 13
            ndp[nr] = (ndp[nr] + dp[r]) % MOD
    dp = ndp

print(dp[5])

E题 · 自助餐 (ABC 145 E) ¶

项目	内容
来源	ABC 145 E — All-you-can-eat
分数	500 分
标签	动态规划、0/1 背包变形

题目大意 ¶

$N$ 种菜品，第 $i$ 种需要 $A_i$ 分钟吃完，美味度 $B_i$。

规则：
- 一次只能点一道菜，点了立刻上
- 同一种不能重复点
- 关键：从第一次点菜开始的 $T-0.5$ 分钟后不能再点新菜，但已经在吃的可以继续吃完

求最大总美味度。

约束 ¶

$2 \le N \le 3000$
$1 \le T \le 3000$
$1 \le A_i, B_i \le 3000$

思路 ¶

关键转化 ¶

$T-0.5$ 意味着：点菜的总开始时间之和必须 严格小于 $T$（因为最后一道菜可以超出时限）。

换句话说：最后一道菜可以在时刻 $t < T$ 开始时点，然后花任意时间吃完。之前所有菜的总时间必须 $< T$。

算法 ¶

这等价于：枚举最后一道菜是哪个，然后对剩下的 $N-1$ 道菜做容量为 $T-1$ 的 0/1 背包。

直接做是 $O(N^2 T)$，不可行。优化思路：

将菜品按 $A_i$ 排序（可选，为了更直观）
计算 $dp[t]$ = 前 $i$ 道菜中选若干道，总时间恰好为 $t$ 的最大美味度（$0 \le t < T$）
对于每道菜 $i$，考虑以它作为”最后一道”：
$$ans = \max(ans,\; dp[t] + B_i) \quad \text{其中 } t < T$$
$dp$ 是不包含菜品 $i$ 时的背包状态。
然后更新 $dp$，把菜品 $i$ 加入背包。

这样只需一次遍历，$O(NT)$ 时间。

实现细节：内层循环从 $T-1$ 向 $A_i$ 遍历，保证每道菜只被选一次（0/1 背包标准写法）。

示例代码 ¶

Java ¶

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int T = sc.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
            B[i] = sc.nextInt();
        }

        // dp[t]: max deliciousness with total time = t (t < T)
        int[] dp = new int[T];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        int ans = 0;
        for (int i = 0; i < N; i++) {
            // 考虑菜品 i 作为最后一道
            for (int t = 0; t < T; t++) {
                if (dp[t] >= 0) {
                    ans = Math.max(ans, dp[t] + B[i]);
                }
            }
            // 将菜品 i 加入背包
            for (int t = T - 1; t >= A[i]; t--) {
                if (dp[t - A[i]] >= 0) {
                    dp[t] = Math.max(dp[t], dp[t - A[i]] + B[i]);
                }
            }
        }

        System.out.println(ans);
    }
}

C++ ¶

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int N, T;
    cin >> N >> T;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }

    // dp[t]: max deliciousness with total time = t (t < T)
    vector<int> dp(T, -1);
    dp[0] = 0;

    int ans = 0;
    for (int i = 0; i < N; i++) {
        // 考虑菜品 i 作为最后一道
        for (int t = 0; t < T; t++) {
            if (dp[t] >= 0) {
                ans = max(ans, dp[t] + B[i]);
            }
        }
        // 将菜品 i 加入背包
        for (int t = T - 1; t >= A[i]; t--) {
            if (dp[t - A[i]] >= 0) {
                dp[t] = max(dp[t], dp[t - A[i]] + B[i]);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Python ¶

n, t = map(int, input().split())
a = []
b = []
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

# dp[time] = 总点菜时间恰好为 time（time < T）时的最大美味度
dp = [-1] * t
dp[0] = 0

ans = 0
for i in range(n):
    # 把第 i 道菜当作"最后一道"：之前所有菜的总时间必须 < T
    for tt in range(t):
        if dp[tt] >= 0:
            ans = max(ans, dp[tt] + b[i])
    # 0/1 背包：把第 i 道菜加入（倒序保证每道菜只选一次）
    for tt in range(t - 1, a[i] - 1, -1):
        if dp[tt - a[i]] >= 0:
            dp[tt] = max(dp[tt], dp[tt - a[i]] + b[i])

print(ans)

F题 · 最小包围盒 (ABC 130 F) ¶

项目	内容
来源	ABC 130 F — Minimum Bounding Box
分数	600 分
标签	数学、三分搜索 / 极值枚举、几何

题目大意 ¶

平面上有 $N$ 个点，第 $i$ 个点初始坐标 $(x_i, y_i)$，以每秒 1 单位的速度沿坐标轴方向移动：

字符	方向
`R`	$x$ 正方向
`L`	$x$ 负方向
`U`	$y$ 正方向
`D`	$y$ 负方向

可以在任意时刻让所有点停止。求 $(x_{\max} - x_{\min}) \times (y_{\max} - y_{\min})$ 的最小值。

约束 ¶

$1 \le N \le 10^5$
$-10^8 \le x_i, y_i \le 10^8$

思路 ¶

第一步：写出极值函数 ¶

每个点的坐标随时间线性变化。对 $x$ 坐标：

R：$x_i + t$
L：$x_i - t$
U / D：$x_i$（不变）

所以 $x_{\max}(t) = \max($ R类最大初始值 $+ t$，L类最大初始值 $- t$，UD类最大初始值 $)$

同理 $x_{\min}(t) = \min($ R类最小初始值 $+ t$，L类最小初始值 $- t$，UD类最小初始值 $)$

对 $y$ 坐标同理。

每个极值函数都是 若干条直线取 max 或 min，因此是分段线性的凸/凹函数。

第二步：候选时刻 ¶

宽度 $w(t) = x_{\max}(t) - x_{\min}(t)$ 和高度 $h(t) = y_{\max}(t) - y_{\min}(t)$ 都是分段线性的凸函数。

面积 $S(t) = w(t) \cdot h(t)$ 在每个分段内是二次函数 $at^2 + bt + c$。

最小值一定出现在以下位置之一：

$t = 0$（初始时刻）
分段边界点：即某两个直线相交的时刻（$x_{\max}$、$x_{\min}$、$y_{\max}$、$y_{\min}$ 的内部交点）
二次函数顶点：在某个分段内，若 $a > 0$，顶点 $t = -\frac{b}{2a}$ 可能落在区间内

由于每个极值最多由 3 条直线决定（R/L/UD 或 U/D/RL），分段点数量是 $O(1)$ 的，总候选时刻约 20~30 个。

第三步：实现 ¶

实际实现中，我们可以直接枚举所有候选时刻，计算面积取最小值。候选时刻集合：

$t = 0$
对于 $x_{\max}$ 的三条直线，两两求交点（若交点在 $t \ge 0$）
对 $x_{\min}$、$y_{\max}$、$y_{\min}$ 同理
在每两个相邻候选时刻之间，取中点 $t_{\text{mid}}$ 计算面积并检查二次函数的顶点

更简单的做法：由于候选时刻很少，直接枚举所有候选时刻 + 每个区间的几个采样点即可。

注意：用 double 计算，输出时保留足够精度。绝对/相对误差在 $10^{-9}$ 以内即可。

示例代码 ¶

Java ¶

import java.util.*;

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

        // 分类存储初始值
        long xMaxR = Long.MIN_VALUE, xMaxL = Long.MIN_VALUE, xMaxUD = Long.MIN_VALUE;
        long xMinR = Long.MAX_VALUE, xMinL = Long.MAX_VALUE, xMinUD = Long.MAX_VALUE;
        long yMaxU = Long.MIN_VALUE, yMaxD = Long.MIN_VALUE, yMaxRL = Long.MIN_VALUE;
        long yMinU = Long.MAX_VALUE, yMinD = Long.MAX_VALUE, yMinRL = Long.MAX_VALUE;

        boolean hasR = false, hasL = false, hasU = false, hasD = false;
        boolean hasUD = false, hasRL = false;

        for (int i = 0; i < N; i++) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            char d = sc.next().charAt(0);

            if (d == 'R') {
                hasR = true;
                xMaxR = Math.max(xMaxR, x);
                xMinR = Math.min(xMinR, x);
                hasRL = true;
                yMaxRL = Math.max(yMaxRL, y);
                yMinRL = Math.min(yMinRL, y);
            } else if (d == 'L') {
                hasL = true;
                xMaxL = Math.max(xMaxL, x);
                xMinL = Math.min(xMinL, x);
                hasRL = true;
                yMaxRL = Math.max(yMaxRL, y);
                yMinRL = Math.min(yMinRL, y);
            } else if (d == 'U') {
                hasU = true;
                yMaxU = Math.max(yMaxU, y);
                yMinU = Math.min(yMinU, y);
                hasUD = true;
                xMaxUD = Math.max(xMaxUD, x);
                xMinUD = Math.min(xMinUD, x);
            } else { // 'D'
                hasD = true;
                yMaxD = Math.max(yMaxD, y);
                yMinD = Math.min(yMinD, y);
                hasUD = true;
                xMaxUD = Math.max(xMaxUD, x);
                xMinUD = Math.min(xMinUD, x);
            }
        }

        // 收集候选时刻
        List<Double> cand = new ArrayList<>();
        cand.add(0.0);

        // x_max 的三条线交点: R(+t), L(-t), UD(const)
        addIntersections(cand, hasR, xMaxR, 1, hasL, xMaxL, -1);
        addIntersections(cand, hasR, xMaxR, 1, hasUD, xMaxUD, 0);
        addIntersections(cand, hasL, xMaxL, -1, hasUD, xMaxUD, 0);

        // x_min
        addIntersections(cand, hasR, xMinR, 1, hasL, xMinL, -1);
        addIntersections(cand, hasR, xMinR, 1, hasUD, xMinUD, 0);
        addIntersections(cand, hasL, xMinL, -1, hasUD, xMinUD, 0);

        // y_max
        addIntersections(cand, hasU, yMaxU, 1, hasD, yMaxD, -1);
        addIntersections(cand, hasU, yMaxU, 1, hasRL, yMaxRL, 0);
        addIntersections(cand, hasD, yMaxD, -1, hasRL, yMaxRL, 0);

        // y_min
        addIntersections(cand, hasU, yMinU, 1, hasD, yMinD, -1);
        addIntersections(cand, hasU, yMinU, 1, hasRL, yMinRL, 0);
        addIntersections(cand, hasD, yMinD, -1, hasRL, yMinRL, 0);

        double ans = Double.MAX_VALUE;
        for (double t : cand) {
            if (t < 0) continue;
            ans = Math.min(ans, area(t,
                hasR, xMaxR, xMinR,
                hasL, xMaxL, xMinL,
                hasUD, xMaxUD, xMinUD,
                hasU, yMaxU, yMinU,
                hasD, yMaxD, yMinD,
                hasRL, yMaxRL, yMinRL));
        }

        System.out.printf("%.10f\n", ans);
    }

    static void addIntersections(List<Double> cand,
            boolean ha, long a, int va,
            boolean hb, long b, int vb) {
        if (!ha || !hb) return;
        if (va == vb) return; // 平行
        // a + va*t = b + vb*t  =>  t = (b - a) / (va - vb)
        double t = (double)(b - a) / (va - vb);
        if (t >= 0) cand.add(t);
    }

    static double area(double t,
            boolean hasR, long xMaxR, long xMinR,
            boolean hasL, long xMaxL, long xMinL,
            boolean hasUD, long xMaxUD, long xMinUD,
            boolean hasU, long yMaxU, long yMinU,
            boolean hasD, long yMaxD, long yMinD,
            boolean hasRL, long yMaxRL, long yMinRL) {

        double xMax = -1e18, xMin = 1e18;
        double yMax = -1e18, yMin = 1e18;

        if (hasR) {
            xMax = Math.max(xMax, xMaxR + t);
            xMin = Math.min(xMin, xMinR + t);
        }
        if (hasL) {
            xMax = Math.max(xMax, xMaxL - t);
            xMin = Math.min(xMin, xMinL - t);
        }
        if (hasUD) {
            xMax = Math.max(xMax, xMaxUD);
            xMin = Math.min(xMin, xMinUD);
        }
        if (hasU) {
            yMax = Math.max(yMax, yMaxU + t);
            yMin = Math.min(yMin, yMinU + t);
        }
        if (hasD) {
            yMax = Math.max(yMax, yMaxD - t);
            yMin = Math.min(yMin, yMinD - t);
        }
        if (hasRL) {
            yMax = Math.max(yMax, yMaxRL);
            yMin = Math.min(yMin, yMinRL);
        }

        return (xMax - xMin) * (yMax - yMin);
    }
}

C++ ¶

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

void add_intersections(vector<double>& cand,
        bool ha, ll a, int va,
        bool hb, ll b, int vb) {
    if (!ha || !hb) return;
    if (va == vb) return;
    double t = double(b - a) / (va - vb);
    if (t >= 0) cand.push_back(t);
}

double area(double t,
        bool hasR, ll xMaxR, ll xMinR,
        bool hasL, ll xMaxL, ll xMinL,
        bool hasUD, ll xMaxUD, ll xMinUD,
        bool hasU, ll yMaxU, ll yMinU,
        bool hasD, ll yMaxD, ll yMinD,
        bool hasRL, ll yMaxRL, ll yMinRL) {

    double xMax = -1e18, xMin = 1e18;
    double yMax = -1e18, yMin = 1e18;

    if (hasR) {
        xMax = max(xMax, (double)xMaxR + t);
        xMin = min(xMin, (double)xMinR + t);
    }
    if (hasL) {
        xMax = max(xMax, (double)xMaxL - t);
        xMin = min(xMin, (double)xMinL - t);
    }
    if (hasUD) {
        xMax = max(xMax, (double)xMaxUD);
        xMin = min(xMin, (double)xMinUD);
    }
    if (hasU) {
        yMax = max(yMax, (double)yMaxU + t);
        yMin = min(yMin, (double)yMinU + t);
    }
    if (hasD) {
        yMax = max(yMax, (double)yMaxD - t);
        yMin = min(yMin, (double)yMinD - t);
    }
    if (hasRL) {
        yMax = max(yMax, (double)yMaxRL);
        yMin = min(yMin, (double)yMinRL);
    }

    return (xMax - xMin) * (yMax - yMin);
}

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

    int N;
    cin >> N;

    ll xMaxR = LLONG_MIN, xMaxL = LLONG_MIN, xMaxUD = LLONG_MIN;
    ll xMinR = LLONG_MAX, xMinL = LLONG_MAX, xMinUD = LLONG_MAX;
    ll yMaxU = LLONG_MIN, yMaxD = LLONG_MIN, yMaxRL = LLONG_MIN;
    ll yMinU = LLONG_MAX, yMinD = LLONG_MAX, yMinRL = LLONG_MAX;

    bool hasR = false, hasL = false, hasU = false, hasD = false;
    bool hasUD = false, hasRL = false;

    for (int i = 0; i < N; i++) {
        ll x, y;
        char d;
        cin >> x >> y >> d;

        if (d == 'R') {
            hasR = true;
            xMaxR = max(xMaxR, x); xMinR = min(xMinR, x);
            hasRL = true;
            yMaxRL = max(yMaxRL, y); yMinRL = min(yMinRL, y);
        } else if (d == 'L') {
            hasL = true;
            xMaxL = max(xMaxL, x); xMinL = min(xMinL, x);
            hasRL = true;
            yMaxRL = max(yMaxRL, y); yMinRL = min(yMinRL, y);
        } else if (d == 'U') {
            hasU = true;
            yMaxU = max(yMaxU, y); yMinU = min(yMinU, y);
            hasUD = true;
            xMaxUD = max(xMaxUD, x); xMinUD = min(xMinUD, x);
        } else { // 'D'
            hasD = true;
            yMaxD = max(yMaxD, y); yMinD = min(yMinD, y);
            hasUD = true;
            xMaxUD = max(xMaxUD, x); xMinUD = min(xMinUD, x);
        }
    }

    vector<double> cand;
    cand.push_back(0.0);

    // x_max
    add_intersections(cand, hasR, xMaxR, 1, hasL, xMaxL, -1);
    add_intersections(cand, hasR, xMaxR, 1, hasUD, xMaxUD, 0);
    add_intersections(cand, hasL, xMaxL, -1, hasUD, xMaxUD, 0);
    // x_min
    add_intersections(cand, hasR, xMinR, 1, hasL, xMinL, -1);
    add_intersections(cand, hasR, xMinR, 1, hasUD, xMinUD, 0);
    add_intersections(cand, hasL, xMinL, -1, hasUD, xMinUD, 0);
    // y_max
    add_intersections(cand, hasU, yMaxU, 1, hasD, yMaxD, -1);
    add_intersections(cand, hasU, yMaxU, 1, hasRL, yMaxRL, 0);
    add_intersections(cand, hasD, yMaxD, -1, hasRL, yMaxRL, 0);
    // y_min
    add_intersections(cand, hasU, yMinU, 1, hasD, yMinD, -1);
    add_intersections(cand, hasU, yMinU, 1, hasRL, yMinRL, 0);
    add_intersections(cand, hasD, yMinD, -1, hasRL, yMinRL, 0);

    double ans = 1e30;
    for (double t : cand) {
        if (t < 0) continue;
        ans = min(ans, area(t,
            hasR, xMaxR, xMinR,
            hasL, xMaxL, xMinL,
            hasUD, xMaxUD, xMinUD,
            hasU, yMaxU, yMinU,
            hasD, yMaxD, yMinD,
            hasRL, yMaxRL, yMinRL));
    }

    printf("%.10f\n", ans);
    return 0;
}

Python ¶

import sys


def add_intersections(cand, ha, a, va, hb, b, vb):
    """两条直线 a + va*t 与 b + vb*t 的交点时刻 t = (b-a)/(va-vb)"""
    if not ha or not hb:
        return
    if va == vb:      # 平行，无交点
        return
    t = (b - a) / (va - vb)
    if t >= 0:
        cand.append(t)


def area(t, hasR, xMaxR, xMinR, hasL, xMaxL, xMinL, hasUD, xMaxUD, xMinUD,
         hasU, yMaxU, yMinU, hasD, yMaxD, yMinD, hasRL, yMaxRL, yMinRL):
    x_max = x_min = y_max = y_min = None
    x_max = -1e18
    x_min = 1e18
    y_max = -1e18
    y_min = 1e18
    if hasR:
        x_max = max(x_max, xMaxR + t)
        x_min = min(x_min, xMinR + t)
    if hasL:
        x_max = max(x_max, xMaxL - t)
        x_min = min(x_min, xMinL - t)
    if hasUD:
        x_max = max(x_max, xMaxUD)
        x_min = min(x_min, xMinUD)
    if hasU:
        y_max = max(y_max, yMaxU + t)
        y_min = min(y_min, yMinU + t)
    if hasD:
        y_max = max(y_max, yMaxD - t)
        y_min = min(y_min, yMinD - t)
    if hasRL:
        y_max = max(y_max, yMaxRL)
        y_min = min(y_min, yMinRL)
    return (x_max - x_min) * (y_max - y_min)


def main():
    input = sys.stdin.readline
    n = int(input())

    NEG = -10**30
    POS = 10**30
    xMaxR = xMaxL = xMaxUD = NEG
    xMinR = xMinL = xMinUD = POS
    yMaxU = yMaxD = yMaxRL = NEG
    yMinU = yMinD = yMinRL = POS
    hasR = hasL = hasU = hasD = hasUD = hasRL = False

    for _ in range(n):
        x, y, d = input().split()
        x = int(x)
        y = int(y)
        if d == 'R':
            hasR = True
            xMaxR = max(xMaxR, x); xMinR = min(xMinR, x)
            hasRL = True
            yMaxRL = max(yMaxRL, y); yMinRL = min(yMinRL, y)
        elif d == 'L':
            hasL = True
            xMaxL = max(xMaxL, x); xMinL = min(xMinL, x)
            hasRL = True
            yMaxRL = max(yMaxRL, y); yMinRL = min(yMinRL, y)
        elif d == 'U':
            hasU = True
            yMaxU = max(yMaxU, y); yMinU = min(yMinU, y)
            hasUD = True
            xMaxUD = max(xMaxUD, x); xMinUD = min(xMinUD, x)
        else:  # 'D'
            hasD = True
            yMaxD = max(yMaxD, y); yMinD = min(yMinD, y)
            hasUD = True
            xMaxUD = max(xMaxUD, x); xMinUD = min(xMinUD, x)

    cand = [0.0]
    # x_max / x_min：R(+t)、L(-t)、UD(常量) 两两求交点
    add_intersections(cand, hasR, xMaxR, 1, hasL, xMaxL, -1)
    add_intersections(cand, hasR, xMaxR, 1, hasUD, xMaxUD, 0)
    add_intersections(cand, hasL, xMaxL, -1, hasUD, xMaxUD, 0)
    add_intersections(cand, hasR, xMinR, 1, hasL, xMinL, -1)
    add_intersections(cand, hasR, xMinR, 1, hasUD, xMinUD, 0)
    add_intersections(cand, hasL, xMinL, -1, hasUD, xMinUD, 0)
    # y_max / y_min：U(+t)、D(-t)、RL(常量)
    add_intersections(cand, hasU, yMaxU, 1, hasD, yMaxD, -1)
    add_intersections(cand, hasU, yMaxU, 1, hasRL, yMaxRL, 0)
    add_intersections(cand, hasD, yMaxD, -1, hasRL, yMaxRL, 0)
    add_intersections(cand, hasU, yMinU, 1, hasD, yMinD, -1)
    add_intersections(cand, hasU, yMinU, 1, hasRL, yMinRL, 0)
    add_intersections(cand, hasD, yMinD, -1, hasRL, yMinRL, 0)

    ans = 1e30
    for t in cand:
        if t < 0:
            continue
        ans = min(ans, area(t,
                            hasR, xMaxR, xMinR,
                            hasL, xMaxL, xMinL,
                            hasUD, xMaxUD, xMinUD,
                            hasU, yMaxU, yMinU,
                            hasD, yMaxD, yMinD,
                            hasRL, yMaxRL, yMinRL))
    print(f"{ans:.10f}")


if __name__ == "__main__":
    main()

G题 · 数学嘉豪 ¶

项目	内容
来源	附加题 — 数学嘉豪
难度	普及–
标签	数学、周期规律、快速幂取模

题目大意 ¶

给定两个正整数 $a$ 和 $b$，求 $a^b$ 的个位数。

约束 ¶

$1 \le a \le 114514$
$1 \le b \le 1919810$

思路 ¶

核心观察 ¶

个位数只和 $a$ 的个位数有关。设 $d = a \bmod 10$，问题转化为求 $d^b \bmod 10$。

个位数的循环规律 ¶

观察 $0 \sim 9$ 的幂次个位数：

$d$	幂次序列（个位）	周期
0	0, 0, 0, 0, …	1
1	1, 1, 1, 1, …	1
2	2, 4, 8, 6, 2, …	4
3	3, 9, 7, 1, 3, …	4
4	4, 6, 4, 6, …	2
5	5, 5, 5, 5, …	1
6	6, 6, 6, 6, …	1
7	7, 9, 3, 1, 7, …	4
8	8, 4, 2, 6, 8, …	4
9	9, 1, 9, 1, …	2

算法 ¶

取 $d = a \bmod 10$
若 $d \in {0, 1, 5, 6}$：答案为 $d$（周期为 1）
若 $d \in {4, 9}$（周期为 2）：计算 $b \bmod 2$，查表
若 $d \in {2, 3, 7, 8}$（周期为 4）：计算 $b \bmod 4$，查表

注意：当 $b \bmod 4 = 0$ 时，实际对应周期中的第 4 个位置（即 $b \bmod 4 = 0 \rightarrow$ 取 $d^4 \bmod 10$）

另一种通用方法：快速幂 ¶

由于 $b \le 1919810$（约 $2 \times 10^6$），直接做快速幂取模 10 也完全可行，代码更简洁：

快速幂：每次将指数折半，底数平方取模 10
时间复杂度 $O(\log b) \approx 21$ 次迭代

示例代码 ¶

Java（查表法） ¶

import java.util.Scanner;

public class Main {
    // 周期表：cycle[d][i] = d^(i+1) 的个位数
    static int[][] cycle = {
        {0},          // 0
        {1},          // 1
        {2, 4, 8, 6}, // 2
        {3, 9, 7, 1}, // 3
        {4, 6},       // 4
        {5},          // 5
        {6},          // 6
        {7, 9, 3, 1}, // 7
        {8, 4, 2, 6}, // 8
        {9, 1}        // 9
    };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int d = a % 10;
        int len = cycle[d].length;
        // b-1 是因为 cycle[d][0] 对应 d^1
        int idx = (b - 1) % len;
        System.out.println(cycle[d][idx]);
    }
}

Java（快速幂法） ¶

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int base = a % 10;
        int result = 1;
        int exp = b;
        while (exp > 0) {
            if ((exp & 1) == 1) result = (result * base) % 10;
            base = (base * base) % 10;
            exp >>= 1;
        }
        System.out.println(result);
    }
}

C++（查表法） ¶

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

// cycle[d] 存储 d 的幂次个位数循环
vector<vector<int>> cycle = {
    {0},          // 0
    {1},          // 1
    {2, 4, 8, 6}, // 2
    {3, 9, 7, 1}, // 3
    {4, 6},       // 4
    {5},          // 5
    {6},          // 6
    {7, 9, 3, 1}, // 7
    {8, 4, 2, 6}, // 8
    {9, 1}        // 9
};

int main() {
    int a, b;
    cin >> a >> b;
    int d = a % 10;
    int len = cycle[d].size();
    // b-1 是因为 cycle[d][0] 对应 d^1
    int idx = (b - 1) % len;
    cout << cycle[d][idx] << endl;
    return 0;
}

Python（查表法） ¶

a, b = map(int, input().split())

# cycle[d] 存储 d 的幂次个位数循环
cycle = [
    [0],          # 0
    [1],          # 1
    [2, 4, 8, 6], # 2
    [3, 9, 7, 1], # 3
    [4, 6],       # 4
    [5],          # 5
    [6],          # 6
    [7, 9, 3, 1], # 7
    [8, 4, 2, 6], # 8
    [9, 1]        # 9
]

d = a % 10
# b-1 是因为 cycle[d][0] 对应 d^1
idx = (b - 1) % len(cycle[d])
print(cycle[d][idx])

C++（快速幂法） ¶

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int base = a % 10, result = 1, exp = b;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % 10;
        base = (base * base) % 10;
        exp >>= 1;
    }
    cout << result << endl;
    return 0;
}

Python（快速幂法） ¶

a, b = map(int, input().split())
base, result, exp = a % 10, 1, b

while exp > 0:
    if exp & 1:
        result = (result * base) % 10
    base = (base * base) % 10
    exp >>= 1

print(result)

总结 ¶

题目	分数	核心知识点	难度
A - 五百元硬币	100	条件判断	★☆☆☆☆
B - 自助取餐	200	数组遍历、模拟	★☆☆☆☆
C - 计票	300	哈希表统计、排序	★★☆☆☆
D - 数字列队	400	DP、模运算、滚动数组	★★★☆☆
E - 自助餐	500	0/1 背包变形、枚举最后一项	★★★★☆
F - 最小包围盒	600	分段线性函数、极值枚举	★★★★★
G - 数学嘉豪	彩蛋	周期规律 / 快速幂取模	★★☆☆☆

这套题单覆盖了从基础语法到高级算法的完整路径，适合循序渐进地练习。关键收获：

A~C 是基础题，考察输入输出、循环、哈希表等基本功
D 引入了 DP 和模运算的组合，是 AtCoder 中非常典型的 DP 模式
E 是经典 0/1 背包的巧妙变体——关键在于理解”最后一道菜可以超时”
F 需要将几何问题转化为代数问题，利用分段线性的性质枚举候选解
G 是个位数周期的经典应用，是快速幂取模的入门好题

ABC 98th 题单 · 详细题解 ¶

目录 ¶

A题 · 五百元硬币 (ABC 150 A) ¶

题目大意 ¶

约束 ¶

思路 ¶

示例代码 ¶

Java ¶

C++ ¶

Python ¶

B题 · 自助取餐 (ABC 140 B) ¶

题目大意 ¶

约束 ¶

思路 ¶

示例代码 ¶

Java ¶

C++ ¶

Python ¶

C题 · 计票 (ABC 155 C) ¶

题目大意 ¶

约束 ¶

思路 ¶

为什么不能只维护最大值？ ¶

示例代码 ¶

Java ¶

C++ ¶

Python ¶

D题 · 数字列队 (ABC 135 D) ¶

题目大意 ¶

约束 ¶

思路 ¶

状态定义 ¶

状态转移 ¶

初始化 ¶

答案 ¶

复杂度 ¶

空间优化 ¶

示例代码 ¶

Java ¶

C++ ¶

Python ¶

E题 · 自助餐 (ABC 145 E) ¶

题目大意 ¶

约束 ¶

思路 ¶

关键转化 ¶

算法 ¶

示例代码 ¶

Java ¶

C++ ¶

Python ¶

F题 · 最小包围盒 (ABC 130 F) ¶

题目大意 ¶

约束 ¶

思路 ¶

第一步：写出极值函数 ¶

第二步：候选时刻 ¶

第三步：实现 ¶

示例代码 ¶

Java ¶

C++ ¶

Python ¶

G题 · 数学嘉豪 ¶

题目大意 ¶

约束 ¶

思路 ¶

核心观察 ¶

个位数的循环规律 ¶

算法 ¶

另一种通用方法：快速幂 ¶

示例代码 ¶

Java（查表法） ¶

Java（快速幂法） ¶

C++（查表法） ¶

Python（查表法） ¶

C++（快速幂法） ¶

Python（快速幂法） ¶

总结 ¶

💬 评论 (0)