2020牛客暑期多校训练营(第一场)F. Infinite String Comparision
链接
https://ac.nowcoder.com/acm/contest/5666/F
题意
比较字符串 $a^\infty$,$b^\infty$ 的大小
思路
类比 $10$ 进制中无限循环小数,如 $0.233233…=\frac{233}{999}=\frac{233}{10^3-1}$
把字符串当做 $26$ 进制数,将串 $S$ 化为无限循环“小数”:$\frac{s}{26^{|s|}-1}$
则有:
$s^{\infty}>t^{\infty}\Leftrightarrow\frac{s}{26^{|s|}-1}>\frac{t}{26^{|t|}-1}\Leftrightarrow s\cdot26^{|t|}+t>t\cdot26^{|s|}+s\Leftrightarrow\overline{st}>\overline{ts}$
另外两种情况同理
官方题解
根据 Periodicity Lemma 可得,若 $s^{\infty}$ 和 $t^{\infty}$ 的前 $|s|+|t|-gcd(|s|,|t|)$ 位都相同,则 $s^{\infty}=t^{\infty}$
代码
1 |
|