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

· · 题解

思路

首先题目给了提示不要用 O(q\sqrt[3]{x}) 的算法通过但是我试了一遍只有30所以我们就不能暴力通过此题。

在题目输入中说到保证给出的 x_1 - x_q 是单调不减的，所以我们可以通过先前得到的答案来得到后面的答案，再看到样例1的解释,不难看出在一个完全立方数到了一个完全立方数的区间中，其立方根的值是相等的并且下一个不一样的立方根是递增的，而且区间大小为后一个完全立方数减去前一个完全立方数加一，所以我们就想到先打表完全立方数到容器a中然后枚举 x_l - x_r 之间经历了那些完全立方数的区间并用 i 来枚举当前区间的立方根值。

就可以得到一条式子 (i+1)\cdot(a[i+1]-a[i])，这可以快速的求出区间的和,用一个 ans 累加;然后再利用到前缀和的思想，加上上一个区间的和即 (i+1)\cdot(x-a[i]+1) 不加会少算一部分,那最后就可以完美通过了。

AC代码

#include<bits/stdc++.h>
#include<queue> 
#define int long long
#define l_queue priority_queue <int,vector<int>,greater<int> >
#define p_queue priority_queue <int>
inline void read(int & a){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}a=s*w;}
void write(int x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');}
using namespace std;
vector<int> a;
void init(){
    for(int i=1;i<=1e4;i++){//1e4^3就是1e12
        a.push_back(i*i*i);
    }
}
int ans,i;//i的值不用每一次更新，前缀和的思想就在这 
signed main(){//偷懒用define不要忘记改signed 
    init();//预处理 
    int q;
    read(q);
    for(int j=1;j<=q;j++){
        int x;
        read(x); 
        for(;i<a.size()-1&&a[i+1]<=x;i++){
            ans+=(i+1)*(a[i+1]-a[i]);
        }
        write(ans+(i+1)*(x-a[i]+1));
        puts("");
    }
    return 0;
}