当前位置: 代码迷 >> 综合 >> 牛客暑假多校训练营(第一场)F-Infinite String Comparision-字符串
  详细解决方案

牛客暑假多校训练营(第一场)F-Infinite String Comparision-字符串

热度:0   发布时间:2024-01-28 08:41:36.0

因为复制过来就散了,就截图发了
在这里插入图片描述
在这里插入图片描述
题意:
一个字符串可以无限复制,那么比较a,b字符串无限复制后,谁比较大。
思路:
这题一直被T,大概思路想到了,但是结束条件没有控制好,所以导致一直超时,这题应该是结束条件应该是最长的字符串的两倍就可以判断出来,找最小的循环节,但是lcm(两个字符串长度会超时),所以根据周期性引理,t1+t2-gcd(t1,t2)<2max(t1,t2),所以判断最长的长度2。否则就输出大小,至于比较的话,我们从0开始,通过取余的方式来判断它到哪一位了,因为我们是比较的步数相同,所以通过步数对长度取余来判断到哪一位了。
队友分享了一个函数截取字符串subst,string s=p.substr(i,lb);
p->需要截的字符串,i从第i为开始,截取lb的长度。
还有一种很简单的思路:把两个字符串a+b,再b+a,来判断两个字符串的大小。如果len a<len b,那么如果在a的长度下就能判断大小,那自然就输出了,但如果前len a个长度下相同,那么b的len a+1位于a的第一位进行比较,那么因为前面有相同的所以相加后就先会把相同的判断了,然后移位进行判断,反正就画画图来理解一下吧,我也稍微有点懵,这个做法tql。
代码:

#include<bits/stdc++.h>
using namespace std;
int main ()
{ios::sync_with_stdio(false);string a;string b;while(cin>>a>>b){int t1=a.size();int t2=b.size();int len=max(t1,t2)*2;int f=0;for(int i=0;i<=len;i++){if(a[i%t1]>b[i%t2]){//判断相同步数下两者字符大小f=1;cout<<">"<<endl;//输出被跳出break;}else if(a[i%t1]<b[i%t2]){f=1;cout<<"<"<<endl;//同理break;}}if(f==0) cout<<"="<<endl;}return 0;
}
  相关解决方案