做题记录 25.10.3

· · 个人记录

\textcolor{yellow}\odot P11841 [USACO25FEB] Transforming Pairs S

每个状态的前驱是确定的，因此从 (c,d) 开始倒序模拟即可，优化是容易的，时间复杂度 O(T\log V)

代码

\purple\odot P5179 Fraction

考虑分类讨论并迭代

当 (\frac ab,\frac cd) 中存在整数，即 \lfloor\frac ab\rfloor+1\le \lceil\frac cd\rceil-1 时，显然取 p=\lfloor\frac ab\rfloor+1,q=1

当 a=0 时，即要求 \frac pq<\frac cd，即 q>\frac{pd}c，取 p=1，q=\lfloor\frac dc\rfloor+1

当 a\le b,c\le d 时，转化为 \frac dc<\frac qp<\frac ba 并递归

否则令 t=\lfloor \frac ab\rfloor，转化为 \frac{a-tb}b<\frac{p-tq}q<\frac{c-td}d 并递归

可证所有子问题都取最小时答案也是最小的

时间复杂度 O(T\log V)

代码

参考

\purple\odot P9193 [USACO23OPEN] Good Bitstrings P

用 [a-b] 表示直线 (0,0)-(a,b)

将二元组放到 xOy 平面上，则一组 (a,b) 对应字符串相当于从原点出发，若在 [a-b] 下方则向上走，否则向右走（点在 [a-b] 上认为是上方），行动的序列即为 (a,b) 对应字符串，字符串的前缀即为行动序列的前缀

定理 \text 1：点 (x,y)(0\le x\le a,0\le y\le b) 合法当且仅当\forall 0\le x_0\le x,\forall 0\le y_0\le y，(x_0,y_0) 在直线 [a-b] 和直线 [x-y] 的同一侧

画图后该结论比较显然

定理 \text 2：对于第一象限（含坐标轴）内的整点 A,B 满足 \overrightarrow{OA}\times \overrightarrow{OB}=1，任意严格位于射线 OA 和射线 OB 之间的整点 C，必然存在且只存在一组 k_1,k_2\in\mathbb N^+ 使得 k_1\overrightarrow{OA}+k_2\overrightarrow{OB}=\overrightarrow{OC}，且满足该要求的点一定在两条射线之间

证明：

从而 \overrightarrow{OA} 和 \overrightarrow{OB} 之间最小整点为 \overrightarrow{OA}+\overrightarrow{OB}

令 A=(1,0),B=(0,1)，两者向 [a-b] 靠拢（类似 \text{Stern-Brocot Tree} 上递归）：

令 \overrightarrow{OC}=\overrightarrow{OA}+\overrightarrow{OB}，则 C 为两射线之间最小整点

当 C 在 [a-b] 上方时，对于 \angle{BOC} 中的点，C 在它们对应直线的下方，根据定理 \text 1 它们都不合法，令 B\gets C

当 C 在 [a-b] 下方时，对于 \angle{AOC} 中的点，C 在它们对应直线的上方，根据定理 \text 1 它们都不合法，令 A\gets C

当 B 在 [a-b] 上时结束

显然合法的点都在这些直线上

可证结束时必有 B=(\frac a{\gcd(a,b)},\frac b{\gcd(a,b)})，\overrightarrow{OA}\times \overrightarrow{(a,b)}=\gcd(a,b)，令最终的 A 为 A_f，则第一次修改 A 之后的 B 加上 A_f 后仍然合法，系数变为 2

注意最终要加上 \gcd(a,b) 个和 [a-b] 共线的和 \gcd(a,b) 个它们加上 A_f，然后减去不合法的 (0,1)

实际实现时无需记录 A 和 B，保存 k_1 和 k_2 的值即可，容易发现相当于辗转相减，容易优化到辗转相除

时间复杂度 O(t\log V)

代码

参考