NOIP2022模拟赛二 By JTZ 10.18

NOIP2022模拟赛二 By JTZ 10.18

yzxoi

2022-10-18 (Updated: 2022-10-18)

oi

DP, Tarjan, 二分, 暴力, 构造, 贪心

A

暴力枚举左端点 i，再二分一个右端点满足 k|\gcd(i,r)，再在该区间二分满足 \gcd(i,r)==k。

O(n\log n)

63091

B

首先 Tarjan 跑出所有强连通分量，并对每个强连通分量分别求解并选取最小权值点。

显然严格次小值有两种情况：

• 某个强连通分量选严格次小而不是最小。
• 某个强连通分量选两个最小点。

63116

C CF1340C

设 f_{i,j} 表示第 i 秒到达第 j 个绝对安全至少经过多少个周期。

转移的边仅有相邻两个，于是直接 01-BFS。

O(mg)

176863749

D CF778D Parquet Re-laying

操作可逆，考虑将起始状态与结束状态转移到一个中间的状态。

不妨设长为偶数，设构造中间状态所有地砖都是横的。

能旋转就旋转，发现一定可以转到。

176863439