完整视频讲解
🎬 前往 Bilibili 观看《AtCoder ABC468 A–G 完整题解》
题目总览
| 题目 | 分值 | 核心方法 | 复杂度 |
|---|---|---|---|
| A. Maximal Value | 100 | 一次扫描连续三元组 | O(N) |
| B. Corridor Watch | 200 | 区间差分 | O(M) |
| C. Between P and Q | 300 | 康托展开 | O(N²) |
| D. Pre-Palindrome | 400 | 奇偶中心扩展 | O(N²) |
| E. Sum of Average | 450 | 调和数与模逆元 | O(N) |
| F. Chmax | 500 | 前缀纪录 + LIS | O(N log N) |
| G. Restricted Permutation | 550 | 块计数 DP | O(N²) |
A. Maximal Value｜统计局部峰值
题意
给定长度为 N 的整数序列 A，统计满足
A[i-1] < A[i] > A[i+1] 的中间位置数量。
核心思路
条件只依赖连续三个元素。枚举中间位置 i=1..N-2，同时比较左右邻居即可。相等不满足严格大于。
正确性证明
算法检查了所有且仅有可能成为三元组中心的位置。对每个位置，它使用的判断式与题目条件完全相同，因此每个合法位置恰好计数一次，非法位置不会计数。
复杂度
- 时间：
O(N) - 额外空间：
O(N)（保存输入；也可流式降为O(1)）
Java 17 标程
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = fs.nextInt();
int answer = 0;
for (int i = 1; i + 1 < n; i++) {
if (a[i - 1] < a[i] && a[i] > a[i + 1]) answer++;
}
System.out.println(answer);
}
private static final class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr, len;
FastScanner(InputStream in) { this.in = in; }
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, value = 0;
do c = read(); while (c <= 32);
while (c > 32) {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
}
易错点
- 下标两端不能作为中心；
- 两侧比较都是严格不等号；
- 输出的是位置个数，不是峰值之和。
B. Corridor Watch｜差分数组统计未监视格
题意
走廊有 M 个格子。每名警卫监视与其距离不超过 D 的格子，求没有被任何警卫监视的格子数。
核心思路
位于 i 的警卫覆盖闭区间：
[max(0, i-D), min(M-1, i+D)]
用差分数组对区间左端加一、右端后一位减一。扫描前缀和时，当前值为零的格子没有被任何区间覆盖。
正确性证明
每名警卫都向差分数组加入了恰好等于其监视范围的区间。差分数组的前缀和等于覆盖当前格子的警卫数量，因此前缀和为零当且仅当该格无人监视。统计这些位置即得到答案。
复杂度
- 时间：
O(M) - 空间：
O(M)
Java 17 标程
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int m = fs.nextInt();
int d = fs.nextInt();
String s = fs.next();
int[] difference = new int[m + 1];
for (int i = 0; i < m; i++) {
if (s.charAt(i) != 'G') continue;
int left = Math.max(0, i - d);
int right = Math.min(m - 1, i + d);
difference[left]++;
difference[right + 1]--;
}
int active = 0;
int answer = 0;
for (int i = 0; i < m; i++) {
active += difference[i];
if (active == 0) answer++;
}
System.out.println(answer);
}
private static final class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr, len;
FastScanner(InputStream in) { this.in = in; }
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
String next() throws IOException {
StringBuilder result = new StringBuilder();
int c;
do c = read(); while (c <= 32);
while (c > 32) {
result.append((char) c);
c = read();
}
return result.toString();
}
int nextInt() throws IOException { return Integer.parseInt(next()); }
}
}
易错点
- 覆盖区间必须截断到走廊边界；
right + 1需要差分数组长度为M + 1；- 没有警卫时所有格子都应计入答案。
C. Between P and Q｜排列排名与康托展开
题意
给定两个 1..N 的排列 P、Q，求严格大于 P 且严格小于 Q 的排列数量，N <= 10。
核心思路
计算排列的零基字典序排名。处理第 i 位时，若当前值之前还有 c 个更小且未使用的数，那么以这些数开头的排列共有：
c × (N-1-i)!
把每一位的贡献相加即可得到排名 rank(P)。严格位于两者之间的排列数量为：
max(0, rank(Q) - rank(P) - 1)
正确性证明
对第 i 位，所有与当前排列前 i 位相同、但第 i 位取更小未用值的排列都排在当前排列之前；每种选择的剩余元素有 (N-1-i)! 种排列。不同首个差异位置对应的排列集合互不相交，所以逐位求和恰好得到字典序排名。两个端点都不计入，故排名差再减一；若 P >= Q，区间为空。
复杂度
- 时间：
O(N^2) - 空间：
O(N)
Java 17 标程
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int[] p = new int[n];
int[] q = new int[n];
for (int i = 0; i < n; i++) p[i] = fs.nextInt();
for (int i = 0; i < n; i++) q[i] = fs.nextInt();
long rankP = rank(p);
long rankQ = rank(q);
System.out.println(Math.max(0L, rankQ - rankP - 1));
}
private static long rank(int[] permutation) {
int n = permutation.length;
long[] factorial = new long[n + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i;
boolean[] used = new boolean[n + 1];
long rank = 0;
for (int i = 0; i < n; i++) {
int smallerUnused = 0;
for (int value = 1; value < permutation[i]; value++) {
if (!used[value]) smallerUnused++;
}
rank += smallerUnused * factorial[n - 1 - i];
used[permutation[i]] = true;
}
return rank;
}
private static final class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr, len;
FastScanner(InputStream in) { this.in = in; }
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, value = 0;
do c = read(); while (c <= 32);
while (c > 32) {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
}
易错点
- 题目要求严格不等，必须减去两个端点之间的一格；
P可能不小于Q；- 排名和阶乘使用
long。
D. Pre-Palindrome｜中心扩展统计准回文
题意
一个字符串若修改至多一个字符就能变成回文，则称为好字符串。统计 S 的非空好子串数量，|S| <= 10^4。
核心观察
对称字符对中：
- 没有失配：本身就是回文；
- 恰好一对失配：修改其中任意一侧即可成为回文；
- 至少两对失配：一次修改不可能同时修好。
因此好字符串等价于“对称失配对数量至多一”。
算法
分别枚举奇数长度中心和偶数长度中心，并向两侧扩展。维护当前失配对数量：
- 失配数为
0或1，当前子串计入答案； - 出现第二对失配后立即停止，因为继续向外扩展不可能减少失配数。
正确性证明
每个非空子串有唯一的奇数或偶数中心，所以中心扩展会且只会访问它一次。访问时累计值正是该子串全部对称位置中的失配对数。算法计数当且仅当失配数不超过一，这与“至多修改一个字符可成为回文”等价，因此答案正确。
复杂度
- 时间：最坏
O(N^2) - 空间：
O(N)（字符数组）
Java 17 标程
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
char[] s = reader.readLine().trim().toCharArray();
int n = s.length;
long answer = 0;
for (int center = 0; center < n; center++) {
int mismatches = 0;
for (int left = center, right = center; left >= 0 && right < n; left--, right++) {
if (s[left] != s[right] && ++mismatches == 2) break;
answer++;
}
}
for (int rightCenter = 1; rightCenter < n; rightCenter++) {
int mismatches = 0;
for (int left = rightCenter - 1, right = rightCenter;
left >= 0 && right < n; left--, right++) {
if (s[left] != s[right] && ++mismatches == 2) break;
answer++;
}
}
System.out.println(answer);
}
}
易错点
- 奇数、偶数中心必须分别处理；
- 修改中心字符无法修复任何对称失配；
- 答案最大约为
N(N+1)/2，使用long。
E. Sum of Average｜调和数拆分子数组平均值
题意
求所有非空连续子数组的算术平均值之和，结果在模 998244353 意义下计算，N <= 5×10^5。
核心思路
交换求和顺序，统计每个 A[i] 对答案的系数。定义调和数：
H[k] = 1 + 1/2 + ... + 1/k, H[0] = 0
固定 A[i]，枚举包含它的左端点，可把右端点的倒数和写成调和数差。最终系数为：
w[i] = Σ(j=0..i) (H[N-j] - H[j])
所以可以从左到右维护：
w += H[N-i] - H[i]
answer += A[i] × w
模逆元用线性递推：
inv[i] = MOD - (MOD / i) × inv[MOD % i] mod MOD
正确性证明
任意子数组 [l,r] 对其中每个 A[i] 的贡献都是 A[i]/(r-l+1)。交换求和顺序后，A[i] 的系数是所有满足 l<=i<=r 的长度倒数之和。对固定 l，右端点从 i 到 N-1，其倒数和是对应调和数之差；再对 l 求和恰好得到上述 w[i]。因此每个三元组 (l,i,r) 的贡献被计入一次且仅一次。
复杂度
- 时间：
O(N) - 空间：
O(N)
Java 17 标程
import java.io.*;
public class Main {
private static final long MOD = 998_244_353L;
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = fs.nextInt();
long[] inverse = new long[n + 1];
long[] harmonic = new long[n + 1];
if (n >= 1) inverse[1] = 1;
for (int i = 1; i <= n; i++) {
if (i >= 2) {
inverse[i] = MOD - (MOD / i) * inverse[(int) (MOD % i)] % MOD;
}
harmonic[i] = (harmonic[i - 1] + inverse[i]) % MOD;
}
long coefficient = 0;
long answer = 0;
for (int i = 0; i < n; i++) {
coefficient += harmonic[n - i] - harmonic[i];
coefficient %= MOD;
if (coefficient < 0) coefficient += MOD;
answer = (answer + a[i] * coefficient) % MOD;
}
System.out.println(answer);
}
private static final class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr, len;
FastScanner(InputStream in) { this.in = in; }
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, value = 0;
do c = read(); while (c <= 32);
while (c > 32) {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
}
易错点
- 除法必须转为模逆元；
- 系数每轮可能为负，取模后要归一化；
- 乘法用
long。
F. Chmax｜前缀最大值与 LIS
题意
依次处理排列 P。每个数可更新 x 或 y 为二者与当前数的较大值；只有被更新变量原值更小时得一分。求最大总分。
核心结论
每个严格大于此前所有元素的前缀最大值一定能得分。删去这些元素，把其余元素按原顺序组成 Q，答案为：
前缀最大值个数 + LIS(Q)
推导
处理完任意前缀后，max(x,y) 必然等于该前缀最大值。新纪录出现时，把较大的变量更新到新纪录能稳定获得一分，并保留较小变量的自由度。
对非纪录元素，只有把它放入当前较小变量、且它比该变量更大时才能得分。所有通过这种方式得分的非纪录元素必须按处理顺序严格递增，因而形成 Q 的一个递增子序列；反过来，选择 Q 的任意递增子序列依次更新较小变量，都能让每个所选元素得分。
正确性证明
纪录元素部分：每个新纪录大于 x,y，必然可以得一分，且任何元素最多得一分，所以这部分贡献恰为纪录数。
非纪录元素部分：得分时它必须提升未保存全局最大值的另一个变量，因此连续得分值严格递增，数量不超过 LIS(Q)；取一条最长递增子序列并仅在这些位置更新较小变量可达到 LIS(Q)。两部分策略可以同时实现，故公式成立。
复杂度
- 时间：
O(N log N) - 空间：
O(N)
Java 17 标程
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int recordCount = 0;
int prefixMaximum = 0;
int[] lisTails = new int[n];
int lisLength = 0;
for (int i = 0; i < n; i++) {
int value = fs.nextInt();
if (value > prefixMaximum) {
prefixMaximum = value;
recordCount++;
continue;
}
int position = Arrays.binarySearch(lisTails, 0, lisLength, value);
if (position < 0) position = -position - 1;
lisTails[position] = value;
if (position == lisLength) lisLength++;
}
System.out.println(recordCount + lisLength);
}
private static final class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr, len;
FastScanner(InputStream in) { this.in = in; }
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, value = 0;
do c = read(); while (c <= 32);
while (c > 32) {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
}
易错点
Q要删掉所有严格前缀最大值；- 求的是严格递增 LIS，二分使用
lower_bound； - 新纪录不应放进 LIS。
G. Restricted Permutation｜小值块数量动态规划
题意
统计 1..N 的排列 P：对每个 k，S[k]='o' 当且仅当所有不超过 k 的数在 P 中占据一段连续区间。答案模 998244353，N <= 2000。
状态设计
把大于 i 的元素看作分隔符，1..i 在最终排列中的若干个极大连续段称为“块”。
dp[i][j] = 已加入 1..i、当前有 j 个块，
且 S[1..i] 的条件全部满足的排列构造数
所有 1..i 连续当且仅当块数为 1。因此：
S[i]='o'时只允许j=1；S[i]='x'时只允许j>=2。
转移
加入新最大值 i 后得到 j 个块：
- 单独插入成新块：从
j-1块来，有j个空隙； - 接到某块左端或右端：从
j块来，有2j种； - 放在相邻两块之间把它们连接：从
j+1块来，有j个间隙。
所以 S[i]='x' 且 j>=2 时：
next[j] = j × (dp[j-1] + 2dp[j] + dp[j+1])
S[i]='o' 时只保留：
next[1] = 2dp[1] + dp[2]
正确性证明
对任意最终排列，删除所有大于 i 的元素后，块划分唯一。加入 i 时，它与已有块的关系必然且只能属于上述三类；三类互斥，选择的位置也唯一确定，因此转移既不遗漏也不重复。每轮再按 S[i] 保留块数为一或至少二的状态，恰好落实当前条件。最终所有元素都已加入，整个排列必是一块，答案为 dp[N][1]。
复杂度
- 时间：
O(N^2) - 空间：
O(N)（滚动数组）
Java 17 标程
import java.io.*;
import java.util.*;
public class Main {
private static final long MOD = 998_244_353L;
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine().trim());
String s = reader.readLine().trim();
if (s.charAt(0) == 'x') {
System.out.println(0);
return;
}
long[] dp = new long[n + 2];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
long[] next = new long[n + 2];
if (s.charAt(i - 1) == 'o') {
next[1] = (2 * dp[1] + dp[2]) % MOD;
} else {
for (int blocks = 2; blocks <= i; blocks++) {
long ways = dp[blocks - 1];
ways = (ways + 2 * dp[blocks]) % MOD;
ways = (ways + dp[blocks + 1]) % MOD;
next[blocks] = blocks * ways % MOD;
}
}
dp = next;
}
System.out.println(dp[1]);
}
}
易错点
S[1]必须是o；S[i]='o'时要清空所有多块状态；- 三种转移的系数分别是
j、2j、j； - 最终读取的是一块状态。