how to

教学计划-差分与离散化

Sep 17, 2024
notesjulyfun工作william240914
3 Minutes
467 Words

差分与离散化

https://www.luogu.com.cn/record/176971240 火烧赤壁

前缀和思想:在起火的左端点标注 +1,右端点标注 -1,则做前缀和以后,大于 0 的线段都是起火的,例如:

1
[ 0 0 +1 +1 0 -1 -1 0]
2
[ 0 0 1 2 2 1 0 ]

这里就有长度为 4 的起火段。

由于坐标太大,无法直接前缀和,可以离散化,将大坐标映射到小坐标,即排序 + 去重后用 map 标号,在做前缀和即可。

1
n = int(input())
2
x = []
3
y = []
4
for _ in range(n):
5
xx, yy = map(int, input().split())
6
x.append(xx)
7
y.append(yy)
8
a = sorted(x + y)
9
b = [a[0]]
10
for i in range(1, len(a)):
11
if a[i] != a[i - 1]:
12
b.append(a[i])
13
di = {}
14
for i in range(len(b)):
15
di[b[i]] = i
11 collapsed lines
16
pre = [0] * len(b)
17
for i in range(n):
18
pre[di[x[i]]] += 1
19
pre[di[y[i]]] -= 1
20
ans = 0
21
for i in range(1, len(b)):
22
pre[i] += pre[i - 1]
23
if pre[i - 1] > 0:
24
ans += b[i] - b[i - 1]
25
26
print(ans)
1
n = int(input())
2
x = []
3
y = []
4
for _ in range(n):
5
xx, yy = map(int, input().split())
6
x.append(xx)
7
y.append(yy)
8
a = sorted(___)
9
b = [a[0]]
10
for i in range(1, len(a)):
11
if ___:
12
b.append(a[i])
13
di = {}
14
for i in range(len(b)):
15
___ = i
9 collapsed lines
16
pre = [0] * len(b)
17
for i in range(n):
18
___ += 1
19
___ -= 1
20
ans = 0
21
for i in range(1, len(b)):
22
pre[i] += pre[i - 1]
23
if pre[i - 1] > 0:
24
ans += ___

T2 # P3029 [USACO11NOV] Cow Lineup S

https://usaco.org/index.php?page=viewproblem2&cpid=89

i 表示当前取的左端点,j 表示右端点。用 map 离散化存储不同品种的奶牛数量。当 i 变动时,向右移动 j 保证奶牛品种数必须为全部品种即可。

作业题 P1904 天际线

https://www.luogu.com.cn/problem/P1904

由于坐标范围很小,可以用 h[i] 表示 i 开始的单位线段所占据的最高楼栋。初值均为 $0$,随后查找 h[i] 变化处输出横纵坐标即可。

1
H = [0] * 10005
2
3
while True:
4
try:
5
a, h, b = map(int, input().split())
6
except EOFError:
7
break
8
9
for i in range(a, b + 1):
10
H[i] = max(H[i], h)
11
12
h = 0
13
for i in range(1, int(1e4)):
14
if h != H[i]:
15
h = H[i]
1 collapsed line
16
print(i, H[i], end=' ')
Article title:教学计划-差分与离散化
Article author:Julyfun
Release time:Sep 17, 2024
Copyright 2025
Sitemap