ABC463-①C-离线查询+贪心/单调栈②D-二分答案③E-Dijkstra+虚拟节点④F-逆元+组合数学#

C-离线查询+贪心/单调栈#

题目#

目前，会议室里有 $N$ 个高桥（Takahashi）。高桥在一间会议室里。其中 $i$ 个 $(1\le i\le N)$ 人的身高是 $H _ i$ 。高桥的身高为 $H _ i$ ，并将在 $L _ i$ 分钟后离开会议室。高桥一旦离开会议室，就再也不会回来了。

你有 $Q$ 个问题，请按顺序回答。对于 $i$ - $(1\le i\le Q)$ 个查询，你会得到一个整数 $T _ i$ ，所以请找出从现在起 $T _ i+\dfrac12$ 分钟后在房间里的高桥的最大身高。在这个问题的约束条件下，可以保证从现在起 $T _ i+\dfrac12$ 分钟后至少有一个高桥在房间里。

离线查询+贪心#

输入是按照时间顺序（升序）来的，对q进行离线查询（按照时间递减排序），逆序遍历维护最大的身高即可

1
n = int(input())
2
h = []
3
l = []
4
for _ in range(n):
5
    hi, li = map(int, input().split())
6
    h.append(hi)
7
    l.append(li)
8
q = int(input())
9
t = list(map(int, input().split()))
10
quer = [(t[i], i) for i in range(q)]
11
quer.sort(reverse=True)
12
ans = [0] * q
13
max_h = 0
14
idx = n - 1
15
for ti, qi in quer:
16
    while idx >= 0 and l[idx] > ti:
17
        max_h = max(max_h, h[idx])
18
        idx -= 1
19
    ans[qi] = max_h
20
print('\n'.join(map(str, ans)))

单调栈#

对于两个人 i 和 j，如果 i 比 j 先离开（L_i < L_j）且 i 的身高更矮（H_i ≤ H_j），那么在 j 离开之前的任何查询中，i 都不可能是答案（因为 j 更高且在房间里待得更久）。

同时满足”离开更早”和”身高更矮”的人是无用的
只有在”离开时间”和”身高”两个维度上都构成反比关系的人才是候选答案

1
import sys
2
import bisect
3
def solve():
4
    input = sys.stdin.readline
5
    n = int(input())
6
    # 单调栈：维护 (身高, 离开时间)，满足身高严格递减，离开时间递增
7
    stack = []
8
    for _ in range(n):
9
        h, l = map(int, input().split())
10
        # 淘汰离开更早但身高更矮的人
11
        while stack and stack[-1][0] <= h:
12
            stack.pop()
13
        stack.append((h, l))
14
    q = int(input())
15
    t = list(map(int, input().split()))
16
    # 提取离开时间用于二分
17
    leave_times = [l for _, l in stack]
18
    ans = []
19
    for ti in t:
20
        # 找到第一个离开时间 > ti 的位置
21
        pos = bisect.bisect_right(leave_times, ti)
22
        ans.append(str(stack[pos][0]))
23
    print('\n'.join(ans))
24
if __name__ == "__main__":
25
    solve()

D-二分答案#

题目#

在一条数线上有 $N$ 块布。 $i$ /- $(1\le i\le N)$ 块布覆盖了直线上的区间 $\lbrack L _ i,R _ i\rbrack$ 。直线上的一点可能被两块或更多块布覆盖，也可能没有被任何一块布覆盖。

如果直线上的某一点同时被两块布覆盖，则称两块布重叠。

对于不重叠的两块布，其距离定义如下：

一块布覆盖的所有点 $p$ 和另一块布覆盖的所有点 $q$ 上 $|p-q|$ 的最小值。

对于没有两块布重叠的 $K$ 块布，将其分数定义为所有这些布对之间的最小距离。从 $N$ 块布中选择 $K$ 块布，使所选的布中没有两块重叠，求可能的最大得分。

如果无法选择 $K$ 这样的布，则输出 -1。

二分答案#

题目要求：从 N 个区间中选 K 个互不重叠的区间，最大化它们两两之间最小距离。

设答案为 D，则：

如果能在最小距离 ≥ D 的条件下选出 K 个区间
那么对于任何 D' < D 也一定能选出（条件更宽松）
对于任何 D' > D 一定选不出（条件更严格）

将所有区间按右端点从小到大排序
维护上一个选中区间的右端点 last_R
遍历每个区间 [L, R]：如果 L - last_R ≥ D，则选择该区间，更新 last_R = R
统计选中的数量是否≥k

1
def check(a, k, d):
2
    cnt = 0
3
    rr = -10 ** 18
4
    for l, r in a:
5
        if l - rr >= d:
6
            if d == 0 and l <= rr:
7
                continue
8
            cnt += 1
9
            rr = r
10
            if cnt >= k:
11
                return True
12
    return False
13
def main():
14
    n, k = map(int, input().split())
15
    a = []
16
    for _ in range(n):
17
        l, r = map(int, input().split())
18
        a.append((l, r))
19
    a.sort(key=lambda x: x[1])
20
    if not check(a, k, 0):
21
        print(-1)
22
        return
23
    l, r = -1, 10 ** 9 + 1
24
    while l + 1 < r:
25
        mid = (l + r) // 2
26
        if check(a, k, mid):
27
            l = mid
28
        else:
29
            r = mid
30
    print(l)
31
if __name__ == "__main__":
32
    main()

E-Dijkstra+虚拟节点#

题目#

AtCoder 国家有 $N$ 座城市和 $M$ 条道路。{9551763}条道路 $(1\le i\le M)$ 双向连接着 $u _ i$ 个城市和 $v _ i$ 个城市，从一个城市到另一个城市只需 $T _ i$ 分钟。

此外，每个城市都安装了翘曲门，使用翘曲门可以在 $X _ i+X _ j+Y$ 分钟内从城市 $i\ (1\le i\le N)$ 到达城市 $j\ (1\le j\le N)$ 。

国内没有其他城市之间的交通方式。

请为每个 $k=2,3,\ldots,N$ 解出下面的问题：

求从城市 $1$ 到城市 $k$ 所需的最少时间。

在同一城市，从一条道路或翘曲门到另一条道路或翘曲门所需的时间可以忽略不计。

Dijkstra+虚拟节点#

在带道路和传送门两种移动方式的图中，求从城市1到所有其他城市的最短时间。传送门代价为 X_i + X_j + Y。

最优路径最多使用一次传送门。因为使用多次传送门可以合并。因此路径只有两种情况：不使用传送门；先走道路到某城市 u，传送至 v，再走道路到终点

从城市1出发，只走道路，得到 dist_road[i]——不使用传送门到达 i 的最短时间。

枚举传送门起点 u，计算使用传送门的最小代价：从1走道路到某个 u，然后从 u 进入传送门，这部分的最小代价。

对于每个城市 i，传送方案有两种可能：

直接传送到 i，不再走路：min_entry + X_i + Y
传送到某个 v，再走道路到 i：这等价于以 min_entry + X_v + Y 为起点，在道路图上走最短路

实现：以 min(dist_road[i], min_entry + X_i + Y) 作为每个城市 i 的初始距离，跑第二次 Dijkstra（多源最短路），在道路图上传播。这自动覆盖了”传送后再走道路”的情况。

1
import heapq
2
n, m, y = map(int, input().split())
3
g = [[] for _ in range(n)]
4
for _ in range(m):
5
    u, v, t = map(int, input().split())
6
    u -= 1
7
    v -= 1
8
    g[u].append((v, t))
9
    g[v].append((u, t))
10
x = list(map(int, input().split()))
11
inf = 10 ** 30
12
dist_road = [inf] * n
13
dist_road[0] = 0
14
pq = [(0, 0)]
15
while pq:
16
    d, u = heapq.heappop(pq)
17
    if d != dist_road[u]:
18
        continue
19
    for v, t in g[u]:
20
        if dist_road[v] > d + t:
21
            dist_road[v] = d + t
22
            heapq.heappush(pq, (dist_road[v], v))
23

24
min_entry = inf
25
for i in range(n):
26
    if dist_road[i] != inf:
27
        min_entry = min(min_entry, dist_road[i] + x[i])
28
dist = [inf] * n
29
pq = []
30
for i in range(n):
31
    dist[i] = min(dist_road[i], min_entry + x[i] + y)
32
    heapq.heappush(pq, (dist[i], i))
33

34
while pq:
35
    d, u = heapq.heappop(pq)
36
    if d != dist[u]:
37
        continue
38
    for v, t in g[u]:
39
        if dist[v] > d + t:
40
            dist[v] = d + t
41
            heapq.heappush(pq, (dist[v], v))
42
ans = [str(dist[i]) for i in range(1, n)]
43
print(' '.join(ans))

音乐

音乐