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

cmask4869 · 2024-04-24 14:41:58 · 题解

思路

这道题是一道数学题，可以简单写为：

如果正常暴力做的话算一下，应该只能得 20pts，所以思考一下其他方法，通过背的立方数公式，可以得出以下规律：

• 因为 x 一定为正整数，所以不考虑 1^3 的情况。
• 当 x<2^3(8)，前面的所有（至上一次判断）正整数的答案都为 1。
• 当 x<3^3(27)，前面的所有（至上一次判断）正整数的答案都为 2。

得出结论，x \le n^3 时，前面的所有（至上一次判断）正整数的答案为 n-1。

而数据保证，n \le 10^{12}，而 \sqrt [3]{10^{12}} 的数值只有 10000，完全可以用打表的方式提前将 n^3(n \le 10000) 的数全部计算出来，于是打出一个这样的表。

之后分层进行判断，得出这样的程序：

for ( ; i<10000 ; i++){
    if (n>=a[i+1]){
        ans+=(i+1)*(a[i+1]-a[i]) ;
    }
    else{
        ans+=(n-a[i]+1)*(i+1) ;
        break ;
    }
}

但是同时要注意到数据组数 q \le 2 \times 10^5，这样的程序只能得到 60pts，所以考虑优化。

这里发现了一个问题，题目告诉我们 n 一定是升序排序的，这个条件并没有用到，再想到比较大的 n 会有较多的重复计算的次数，于是 dp 的思想符合了，我们可以利用 dp 将前一个的状态进行记忆化。但是同样遇到了一个问题，使用的程序在最后一步要有一个特判（已少于下一次递归的 n^3），然后把状态提前到每次可能是重复运算的式子。

其中 dp 是用来存储上一次的数值，而 cdp 是存上一次计算到哪里了，从而更方便地进行下一次循环。另外，我们还需考虑 for 循环所带来的次数的多次累计，但是同样后面还有一层特判，最后在下一次用的地方对 cdp+1 就可以解决这个问题。