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(nlog n)
63091
B
首先 Tarjan 跑出所有强连通分量，并对每个强连通分量分别求解并选取最小权值点。
显然严格次小值有两种情况：
- 某个强连通分量选严格次小而不是最小。
- 某个强连通分量选两个最小点。
63116
C CF1340C
设 f_{i,j} 表示第 i 秒到达第 j 个绝对安全至少经过多少个周期。
转移的边仅有相邻两个，于是直接 01-BFS。
O(mg)
176863749
D CF778D Parquet Re-laying
操作可逆，考虑将起始状态与结束状态转移到一个中间的状态。
不妨设长为偶数，设构造中间状态所有地砖都是横的。
能旋转就旋转，发现一定可以转到。
176863439
