题解：P9863 [POI 2021/2022 R2] arm

· · 题解

P9863 [POI 2021/2022 R2] arm

题目大意

初始时你有 1 个物品，你需要将物品的数量按若干次以下步骤增加到大于 n 个。

初始时数据库为空，问最小操作次数。

观察

操作序列可以划分为多个阶段，每个阶段包含：

假设进行 k 阶段操作，第 i 阶段使用了 1 次存储操作、 Xi 次增加操作，则：

综上可得，物品增长模式为：

最终数量 = (1 + x₁) × (1 + x₂) × ... × (1 + xₖ)

数学优化

因此，对于固定的阶段数 k，我们不难想到以下条件：

接下来就很明显了，考虑使用二分的方法完成，具体请见代码。

代码详解

#include<bits/stdc++.h>
#define imx __int128
using namespace std;
imx n,a,b,ans,l,r,now;
// 安全计算x的k次方，防止溢出
imx spw(imx x,imx k){
    imx p=1;
    for(imx i=1;i<=k;i++){
        if(p>n) return n+2;    // 已超过n，提前返回
        p*=x;
        if(p>n) return n+2;    // 再次检查是否溢出
    }
    return p;
}

// __int128输入输出函数
imx iread(){
    imx x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
void iprint(imx x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) iprint(x/10);
    putchar(x%10+'0');
    return;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=iread(),a=iread(),b=iread();
    // 初始答案：单阶段策略（存储1次，增加n次）
    ans=a+n*b;
    // 枚举阶段数k（从2到60）
    // 60是上限因为2^60 ≈ 1.15e18 > 1e18
    for(imx k=2;k<=60;k++){
        // 二分查找：找到最大的base使得base^k ≤ n+1
        l=1,r=n+1,now=1;
        while(l<=r){
            imx mid=(l+r)/2;
            if(spw(mid,k)<=n+1)
                now=mid,l=mid+1;
            else r=mid-1;
        }
        // 尝试不同的因子组合：now和now+1
        for(imx i=0;i<=k;i++){
            imx p1=spw(now,k-i);   // now^(k-i)
            imx p2=spw(now+1,i);   // (now+1)^i
            // 检查乘积是否满足条件
            if(p1>n||p2>n){
                // 单个因子已超过n
                imx t=now*(k-i)+(now+1)*i;  // 因子和
                ans=min(ans,k*a+(t-k)*b);   // 总时间
                break;
            }
            else{
                // 检查乘积是否会溢出或满足条件
                if(p2>0&&p1>(n+1)/p2){
                    imx t=now*(k-i)+(now+1)*i;
                    ans=min(ans,k*a+(t-k)*b);
                    break;
                }
                else if(p1*p2>=n+1){
                    // 乘积满足条件
                    imx t=now*(k-i)+(now+1)*i;
                    ans=min(ans,k*a+(t-k)*b);
                    break;
                }
            }
        }
    }
    iprint(ans);
    return 0;
}

关键