425 字
1 分钟
CF476

A. Dreamoon and Stairs#

nn 节楼梯,每次爬 1122 节,希望移动的步数是 mm 的倍数,问最少移动步数。

若每次爬 11 节,共 nn 步,若每次爬 22 节,共 n+12\frac{\lfloor n+1 \rfloor}{2} 步,这之间的任意步数均可达到,找到区间内最小的 mm 的倍数即为答案,若没有即无解。

signed main(){
int n,m;cin>>n>>m;
int minn=(n+1)/2,maxx=n;
int ans=-1;
for(int i=minn;i<=maxx;i++){
if(i%m==0){
ans=i;
break;
}
}
cout<<ans<<endl;
return 0;
}

B. Dreamoon and WiFi#

给定一字符串,字符串中 + 表示正方向移动一个单位,- 表示负方向移动一个单位,给定另一字符串,除了 +- 以外增加了 ? 表示正负方向各有 50%50\% 的概率,问第二个字符串有多大概率到达和第一个字符串相同的位置。

易得,正负移动的先后对结果无影响,则可以对第一个字符串中的正负方向位移计数(可以正负方向分别计数也可以只记录最终位置,原理相同),最后根据不确定项的二项分布计算答案概率。

int qmi(int a,int b){
int ans=1;
while(b){
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int C(int A,int a){
if(a>A)return 0;
int ans=1;
for(int i=1,j=A;i<=a;i++,j--){
ans=ans*j;
ans=ans/i;
}
return ans;
}
signed main(){
string s;cin>>s;
int cnt[2]={0};
for(int i=0;i<s.size();i++){
if(s[i]=='+')cnt[1]++;
else cnt[0]++;
}
cin>>s;
for(int i=0;i<s.size();i++){
if(s[i]=='+')cnt[1]--;
else if(s[i]=='-')cnt[0]--;
}
if(cnt[0]<0||cnt[1]<0)cout<<"0.000000000000\n";
else{
double d=1;
for(int i=0;i<cnt[0]+cnt[1];i++)d/=2;
cout<<fixed<<setprecision(12)<<C(cnt[0]+cnt[1],cnt[0])*d<<endl;
}
return 0;
}

C. Dreamoon and Sums#

给定整数 aabb,计算所有满足 x mod b0,xbx mod b=kx\ mod\ b \ne 0, \frac{\lfloor \frac{x}{b} \rfloor}{x\ mod\ b}=kxx 之和,其中 1ka1\leq k\leq a。 设 xb=d,x mod b=m\left\lfloor\frac{x}{b}\right\rfloor=d,x\ mod\ b=m, 则有 d=mk,x=db+m    x=mkb+m    x=m(kb+1)d=mk,x=db+m\implies x=mkb+m\implies x=m(kb+1),其中有 1m<b,1ka1\leq m<b,1\leq k\leq a。 易得。

const int mod=1e9+7;
signed main(){
int a,b;cin>>a>>b;
a=(((1+a)*a/2)%mod*b%mod+a)%mod;
cout<<((b-1)*b/2)%mod*a%mod<<endl;
return 0;
}
分享

如果这篇文章对你有帮助,欢迎分享给更多人!

CF476
https://leaf146.cn/posts/cf476
作者
LeAf146
发布于
2026-07-09
许可协议
MIT

部分信息可能已经过时