题解：P10373 [AHOI2024 初中组] 立方根

xiezheyuan · 2024-04-23 13:25:47 · 题解

首先发现，f(x)=\lfloor x^{\frac{1}{3}}\rfloor 一定是呈块状分布的。

因此我们可以找出来每一个块的开始。设 t_i 表示第一个 y，满足 f(y)=i。那么 t_i 可以直接预处理。

然后我们再处理一个 a_i 表示 1\sim t_i-1 的答案，这个东西也可以预处理。预处理方法是递推，考虑新增块的贡献。

然后我们考虑如何回答询问，我们可以二分，找出询问的 x 所在块的位置，则前面若干个整块的答案我们通过 a_i 来求，末尾散块的答案直接乘就好了。

时间复杂度为 O(n^{\frac{1}{3}}+q\log n)，可以通过本题。

我没有用到 x 递增这一条件。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e4 + 5;
int tab[N], ans[N], q;

signed main(){
    cin>>q;
    for(int i=1;i<=10000;i++) tab[i] = i * i * i;
    for(int i=1;i<=10000;i++) ans[i] = ans[i - 1] + (i - 1) * (tab[i] - tab[i - 1]);
    while(q--){
        int n;cin>>n;
        int pos = upper_bound(tab + 1, tab + 10000 + 1, n) - tab;
        cout << (ans[pos - 1] + (pos - 1) * (n - tab[pos - 1] + 1)) << '\n';
    }
    return 0;
}