2023 NOI 春季测试
T1 不再赘述。
P9118 [春季测试 2023] 幂次【民间数据】
考场上没判 k 巨大的情况。
\(n\le10^{18}\) ，所以当 \(b\ge3\) 时就有 \(a\le10^6\) 了。考虑对 \(b=2\) 和其他情况讨论。直接算出完全平方数的个数，枚举 \(b\ge3\) 且不能表示为平方数的数，去重就是丢到 set 里面。
P9119 [春季测试 2023] 圣诞树【民间数据，spj 暂缺】
发现这是一个凸多边形，得到一个性质：两条边不会交叉。如果有交叉，显然交换它们长度会更小。
那么假设从 x 出发，那么下一步必然走 x+1 或 x-1 ，否则遍历回来必然有相交。定义 \(f_{i,j,0}\) 表示 \(i,i+1,i+2\dots j\) 的最短路径， \(f_{i,j,1}\) 表示 \(i,i-1,i-2\dots j\) 的最短路径。有转移式：
\[f_{i,j,0}=\min(\text{dist}(i,i+1)+f_{i+1,j,0},\text{dist}(i,j)+f_{j,i+1,1}) \]\[f_{i,j,1}=\min(\text{dist}(i,i-1)+f_{i-1,j,1},\text{dist}(i,j)+f_{j,i-1,0}) \]其中 \(\text{dist(i,j)}\) 表示 i,j 间的距离。边界是 \(f_{i,i,0/1}=0\) （注意这里我们并没有考虑环形的条件，比如 \(1\rightarrow n\) ）。