『RetOI』Round 2 题解
2026-02-21 17:38:10
发布于：江苏
23阅读
0回复
0点赞
个人难度：橙红黄橙黄
T1
高精度乘法板子
#include<bits/stdc++.h>
using namespace std;
string s;
long long n=1,a[5005],b;
int main(){
cin>>s;
a[1]=1;
for(int i=0;i<s.size();i++){
b=s[i];
for(int j=1;j<=n;j++){
a[j]*=b;
a[j]+=a[j-1]/10;
a[j-1]%=10;
}
while(a[n]>=10){
n++;
a[n]+=a[n-1]/10;
a[n-1]%=10;
}
}
for(int i=n;i>=1;i--)cout<<a[i];
}
T2
可以将问题转化为求 年内的闰年数量和 年内的闰年数量
#include<bits/stdc++.h>
using namespace std;
long long l,r;
int main(){
cin>>l>>r;
l--;
cout<<(r/4-r/100+r/400)-(l/4-l/100+l/400);
}
T3
区间DP，设 表示字符串第 个字符到第 个字符时先手能否必胜。
#include<bits/stdc++.h>
using namespace std;
int T,n,a[105],dp[105][105];
string s;
int main(){
cin>>T;
while(T--){
cin>>s;
n=0;
memset(dp,0,sizeof(dp));
for(char i:s){
if(i=='P'||i=='i'||i=='p'||i=='l'||i=='o'||i=='n'||i=='g')a[++n]=1;
else a[++n]=0;
}
s=" "+s;
for(int i=0;i<=n;i++)dp[i+1][i]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
int k=j+i-1;
if(i==1){
dp[j][k]=1;
continue;
}
if(s[j]==s[k])dp[j][k]=1-dp[j+1][k-1];
else if(a[j]==1&&a[k]==0)dp[j][k]=1-dp[j+1][k];
else if(a[j]==0&&a[k]==1)dp[j][k]=1-dp[j][k-1];
else if(a[j]==0&&a[k]==0)dp[j][k]=max(1-dp[j+1][k],1-dp[j][k-1]);
else dp[j][k]=max(1-dp[j+2][k],1-dp[j][k-2]);
}
}
if(dp[1][n])cout<<"lz will win.\n";
else cout<<"pzh will win.\n";
}
}
T4
模拟即可
#include<bits/stdc++.h>
using namespace std;
long long T,n,m,x,y;
int main(){
cin>>T;
while(T--){
cin>>n>>m>>x>>y;
if(n==1||m==1){
if(n==1&&y!=m&&y!=1||m==1&&x!=n&&x!=1)cout<<"No\n";
else cout<<"Yes\n";
}else if(n%2==0||m%2==0)cout<<"Yes\n";
else if(x%2==y%2)cout<<"Yes\n";
else cout<<"No\n";
}
}
T5
可以很快想出埃氏筛后对每个质数格子的贡献求和，得到一份TLE代码
#include<bits/stdc++.h>
using namespace std;
bool a[2000005];
int n,m,mod=1e9+7;
long long b[2000005]={1},num;
long long qpow(long long x){
long long ans=1,k=mod-2;
while(k){
if(k%2)ans=ans*x%mod;
x=x*x%mod;
k/=2;
}
return ans;
}
long long C(long long x,long long y){
return b[y]*qpow(b[x]*b[y-x]%mod)%mod;
}
int main(){
cin>>n>>m;
for(int i=2;i<=n+m;i++)a[i]=false;
for(int i=2;i<=n+m;i++)if(!a[i]){
for(int j=i*2;j<=n+m;j+=i)a[j]=true;
}
for(int i=1;i<=n+m;i++)b[i]=b[i-1]*i%mod;
for(int i=2;i<=n+m;i++)if(!a[i]){
for(int j=max(1,i-n);j<=min(i-1,m);j++){
num=(num+C(j-1,i-2)*C(m-j,n+m-i)%mod)%mod;
}
}
cout<<num;
}
我们对小规模数据进行一些测试就会发现每个质数的贡献相同，所以第二层循环只需循环一次，结果乘上质数个数就能得出答案
#include<bits/stdc++.h>
using namespace std;
bool a[2000005];
int n,m,mod=1e9+7;
long long b[2000005]={1},v,num,cnt;
long long qpow(long long x){
long long ans=1,k=mod-2;
while(k){
if(k%2)ans=ans*x%mod;
x=x*x%mod;
k/=2;
}
return ans;
}
long long C(long long x,long long y){
return b[y]*qpow(b[x]*b[y-x]%mod)%mod;
}
int main(){
cin>>n>>m;
for(int i=2;i<=n+m;i++)a[i]=false;
for(int i=2;i<=n+m;i++)if(!a[i]){
for(int j=i*2;j<=n+m;j+=i)a[j]=true;
}
for(int i=1;i<=n+m;i++)b[i]=b[i-1]*i%mod;
for(int i=2;i<=n+m;i++)if(!a[i]){
cnt++;
if(v)continue;
v=1;
for(int j=max(1,i-n);j<=min(i-1,m);j++){
num=(num+C(j-1,i-2)*C(m-j,n+m-i)%mod)%mod;
}
}
cout<<num*cnt%mod;
}
乃悟T5假寐，盖以水蓝。
有帮助，赞一个