模拟赛T3：整数（详解）
2025-08-19 16:32:04
发布于：浙江
7阅读
0回复
0点赞
链接描述
这道题看到的第一眼回想到BFS。
第二眼会想到最短路。
但是问题在于第二种操作到底应该加多少？
经过一些思考便可得出，其最多加到距离最近的2的整数次幂。
那么大概就会得出一个基本的思路。
然后你就可以获得一份40pts的代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e7+5;
typedef long long ll;
ll n,a,b,c;
struct Node{
int z;
ll q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>pq;
ll dis[N];
bool vis[N];
void solve1(){
memset(vis,0,sizeof vis);
for(int i=1;i<=2*n;i++)dis[i]=1e9;
dis[n]=0;
pq.push({n,0});
for(int i=n+1;i<=2*n;i++){
dis[i]=b;
pq.push({i,b});
}
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
if(k>1){
//pq.push({k-1,sum.q+a});
if(dis[k-1]>dis[k]+a){
dis[k-1]=dis[k]+a;
pq.push({k-1,dis[k-1]});
}
}
if(k%2==0){
//pq.push({k/1,sum.q+c});
if(dis[k/2]>dis[k]+c){
dis[k/2]=dis[k]+c;
pq.push({k/2,dis[k/2]});
}
}
}
cout<<dis[1]<<endl;
while(!pq.empty())pq.pop();
}
void solve(){
cin>>n>>a>>b>>c;
if(a<=1e6&&b<=1e6&&c<=1e6){
solve1();
}
}
int main(){
int t;
cin>>t;
while(t--)solve();
return 0;
}
然后可以再观察一下说明/提示：
发现50%-60%的数据中，，这就代表着只用减法和除法。
也就是说，当你是一个奇数的时候，你就可以先试用减法。
而对于偶数，你就要考虑使用减法更好还是除法更好。
然后就可以写代码了。
直接在上面的代码的基础上进行修改就好了。
只要加这样的代码，你就能多获得10pts:
void solve2(){
ll ans=0;
while(n!=1){
if(n%2==1)ans+=a,n--;
else ans+=min((n/2)*a,c),n/=2;
}
cout<<ans<<endl;
return;
}
然后可以再观察一下说明/提示：
发现60%-70%的数据中，，这就代表着只用加法和除法。
那么代码的实现就是将加到二的幂次，然后再用除法。
注意：左移是两个小于号。
void solve3(){
for(int i=0;i<=40;i++){
if((1ll<<i)>n){
cout<<b+i*c<<endl;
return;
}
if((1ll<<i)==n){
cout<<i*c<<endl;
return;
}
}
}
然后就是痛苦时间。
这里空空如也
有帮助，赞一个