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
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
string a,b;
int main() {
while(cin>>a>>b) {
string c=a+b,d=b+a;
if(c>d) puts(">");
else if(c<d) puts("<");
else puts("=");
}
return 0;
}