题解：CF2048F Kevin and Math Class

· · 题解

题意

Kevin 在数学课上遇到了一个有趣的问题：黑板上有两行数字 a 和 b，每次操作可以选择一个区间 [l, r]，计算 b_l 到 b_r 中的最小值 x，然后将区间内每个 a_i 替换为 \lceil \frac{a_i}{x} \rceil（向上取整）。Kevin 想知道最少需要多少次操作，才能让所有 a_i 都变成 1。

分析

发现每次操作实际上是用区间内 b 的最小值 x 对 a 进行"集体除法"。由于 x \geq 2，所以最多 63 次操作。

有一个神秘的东西，\lceil \lceil x /a \rceil /b \rceil=\lceil \lceil x /b \rceil /a \rceil，有兴趣的同学可以研究证明。

我们可以构建一棵从小的数到大的数的笛卡尔树，发现每个节点代表的区间就是以这个数为最小值的最优区间，考虑用树形动态规划解决。

状态

设 dp_{i,j} 表示以位置 i 为根的子树，经过 j 次操作后，区间最小的最大值。

转移：

  1. 叶子节点：没有子节点，只能对自己的 a_i 进行操作：

    • dp_{i,0} = a_i

  2. 单子树节点：只有一个子节点，需要同时考虑自己和孩子：

    • dp_{i,0} = \max(a_i, dp_{son,0})
    • dp_{i,k} = \min(\max(a_i, dp_{son,k}), \lceil dp_{i,k-1} / b_i \rceil)

  3. 双子树节点：有两个子节点，需要合并左右子树的操作：

    • dp_{i,0} = \max(a_i, dp_{ls,0}, dp_{rs,0})
    • dp_{i,k} = \min\left(\lceil dp_{i,k-1} / b_i \rceil, \min_{0 \leq j \leq k} \max(a_i, dp_{ls,j}, dp_{rs,k-j})\right)

总复杂度：O(n \log n + nM^2)，可以通过此题。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,M=70;  // M=70足够，因为2^60>10^18

int n;
int a[N],b[N];

// RMQ结构体，用于查询区间最小值位置
struct RMQ{
    pair<int,int> dp[N][22];  // 存储(值,位置)

    void RMQ_init(int m,int a[]){
        for(int i=1;i<=m;i++)
            dp[i][0]={a[i],i};
        for(int j=1;j<=20;j++)
            for(int i=1;i+(1<<j)-1<=m;i++)
                dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
    }

    int Min(int l,int r){
        int lg=__lg(r-l+1);
        return min(dp[l][lg],dp[r-(1<<lg)+1][lg]).second;
    }
}st;

int dp[N][M];  // dp[i][j]:以i为根的子树，j次操作后a[i]的最小值

// 向上取整除法
int ceil_div(int x,int y){return (x+y-1)/y;}

// 递归构建树并计算DP值
int build_tree(int l,int r){
    if(r<l) return 0;  // 空区间

    // 找到当前区间b的最小值位置
    int x=st.Min(l,r);

    // 递归处理左右子树
    int ls=build_tree(l,x-1);
    int rs=build_tree(x+1,r);

    // 初始化dp[x][0]
    dp[x][0]=a[x];

    // 情况1：叶子节点
    if(ls+rs==0){
        for(int i=1;i<M;i++)
            dp[x][i]=ceil_div(dp[x][i-1],b[x]);
        return x;
    }

    // 情况2：只有一个子节点
    if(ls*rs==0){
        int son=(ls?ls:rs);
        dp[x][0]=max(dp[son][0],dp[x][0]);
        for(int i=1;i<M;i++)
            dp[x][i]=min(max(dp[son][i],a[x]),ceil_div(dp[x][i-1],b[x]));
        return x;
    }

    // 情况3：有两个子节点
    dp[x][0]=max({dp[x][0],dp[ls][0],dp[rs][0]});
    for(int i=0;i<M;i++){
        if(i) dp[x][i]=ceil_div(dp[x][i-1],b[x]);
        // 枚举分配给左右子树的操作次数
        for(int j=0;j<=i;j++)
            dp[x][i]=min(dp[x][i],max({dp[ls][j],dp[rs][i-j],a[x]}));
    }
    return x;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    // 初始化dp数组
    for(int i=1;i<=n;i++)
        for(int j=0;j<M;j++)
            dp[i][j]=1e18;

    // 预处理RMQ
    st.RMQ_init(n,b);

    // 构建树并计算DP
    int root=build_tree(1,n);

    // 找到最小的操作次数使所有数变为1
    for(int i=0;i<M;i++)
        if(dp[root][i]==1){
            cout<<i<<"\n";
            return;
        }
}

void clear(){
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T; cin>>T;
    while(T--){
        solve();
        clear();
    }
    return 0;
}