本文共 2727 字，大约阅读时间需要 9 分钟。

“飞雪连天射白鹿，笑书神侠倚碧鸳”。作为一名碧血丹心的大侠，山山时常在江湖之上行侠仗义，惩恶扬善，而且江湖素有“神雕大侠杨过，走遍江南名扬天下；逍遥神侠山山，踏尽漠北誉满江湖”。可是，又有谁知道，山山能有如今的成就，全都源起他幼年时的一次奇遇。 二十年前，还是孩童的山山正与村中几位玩伴嬉戏玩耍。正当他们玩得尽兴之时，忽然一位过路的乞丐叫住了山山。 乞丐说道：“小朋友，我看你灵智已开，颇具慧根，如果你能解读我这秘籍上的神秘语言，我将教你一门绝世武功”。 其他几个小朋友一看到瘦骨嶙峋、灰头土脸的乞丐，全都吓坏了，赶忙哭喊着逃回了家，而山山却毫无惧意，说道：“让我看看！”。 乞丐笑了笑，拿出了秘籍。山山接过秘籍，发现上面写着：“求有多少a, b, c, d满足a3=b3+c3+d3，其中a, b, c, d满足1 <= a, b, c, d <= n，且都是正整数”。 山山看完之后，忽然好像被雷击了一般，不假思索，想都不带想的说出了答案。乞丐一时傻了眼，但是看山山一脸认真的模样，又觉得他不像在撒谎，叹了一口气说道：“果然，你才是天选之人，这本《图灵圈》你拿去吧，上面记录了江湖上所有的绝世武功，你勤加修炼，定能成为旷世大侠的”，说罢，乞丐缓缓转身离去。 山山一脸不解地看着乞丐离开的背影，心里却被秘籍上的武功所吸引。于是，山山把秘籍藏在了后山之上，每天晚上偷偷去练习信息学竞赛。后来，就有了山山行走江湖的故事了。后世之人都对秘籍上所写的神秘语言感兴趣，这也引发了全民参与到这个问题的解读过程中，久而久之，就有了信息学竞赛(Doge)。 （以上故事纯属虚构，如有雷同，纯属虚构）

输入格式:

一个正整数n，含义见题目描述

n <= 100（简单）

n<=1000（困难） 

输出格式:

一个正整数表示答案

限制:

空间限制：512MByte

时间限制：1秒（简单and困难）

时间限制：0.25秒（毒瘤）

样例:

输入：

10

输出：

12

既然是a^3=b^3+c^3+d^3，所以理所当然的四重循环：

#include
   
    using namespace std;int main(){	int n,sum=0;	cin>>n;	for(int a=1;a<=n;a++){		for(int b=1;b<=n;b++){			for(int c=1;c<=n;c++){				for(int d=1;d<=n;d++){					if((a*a*a)==(b*b*b)+(c*c*c)+(d*d*d)){						sum++;					}				}			}		}	}	cout<
   

但这样肯定过不了，时间复杂度已经是O(n^4),肯定会超时。

那怎么办呢？预处理：

#include
   
    using namespace std;const int N = 1e6+100;int sum[N];int main() {	for(int i=1; i<=100; i++) {		sum[i] = i*i*i;	}	int n,ans=0;	cin>>n;	for(int a=1; a<=n; a++) {		for(int b=1; b<=n; b++) {			for(int c=1; c<=n;c++) {				for(int d=1; d<=n; d++) {					if(sum[a]==sum[b]+sum[c]+sum[d]) {						ans++;					}				}			}		}	}	cout<
   

虽然还是O(n^4)，但100是没问题的，简单版也过了。

我们看看a^3=b^3+c^3+d^3这个式子，它可以进行一些变形，将b^3移过去，就变成了a^3-b^3=c^3+d^3，瞬间变成O(n^2)。

#include
   
    #include
    
   

但还不够，map虽然方便，但方便的东西是有代价的（此处引用张学长的名言），map的复杂度是

O(logn)的，这说明这个代码复杂度实际上是O(n^2logn)的。

按理说问题也不大，可恰恰这里出了问题。

没错，过不了（我们的张学长卡的太死）

那咋办，别慌，不用map的来了：

#include
   
    #include
    
   

到这，困难版总算过了，至于毒瘤版。。。

我也不会，你们自己做吧

转载地址：https://blog.csdn.net/jhfhfhu/article/details/119038654 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！