当前位置：首页 > ops >正文

2025 吉林CCPC

ops 2025/7/23 10:48:46

文章目录

2025 吉林CCPC
- A.交互题
- F.字符串（暴力、后缀和）
- D.互质（最大素数间隔）
- 总结

2025 吉林CCPC

题目链接：

Dashboard - The 18th Jilin Provincial Collegiate Programming Contest - Codeforces

sdccpc20250527 - Virtual Judge

A.交互题

实质上就是两个分数比大小。

虽然没写出来，不过自己的思路是正确的，值得庆幸。

不然，连一个分数比较大小都没想到解决办法，那更丢人了。

a,b,c,d 都是正整数。
用真分数来比较更优
分数越大，倒数越小，成反比
如果是99/100 可以换成 1/100，来比较相当于一个二分（这种循环进行400次就够了）

这样就形成初步的思路。

还有几个注意事项:

运算过程不能溢出，一旦出现“err”就会WA

起初我是通过判断是否溢出，来确定谁大谁小，这种方法不可取。

注意次数！！！

超过6666，就会err

次数太少就会找不到答案！

整除！！！分子变成0啦

具体：

在循环中，将其换成真分数，如果a/b不等于 c/d ,直接得出答案

**考虑整除使得分子变成 0 **

其中一个变成0 ，就确定了分数大小。

将分数换成倒数，这时候又变成了假分数。

不断循环。

分子分母颠倒，改变变量，不改变值，减少操作次数。循环里询问9次，循环大概需要进行737~740次。

这个数据范围很重要！！！

string check(){string s;cin >> s;return s;
}
void solve(){int f=0,p=740;string t ,tt;char aa='a',bb='b',cc='c',dd='d';while(p--){cout << "/ r0 "<<aa<<' '<<bb<< endl;check();cout << "/ r1 "<<cc<<" "<<dd << endl;check();cout << "? r0 r1" << endl;t=check();if(t!="="){if(f==0) cout << "! " << t << endl;else{if(t=="<") cout << "! >"<< endl;else cout << "! <"<< endl;}check();return ;}cout << "* r1 r1 "<<dd << endl;check();cout << "* r0 r0 "<<bb << endl;check();	cout << "- "<<aa<<' '<<aa<<" r0"<< endl;check();cout << "- "<<cc<<' '<<cc<<" r1"<< endl;check();cout<<"? "<<aa<<" r2"<<endl;t=check();cout<<"? "<<cc<<" r2"<<endl;tt=check();if(t=="="&&tt=="="){cout<<"! ="<<endl;check();return;}else if(t=="="){if(f==0)cout<<"! <"<<endl;elsecout<<"! >"<<endl;check();return;}	 	 else if(tt=="="){if(f==0)cout<<"! >"<<endl;elsecout<<"! <"<<endl;check();return;}f^=1;char w;w=aa;aa=bb,bb=w;w=cc;cc=dd;dd=w;	 }cout<<"* "<<aa<<" "<<aa<<" "<< dd<<endl; check();cout<<"* "<<cc<<" "<<cc<<" "<< bb<<endl; check();cout<<"? "<<aa<<' '<< cc<<endl;   t=check();if(f==0) cout<<"! "<<t<<endl;else{if(t=="<") cout << "! >"<< endl;else if(t==">") cout << "! <"<< endl;else cout<<"! ="<<endl;}check();return ;
}

F.字符串（暴力、后缀和）

题目数据比较水，暴力就可以过，O(n*n)

可以优化为O(n) ，用两次后缀和

int a[N];
void solve()
{ int n,ans=0;cin>>n;string s;cin>>s;fir_(i,n-1,0){if(s[i]=='f')a[i]+=1;a[i]+=a[i+1];//计算后缀f的数量}fir_(i,n-2,0){a[i]+=a[i+1];//计算后缀f 的总距离if(s[i]=='e')ans+=a[i+1];}cout<<ans<<'\n';
}