NOIP2022模拟赛二 By JTZ 10.18
A
暴力枚举左端点 $i$，再二分一个右端点满足 $k|\gcd(i,r)$，再在该区间二分满足 $\gcd(i,r)==k$。
$O(n\log n)$
B
首先 Tarjan 跑出所有强连通分量，并对每个强连通分量分别求解并选取最小权值点。
显然严格次小值有两种情况：
- 某个强连通分量选严格次小而不是最小。
- 某个强连通分量选两个最小点。
C CF1340C
设 $f_{i,j}$ 表示第 $i$ 秒到达第 $j$ 个绝对安全至少经过多少个周期。
转移的边仅有相邻两个，于是直接 01-BFS。
$O(mg)$
D CF778D Parquet Re-laying
操作可逆，考虑将起始状态与结束状态转移到一个中间的状态。
不妨设长为偶数，设构造中间状态所有地砖都是横的。
能旋转就旋转，发现一定可以转到。