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;
}