ABC462#

CodeQUEEN 2026 -qual- (AtCoder Beginner Contest 462) - AtCoder

更好的阅读体验

C-排序#

题意：

给定二维平面上N个点，求满足以下条件点的个数：

以平行于xy轴的矩形，其左下顶点为(0,0)，右上为(x,y)，该矩形内不包含编号1到N的任意一点

题解：

按照x,y坐标形式升序，枚举每个点并维护当前点的最小y值，若

一个点合法当且仅当其左侧不存在纵坐标更小的点，即 pi是前缀最小值，

1
n = int(input())
2
a = []
3
for i in range(n):
4
    x, y = map(int, input().split())
5
    a.append((x, y))
6
a.sort()
7
ans = 0
8
min_y = n + 1
9
for x, y in a:
10
    if y < min_y:
11
        ans += 1
12
        min_y = y
13
print(ans)

D-差分#

题目重述

有 N 个嫌疑人，第 i 个人在时间 S_i 进入别墅，在时间 T_i 离开别墅，期间始终待在别墅中，因此其在别墅中的时间区间为：

[S_i,T_i]

已知：

恰好有两名凶手；
犯罪从整数时刻 x 开始；
持续 D 个时间单位；
在整个犯罪过程

[x,x+D]

内，两名凶手必须始终在别墅中。

要求统计所有合法的：

(\text{凶手A},\text{凶手B},x)

方案数。

其中两名凶手无序，不同开始时间视为不同方案。

思路分析

对于某个人来说，如果犯罪开始于时间 x，则必须满足：

S_i \le x

并且

x+D \le T_i

整理得：

S_i \le x \le T_i-D

因此此人能够参与犯罪的所有开始时间构成区间：

[S_i,T_i-D]

若：

T_i-S_i<D

则该区间为空，此人不可能参与犯罪。

设：

c_x

表示能够在时间 x 作为凶手的人数。

即满足：

S_i\le x\le T_i-D

的人数。

那么当开始时间固定为 x 时，可以从这 c_x 个人中任选两人：

\binom{c_x}{2}

种选择。

因此答案为：

\sum_x \binom{c_x}{2}

差分统计覆盖次数

每个人贡献一个可行开始时间区间：

[S_i,T_i-D]

问题变成：

求每个时间点被多少个区间覆盖。

这是经典差分问题。

对于区间：

[L,R]

执行：

1
d[L] += 1
2
d[R + 1] -= 1

这里：

1
L = S_i
2
R = T_i - D

因此：

1
d[S_i] += 1
2
d[T_i - D + 1] -= 1

随后求前缀和即可得到：

1
c += d[t]

其中 c 即当前时间点的覆盖人数。

统计答案

对于每个时间点：

1
ans += c * (c - 1) // 2

因为：

=\frac{c(c-1)}2

表示当前时间作为犯罪开始时间时，两名凶手的选择方案数。

把所有时间点贡献累加即可。

正确性证明

对于某个时间 x：

能够参与犯罪的人恰好满足：

S_i \le x \le T_i-D

因此覆盖时间点 x 的区间数量正好等于：

c_x

在这些人中任选两人即可组成凶手组合，共有：

\binom{c_x}{2}

种方案。

不同时间的方案互不重叠，因此总方案数为：

\sum_x \binom{c_x}{2}

算法统计的正是该式，因此正确。

复杂度分析

时间范围最大为：

10^6

差分扫描一次即可。

时间复杂度：

O(N+10^6)

空间复杂度：

O(10^6)

满足题目要求。

将每个人能参与犯罪的开始时间转化为区间 [S_i,T_i-D]，利用差分统计每个时间点可作案人数 c，答案即所有时间点的

\binom{c}{2}

之和。

1
N, D = map(int, input().split())
2
M = 10**6 + 1
3
d = [0] * M
4
for i in range(N):
5
    S, T = map(int, input().split())
6
    if T - S >= D:
7
        d[S] += 1
8
        d[T - D + 1] -= 1
9

10
c, ans = 0, 0
11
for i in range(M):
12
    c += d[i]
13
    ans += c * (c - 1) // 2
14
print(ans)

E-数学#

题目重述

平面上有一个棋子，初始位于：

(0,0)

每次操作可以向上下左右移动一格。

设当前是第 $k$ 次移动：

若 $k$ $k$ 为奇数：
- 水平移动费用为 $A$
- 垂直移动费用为 $B$
若 $k$ $k$ 为偶数：
- 水平移动费用为 $B$
- 垂直移动费用为 $A$

要求将棋子移动到：

(X,Y)

求最小总代价。

共有 $T$ 组数据。

性质观察

首先发现方向不重要。

因为：

向左和向右费用相同；
向上和向下费用相同。

因此只关心需要移动多少次横向和纵向。

设：

x=|X|,\qquad y=|Y|

那么：

横向必须移动 $x$ 次；
纵向必须移动 $y$ 次；

总步数：

n=x+y

奇偶步费用规律

观察连续两步：

第一步（奇数步）
第二步（偶数步）

若两步都走水平：

A+B

若两步都走竖直：

A+B

若一横一竖：

A+A=2A

或者

B+B=2B

因此每两步形成一个配对时：

同方向代价固定为 $A+B$
不同方向代价可能是 $2A$ 或 $2B$

于是问题本质变成：

如何安排横步和竖步在奇偶位置上的分布。

不妨设 A ≤ B

首先执行：

1
if a > b:
2
    a, b = b, a

因此后面始终满足：

A\le B

此时：

2A \le A+B

说明：

一横一竖组成一对永远不劣于两步同方向。

因此应尽量让奇偶步分别承担不同方向。

偶数总步数情况

先讨论：

x+y

为偶数。

设：

x\le y

（代码中交换保证）

1
if x > y:
2
    x, y = y, x

方案一：全部采用交替

若能做到每对都是：

(H,V)

则每对费用：

2A

总共有：

y

对。

总代价：

2Ay

对应代码：

1
2 * a * y

方案二：先尽量配对

横向共有 $x$ 步。

把这 $x$ 步全部与竖向配对：

x \text{ 对}

费用：

2Ax

剩余：

y-x

个竖向步。

由于总步数为偶数，

y-x

也是偶数。

这些剩余竖步只能两两组成同方向对。

每对费用：

A+B

共有：

\frac{y-x}{2}

对。

总代价：

化简：

对应代码：

1
a * (x + y)
2
+ (b - a) * (y - x) // 2

因此偶数情况答案为：

\operatorname* {m i n} \left(2 A y , A(x + y) + \frac{(B - A) (y - x)}{2} \right)

奇数总步数情况

若：

x+y

为奇数。

最终一定会剩下一步无法配对。

最后一步只能是：

横向一步
或纵向一步

分别产生代价：

A

或

B

于是枚举最后一步：

最后一步为横向

先完成：

(x-1,y)

此时总步数变为偶数。

费用：

1
solve(x-1,y)+A

最后一步为纵向

先完成：

(x,y-1)

费用：

1
solve(x,y-1)+B

取最小值：

1
min(
2
    solve(x-1,y)+A,
3
    solve(x,y-1)+B
4
)

算法流程

对于每组数据：

取绝对值

1
x = abs(X)
2
y = abs(Y)

若总步数为偶数

直接调用：

1
solve(a,b,x,y)

若总步数为奇数

枚举最后一步：

1
min(
2
    solve(a,b,x-1,y)+a,
3
    solve(a,b,x,y-1)+b
4
)

正确性证明

设需要横向移动 $x$ 次，纵向移动 $y$ 次。

由于费用只与：

当前步数奇偶
移动方向

有关，而与具体坐标无关，因此问题只取决于横步和竖步的排列顺序。

当 $A\le B$ 时，

2A\le A+B

说明让一横一竖占据一组奇偶位置一定不劣于同方向配对。

因此最优策略一定是：

尽可能进行横竖配对；
无法配对的部分再使用同方向配对；

从而得到偶数情况的公式。

奇数情况必然存在一个未配对的最后一步，枚举其方向即可覆盖全部最优方案。

故算法正确。

复杂度分析

每组数据仅进行常数次运算：

O(1)

总复杂度：

O(T)

其中：

T\le 2\times10^5

可以轻松通过。

把移动次数转化为横步数和竖步数，利用「奇偶两步构成一组」的性质分析配对代价；当 $A\le B$ 时优先进行横竖配对，得到偶数步公式，奇数步再枚举最后一步方向即可在 $O(1)$ 时间求解。

1
input = __import__("sys").stdin.readline
2
def solve(a, b, x, y):
3
    assert (x + y) % 2 == 0
4
    if a > b:
5
        a, b = b, a
6
    if x > y:
7
        x, y = y, x
8
    return min(2 * a * y, a * (x + y) + (b - a) * (y - x) // 2)
9
for _ in range(int(input())):
10
    a, b, x, y = map(int, input().split())
11
    x, y = abs(x), abs(y)
12
    if (x + y) % 2 == 1:
13
        print(min(solve(a, b, x - 1, y) + a, solve(a, b, x, y - 1) + b))
14
    else:
15
        print(solve(a, b, x, y))

F-带权区间选择 DP#

题目重述

给定一个仅由大写字母组成的字符串 S。

记字符串中 "ABC" 作为连续子串出现的次数为：

cnt(S)

现在允许修改字符串中的若干字符。

目标是使修改后的字符串满足：

cnt(S') = cnt(S) + K

即 "ABC" 的出现次数恰好增加 K 次。

要求：

判断是否存在这样的修改方案；
如果存在，求最少需要修改多少个字符；
否则输出 -1。

题解思路

一次新增的 "ABC" 必然对应一个长度为 3 的区间：

1
ABC

设其结尾位置为 i，对应区间：

[i-2,i]

对于每个长度为 3 的区间，可以计算：

y_i

表示把该区间修改成 "ABC" 所需的最少修改次数。

例如：

1
ABC -> 0
2
AAC -> 1
3
BBB -> 2
4
CCC -> 3

代码中的计算：

1
if(s[i-3]!='A') y[i]++;
2
if(s[i-2]!='B') y[i]++;
3
if(s[i-1]!='C') y[i]++;

正是在求这个值。

原有 ABC 的处理

定义：

z_i = \begin{cases} 1 & \text{区间} [i-2, i] \text{本来就是 ABC} \\ 0 & \text{否则} \end{cases}

即：

1
if(y[i]==0) z[i]++;

假设我们选择某个区间作为新增的 "ABC"。

那么最终该区间一定会变成 "ABC"。

此时会产生两个影响：

新增一个 "ABC"；
可能覆盖原来已经存在的 "ABC"。

x 数组的含义

注意两个 "ABC" 只有距离小于 3 时才会重叠。

因此对于一个原有 "ABC"：

1
ABC

它只会影响：

1
位置 i
2
位置 i+1
3
位置 i+2

对应代码：

1
for(int j=0;j<3;j++){
2
    if(i+j<=n)x[i+j]+=z[i];
3
}

因此：

x_i

表示：

若把区间 $i$ 变成新的 "ABC"，会覆盖掉多少个原本存在的 "ABC"。

DP 状态设计

定义：

dp[i][j]

表示：

处理前 $i$ 个字符后，
最终需要净增加 $j$ 个 "ABC"，
所需的最小修改次数。

状态转移

不选择位置 i 作为新的 ABC

直接跳过当前位置：

1
dp[i][j]=dp[i-1][j+z[i]]

原因：

若当前位置原本已经有一个 "ABC"，

z[i]=1

那么不保留它，相当于净增量减少 1。

对应代码：

1
if(j+z[i]<=k)
2
    dp[i][j]=min(dp[i][j],dp[i-1][j+z[i]]);

选择位置 i 作为新的 ABC

则必须占据区间：

[i-2,i]

为了避免重叠，

前一个选择只能结束在：

i-3

之前。

因此转移来自：

1
dp[i-3][...]

新增一个 "ABC" 后：

贡献：

+1

但会覆盖：

x[i]

个原有 "ABC"。

因此净贡献：

1-x[i]

故状态转移：

= dp[i-3][j-1+x[i]]

对应代码：

1
dp[i][j]=
2
min(
3
    dp[i][j],
4
    dp[i-3][j-1+x[i]]+y[i]
5
);

初始化

1
dp[0][0]=0

其余：

1
INF

表示不可达。

最终答案

要求净增加：

K

个 "ABC"。

因此答案为：

1
dp[n][K]

若不可达：

1
-1

正确性理解

由于两个 "ABC" 长度均为 3，

最终字符串中的新增 "ABC" 一定可以看成若干个互不重叠的长度 3 区间。

每个区间：

花费 y[i] 修改成 "ABC"；
产生一个新的 "ABC"；
可能覆盖 x[i] 个原有 "ABC"。

因此每个区间对答案的贡献为：

1-x[i]

问题转化成：

在所有长度 3 的区间中选择若干互不重叠区间，
使净增量恰好为 $K$ ，
修改代价最小。

这正是上述 DP 所求。

复杂度分析

设：

n=|S|

状态数：

O(nK)

其中：

K\le 10

因此：

O(nK)=O(10n)

总长度：

\sum n\le 3\times 10^5

总复杂度：

O\!\left(\sum n \cdot K\right)

约为：

3\times10^6

可以轻松通过。

先预处理每个长度为 3 的区间变成 "ABC" 的代价以及其会覆盖多少原有 "ABC"，然后把问题转化为「选择若干互不重叠区间，使净增加的 "ABC" 数量恰好为 $K$ 且总代价最小」的区间 DP。

1
import sys
2

3
input = sys.stdin.readline
4
INF = 10**18
5

6
T = int(input())
7

8
for _ in range(T):
9
    s = input().strip()
10
    k = int(input())
11
    n = len(s)
12

13
    x = [0] * (n + 1)
14
    y = [0] * (n + 1)
15
    z = [0] * (n + 1)
16

17
    for i in range(3, n + 1):
18
        if s[i - 3] != 'A':
19
            y[i] += 1
20
        if s[i - 2] != 'B':
21
            y[i] += 1
22
        if s[i - 1] != 'C':
23
            y[i] += 1
24

25
        if y[i] == 0:
26
            z[i] = 1
27

28
        for j in range(3):
29
            if i + j <= n:
30
                x[i + j] += z[i]
31

32
    dp = [[INF] * (k + 1) for _ in range(n + 1)]
33
    dp[0][0] = 0
34

35
    for i in range(1, n + 1):
36
        dp[i][0] = 0
37

38
        for j in range(1, k + 1):
39
            # 不选择以 i 结尾的 ABC
40
            if j + z[i] <= k:
41
                dp[i][j] = min(dp[i][j], dp[i - 1][j + z[i]])
42

43
            # 选择区间 [i-2, i]
44
            if i >= 3:
45
                prev = j - 1 + x[i]
46
                if 0 <= prev <= k:
47
                    dp[i][j] = min(
48
                        dp[i][j],
49
                        dp[i - 3][prev] + y[i]
50
                    )
51

52
    ans = dp[n][k]
53
    print(-1 if ans >= INF else ans)

音乐

音乐

ABC462#

C-排序#

D-差分#

E-数学#

F-带权区间选择 DP#

音乐

目录

音乐

音乐

ABC462-①排序②差分③数学④带权区间选择 DP

ABC462#

C-排序#

D-差分#

E-数学#

F-带权区间选择 DP#

音乐

目录