自动搬运

查看原文

来自洛谷，原作者为

	abc1856896 谦虚谨慎，砥砺前行。

搬运于2025-08-24 22:57:20，当前版本为作者最后更新于2024-04-25 14:00:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意

给定 $t$ 个 $x_i$，输出：

$$\sum _{j=1} ^{x_i} \lfloor j^{\frac{1}{3}} \rfloor $$

$x_i$ 满足单调递增。

错误解法

我们可以先预处理出完全立方数，再每次从 $\bm 1$ 开始计算即可。

代码

#include <bits/stdc++.h>
#define int long long 
#define mod 998244353
#define MAX_X 10000
using namespace std;
int a [MAX_X+5] ;
void init () {
	for ( int i = 1 ; i <= 10000 ; i++) {
		a [i] = ( i * i * i ); 
	}
	return ; 
}
void solve () {
	int x ;
	cin >> x;
	int ans=0,i=1;
	for ( ; i <= 10000 ; i++){
		if( a[i] > x) {
			break ;
		}
		ans += ( a[i] - a[ i - 1] ) * (i - 1);
	}
	cout << ans + (i - 1) * (x - a [i - 1] + 1) << "\n" ;
}
signed main () {
	init () ;
	int T;
	cin >> T ;
	while( T-- ){
		solve() ;
	}
	return  0 ;
}

这份代码的时间复杂度为 ${O(q\sqrt[3]{x})}$，只能拿 $70$ 分。

正解

考虑优化。从上面的代码我们可以知道超时的原因是每次从 $\bm 1$ 开始枚举。而结合题目我们可以知道 $x_i$ 单调递增。所以我们可以从上一次的 $p$ 开始枚举即可。

代码

#include <bits/stdc++.h>
#define int long long 
#define mod 998244353
#define MAX_X 10000
using namespace std;
int a [MAX_X+5] ;
void init () {
	for ( int i = 1 ; i <= 10000 ; i++) {
		a [i] = ( i * i * i ); 
	}
	return ; 
}
int i = 1 , ans = 0;
void solve () {
	int x ;
	cin >> x;
	for ( ; i <= 10000 ; i++){
		if( a[i] > x) {
			break ;
		}
		ans += ( a[i] - a[ i - 1] ) * (i - 1);
	}
	cout << ans + (i - 1) * (x - a [i - 1] + 1) << "\n" ;
}
signed main () {
	init () ;
	int T;
	cin >> T ;
	while( T-- ){
		solve() ;
	}
	return  0 ;
}

增加了这个优化的效率非常高，每个测试点都在 $191ms$ 内解决。