NOIP2022模拟赛二 By JTZ 10.18
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
操作可逆,考虑将起始状态与结束状态转移到一个中间的状态。
不妨设长为偶数,设构造中间状态所有地砖都是横的。
能旋转就旋转,发现一定可以转到。