ABC461-①贪心②前缀和+双指针③树状数组#

目录#

C-贪心
D-前缀和+双指针
E-树状数组

更好的阅读体验

C-贪心#

题意#

有 N 个宝石。

第 i 个宝石：

颜色为 Ci
价值为 Vi

需要恰好选择 K 个宝石，并且满足：

选出的宝石颜色种类数不少于 M

求能够获得的最大总价值。

数据范围：

1 ≤ M ≤ K ≤ N ≤ 2×10^5
1 ≤ Vi ≤ 10^9

思路分析#

将同一种颜色的宝石按照价值从大到小排序：

1
v1 ≥ v2 ≥ v3 ≥ ...

如果最终方案使用了这种颜色，那么一定可以选择：

1
v1

作为该颜色的代表宝石。

因为如果选择的是：

1
v2

那么直接换成：

1
v1

颜色数不会减少，而总价值一定不会变小。

因此：

每种颜色价值最大的宝石称为 颜色代表
其余宝石称为 普通宝石

题目要求：

1
至少 M 种颜色

因此必须先选择 M 个颜色代表。

设所有颜色代表的价值为：

1
a1,a2,a3,...

显然应该选择价值最大的 M 个颜色代表。

否则把较小的颜色代表替换成更大的颜色代表一定更优。

已经选了：

1
M 个颜色代表

还需要选择：

1
K-M 个宝石

此时颜色数要求已经满足。

因此剩余位置只需要尽量提高价值即可。

剩余可选宝石包括：

所有普通宝石
未被选作颜色代表的颜色代表

即：

1
tail += r[1:]
2
tail += top[M:]

然后从这些宝石中选出价值最大的：

1
K-M 个

即可。

正确性证明#

设某个颜色被选中。

若没有选择该颜色价值最大的宝石，而选择了价值较小的宝石：

1
v1 > vx

那么将其替换为：

1
v1

颜色种类数不会改变，而总价值增大。

因此最优解一定存在一种形式：

1
每个被使用的颜色都选择其最大价值宝石

为了满足至少 M 种颜色，显然应选择价值最大的 M 个颜色代表。

之后颜色要求已经满足。

剩余的 K-M 个位置不再影响颜色数，因此直接选择剩余宝石中价值最大的 K-M 个即可。

故该贪心策略正确。

算法步骤#

按颜色分组。
每组按价值降序排序。
取每组最大值放入 top。
其余宝石放入 tail。
将 top 降序排序。
选择最大的 M 个颜色代表。
将剩余颜色代表加入 tail。
从 tail 中选择最大的 K-M 个宝石。
输出总价值。

复杂度分析#

设宝石总数为 N。

排序总复杂度：

1
O(N \log N)

空间复杂度：

1
O(N)

能够通过：

1
N ≤ 2×10^5

1
n,k,m = map(int,input().split())
2
t = [[] for _ in range(n+1)]
3
for i in range(n):
4
    c,v = map(int,input().split())
5
    t[c].append(v)
6
top = []
7
tail = []
8
for r in t:
9
    if len(r) > 0:
10
        r.sort(reverse = True)
11
        top.append(r[0])
12
        tail += r[1:]
13
top.sort(reverse = True)
14
tail += top[m:]
15
tail.sort(reverse = True)
16
print(sum(top[:m]) + sum(tail[:k - m]))

D-前缀和+双指针#

题意#

给定一个 H × W 的 01 矩阵。

求有多少个矩形满足：

矩形边界与网格对齐；
矩形内部所有数字之和恰好等于 K。

即统计满足：

1\le r_1\le r_2\le H

1\le c_1\le c_2\le W

且

\sum_{i=r_1}^{r_2}\sum_{j=c_1}^{c_2}A_{i,j}=K

的矩形数量。

思路分析#

直接枚举矩形四条边：

1
上边界
2
下边界
3
左边界
4
右边界

复杂度：

O(H^2W^2)

当

H,W\le 500

时显然无法通过。

第一步：固定上下边界

先对每一列做纵向前缀和。

设：

1
a[i][j]

表示第 j 列前 i 行中 1 的个数。

则：

1
a[d][j] - a[u-1][j]

表示：

1
第 j 列
2
从第 u 行到第 d 行
3
之间的 1 的数量

固定：

1
上边界 u
2
下边界 d

后，

每一列的贡献变成：

col_j=a[d][j]-a[u-1][j]

于是问题转化为：

一个长度为 W 的非负数组中，求和为 K 的连续子数组个数。

第二步：列前缀和

构造前缀和：

1
b[0]=0
2

3
b[j]
4
=
5
b[j-1]+col_j

则区间：

[l+1,r]

的和为：

b[r]-b[l]

于是问题变成：

统计满足

b[r]-b[l]=K

的前缀和对数。

第三步：双指针

注意：

矩阵元素只有：

1
0 或 1

因此：

1
col_j ≥ 0

从而：

1
b[j]

单调不减。

对于每个左端点 l：

维护两个指针：

最小满足：

b[r_1]-b[l]\ge K

的位置。

最小满足：

b[r_2]-b[l]>K

的位置。

则：

1
[r1,r2)

中的所有位置都满足：

b[r]-b[l]=K

贡献：

r_2-r_1

即可。

子过程

定义：

1
subp(b,k)

统计：

b[r]-b[l]=k

的方案数。

由于：

1
b 单调不减

双指针总共只移动：

O(W)

次。

总复杂度

枚举上下边界：

O(H^2)

每次统计：

O(W)

因此总复杂度：

O(H^2W)

复杂度分析#

时间复杂度：

O(H^2W)

空间复杂度：

O(HW)

当：

H,W\le 500

时可以通过。

1
def subp(a, k):
2
    n = len(a)
3
    r1 = 0
4
    r2 = 0
5
    res = 0
6
    for l in range(n - 1):
7
        r1 = max(r1, l + 1)
8
        r2 = max(r2, l + 1)
9
        while r1 < n and a[r1] - a[l] < k:
10
            r1 += 1
11
        while r2 < n and a[r2] - a[l] <= k:
12
            r2 += 1
13
        res += r2 - r1
14
    return res
15
H, W, K = map(int, input().split())
16
a = [[0] * (W + 1) for _ in range(H + 1)]
17
for i in range(1, H + 1):
18
    s = input().strip()
19
    for j in range(1, W + 1):
20
        if s[j - 1] == '1':
21
            a[i][j] = 1
22
for i in range(1, H + 1):
23
    for j in range(1, W + 1):
24
        a[i][j] += a[i - 1][j]
25
ans = 0
26
for u in range(1, H + 1):
27
    for d in range(u, H + 1):
28
        b = [0] * (W + 1)
29
        for j in range(1, W + 1):
30
            b[j] = b[j - 1] + (a[d][j] - a[u - 1][j])
31
        ans += subp(b, K)
32
print(ans)

1
h, w, k = map(int, input().split())
2
grid = [input().strip() for _ in range(h)]
3
pre = [[0] * w for _ in range(h + 1)]
4
for i in range(h):
5
    for j in range(w):
6
        pre[i + 1][j] = pre[i][j] + (1 if grid[i][j] == '1' else 0)
7
ans = 0
8
for r1 in range(h):
9
    for r2 in range(r1, h):
10
        col_sum = [0] * w
11
        for j in range(w):
12
            col_sum[j] = pre[r2 + 1][j] - pre[r1][j]
13
        pref = 0
14
        cnt = {0: 1}
15
        for val in col_sum:
16
            pref += val
17
            if pref - k in cnt:
18
                ans += cnt[pref - k]
19
            cnt[pref] = cnt.get(pref, 0) + 1
20
print(ans)

E-树状数组#

题意#

有一个 N × N 的网格，初始时所有格子均为白色。

进行 Q 次操作：

操作 1

1
1 R

将第 R 行的所有格子染成黑色。

操作 2

1
2 C

将第 C 列的所有格子染成白色。

每次操作结束后，输出当前网格中的黑色格子数量。

数据范围

1
1 ≤ N,Q ≤ 3×10^5

显然不能真的维护整个矩阵。

思路分析#

对于任意一个格子：

1
(row , col)

最终颜色只取决于：

1
最近一次涉及它的操作

即：

最近一次给所在行染黑
最近一次给所在列染白

谁发生得更晚。

时间轴思想

将每次操作编号：

1
1,2,3,...,Q

对于一行 R：

记录：

1
last_row[R]

表示最近一次：

1
操作 1

出现的位置。

对于一列 C：

记录：

1
last_col[C]

表示最近一次：

1
操作 2

出现的位置。

对于格子：

1
(R,C)

若：

1
last_row[R] > last_col[C]

则该格子为黑色。

否则为白色。

维护黑色格子数量

设当前黑格数量为：

1
b

操作 1：整行染黑

假设：

1
1 R

发生在时间：

1
i

第一次出现

如果此前从未染黑过该行：

1
last_row[R] == -1

则整行直接变黑：

1
b += N

不是第一次

旧时间：

1
old = last_row[R]

原来该行贡献的黑格数为：

1
N - (在 old 之后被染白的列)

更新后：

1
N - (在 i 之后被染白的列)

两者差值就是新增黑格数。

设：

1
kind=old 与 i 之间出现的列操作数量

则：

1
b += kind

操作 2：整列染白

同理：

1
2 C

若是第一次出现：

1
last_col[C] = 0

表示初始白色状态。

设旧时间：

1
old = last_col[C]

统计：

1
old 与 i 之间出现的行操作数量

记为：

1
kind

这些格子原本是黑色，

现在被染白。

因此：

1
b -= kind

如何统计区间内操作数？

需要支持：

1
统计某类操作在时间区间内出现次数

例如：

1
行操作

出现于：

1
3,7,10,...

要查询：

1
[old , i)

之间有多少个。

这是典型：

1
单点修改
2
前缀和统计

使用树状数组维护即可。

树状数组维护

建立两个 Fenwick Tree：

1
f[0]

记录：

1
行操作

出现的位置。

1
f[1]

记录：

1
列操作

出现的位置。

查询：

1
f[t].sum(l,r)

即可得到：

1
[l,r)

区间内该类操作数量。

算法流程

维护：

1
last_row
2
last_col

以及：

1
b

当前黑格数。

对于操作：

行染黑

1
if first:
2
    b += N
3
else:
4
    kind = 区间内列操作数量
5
    b += kind

列染白

1
kind = 区间内行操作数量
2
b -= kind

更新：

1
last
2
Fenwick

输出答案。

正确性证明

对于任意格子：

1
(r,c)

颜色仅由：

1
最近一次行染黑
2
最近一次列染白

决定。

若最近的是行操作：

1
last_row[r] > last_col[c]

则该格子黑色。

否则白色。

一次新的行操作：

只会影响：

1
该行

中那些最近一次列操作发生在：

1
old ~ now

之间的格子。

数量正是区间中的列操作种类数。

因此：

1
b += kind

正确。

同理列操作：

会把对应区间产生的黑格全部消除。

因此：

1
b -= kind

正确。

故算法正确。

复杂度分析#

每次操作：

Fenwick 查询一次
Fenwick 修改一次

均为：

1
O(\log Q)

总复杂度：

1
O(Q\log Q)

空间复杂度：

1
O(N+Q)

1
class FenwickTree:
2
    def __init__(self, n):
3
        self.n = n
4
        self.bit = [0] * (n + 1)
5
    def add(self, idx, val):
6
        idx += 1
7
        while idx <= self.n:
8
            self.bit[idx] += val
9
            idx += idx & -idx
10
    def sum_prefix(self, r):
11
        res = 0
12
        while r > 0:
13
            res += self.bit[r]
14
            r -= r & -r
15
        return res
16
    def sum(self, l, r):
17
        return self.sum_prefix(r) - self.sum_prefix(l)
18
N, Q = map(int, input().split())
19
# f[0]：记录行染黑操作出现的时间点
20
# f[1]：记录列染白操作出现的时间点
21
f = [FenwickTree(Q + 1) for _ in range(2)]
22
# 当前黑色格子数量
23
b = 0
24
# last[0][r]：第 r 行最近一次染黑的时间
25
# last[1][c]：第 c 列最近一次染白的时间
26
last = [
27
    [-1] * (N + 1),
28
    [0] * (N + 1)
29
]
30
for i in range(1, Q + 1):
31
    t, x = map(int, input().split())
32
    t -= 1
33
    if last[t][x] == -1:
34
        # 行第一次染黑
35
        b += N
36
    else:
37
        # 统计两次同类操作之间发生了多少次异类操作
38
        kind = f[1 - t].sum(last[t][x], i)
39
        if t == 0:
40
            # 行染黑
41
            b += kind
42
        else:
43
            # 列染白
44
            b -= kind
45
        # 删除旧时间点
46
        f[t].add(last[t][x], -1)
47
    # 记录当前操作时间
48
    f[t].add(i, 1)
49
    last[t][x] = i
50
    print(b)

涉及算法#

时间轴思想（Last Occurrence）
树状数组（Fenwick Tree）
前缀和统计
在线维护答案
数据结构优化

音乐

音乐

ABC461-①贪心②前缀和+双指针③树状数组#

目录#

C-贪心#

题意#

思路分析#

正确性证明#

算法步骤#

复杂度分析#

D-前缀和+双指针#

题意#

思路分析#

复杂度分析#

E-树状数组#

题意#

思路分析#

复杂度分析#

涉及算法#

音乐

目录