Codeforces Round 927 (Div. 3)

比赛链接，官方题解

ID	Difficulty (0-5)	Topic	Status	Code
A	0	Greedy	Solved	A.cpp
B	0	Greedy	Solved	B.cpp
C	1	Implementation	Solved	C.cpp
D	1	Greedy	Solved	D.cpp
E	1	Implementation	Solved	E.cpp
F	2	Dynamic Programming	Solved	F.cpp
G	3	Shortest Path	Upsolved	G.cpp

F. Feed Cats

给若干线段，选一些点。

使得每个线段最多包含一个选中的点，并且最大化包含选中点的线段数。

离散化之后有用的点和线段数同级别。

对每个位置 $i$，预处理其覆盖的线段数量 $cnt_i$ ，和这些线段左边界的最小值 $L_i$。

动态规划。令 $f_i$ 表示最后一个选中的点是 $i$​ ，最多能覆盖多少个线段。

则 $f_i=\max_{1\le j<L_i} f_j+cnt_i$ ，维护前缀 max 支持转移，总复杂度 $O(n)$ 。

G. Moving Platforms

无向图 $n$ 个点 $m$ 条边，每个点有两个参数 $l_i,s_i$ ，以及一个参数 $H$ 。

第 $t$ 时刻，第 $i$ 个点的颜色是 $(l_i+s_i\cdot (t-1))\mod H$ 。

一条边只有两个端点颜色相同的时候才有效。

$1$ 时刻起从 $1$ 号点出发，每个时刻可以选择不动，或者走一条有效的边，求最早能到 $n$ 的时间。

Dijkstra 求最短路。

考虑每次在一个点扫描它的所有出边，在 $u\to v$ 这条边上所需的时间，就是最近一次两个点颜色相同的时刻和现在时刻 （即 $dis[u]$ ）的差值。

求最近的颜色相同的时刻是一个同余方程，可以扩展欧几里得求出。

总复杂度 $O(m\log n+m\log H)$​ 。细节：

1. 每个时刻只能走一条边，所以更新的时候要处理成 dis[v] = dis[u] + dlt + 1；
2. dis 是 long long 级别，求当前层的 l[u]+s[u]*(dis[u]-1) 会爆 long long 。