题目描述
四平方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多 4个正整数的平方和。
如果把 0包括进去,就正好可以表示为 4个数的平方和。
比如:
5=02+02+12+22
7=12+12+12+22
对于一个给定的正整数,可能存在多种平方和的表示法。要求你对 4
个数排序:
0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d
为联合主键升序排列,最后输出第一个表示法。
输入格式
输入一个正整数 N
输出格式
输出4个非负整数,按从小到大排序,中间用空格分开。
数据范围
0<N<5∗106
样例
输入样例:
5
输出样例:
0 0 1 2
算法1
暴力(O(N的3次方))
一般对于C++里面的代码,1s也就运行10的8次方次,这个题的最大取到10的6次方,开方10的3次方,N的3次方,大概10的9次方的运算次数,肯定会超时,视频里暴力可以过因为数据弱,本题数据加强了,现在过不了了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int main(int argc, char** argv) {
int n;
cin>>n;
for(int a=0;a*a<=n;a++){
for(int b=a;a*a+b*b<=n;b++){
for(int c=b;a*a+b*b+c*c<=n;c++){
int t=n-a*a-b*b-c*c;
int d=sqrt(t);
if(d*d==t){
printf("%d %d %d %d\n",a,b,c,d);
return 0;
}
}
}
}
return 0;
}
算法2(二分)O(n的平方logn)
遍历3次肯定是过不了,所以遍历两次,先双层遍历c,d;用结构体将cc+dd,c,d存起来,然后再来一个双层遍历,遍历a,b,在那个结构体里面是否存在n-aa-bb,若存在则选择字典序最小的那个,查询的时候 可以用二分,所以要对结构体里的cc+dd进行排序,然后c,d又要按照字典序,所要重载<,因为a,b,c,d是升序,所以要先遍历c,d,存起来cc+dd,c,d,再遍历a,b,在那个结构体里面是否存在n-aa-bb
趁着今天这个题我就把sort自定义排序,重载运算符学一下吧
重载运算符
bool operator<(const node &x) const{//x可以是任意名字,node是结构体的名字
//中间写排序规则
}
eg:
struct Sum{
int s,c,d;
bool operator<(const Sum &t) const{//重载<
if(s!=t.s) return s<t.s;
if(c!=t.c) return c<t.c;
return d<t.d;
}
}sum[2500010];
//这里是多关键字排序,s是第一关键字,c是第二关键字,d是第三关键字。具体比较规则按照代码的字面意思理解就行:如果s不同,则s小的元素小;否则如果s相同但c不同,则c较小的元素小,依次类推。
struct Sum{
int s,c,d;
bool operator<(const Sum &t) const{//重载<
if(s!=t.s) return s>t.s;//降序
if(c!=t.c) return c<t.c;//升序
return d<t.d;//升序
}
}sum[2500010];
自定义排序函数
struct Sum{
int s,c,d;
}sum[2500010];
bool cmp(Sum a,Sum b){//自定义函数排序,Sum是结构体名
if(a.s==b.s) return a.c<b.c;
if(a.c==b.c) return a.d<b.d;
return a.s<b.s;
}
sort(a,a+n);//默认下标0~n-1升序
sort(a+1,a+n+1);//默认下标1~n升序
sort(a,a+n,greater<int>());//降序
sort(a,a+n,cmp);//自定义函数排序,重写cmp
拓展一点结构体的知识://昨天不了一个天梯赛选拔赛的模拟题发现结构体都不会了,特意学了一下
第一种写法,带了typedef
typedef struct Node{ //typedef的出现是给结构体类型名Node,重新起个名字叫node,在后来你可以用node定义一个结构体变量名,你也可以用Node定义一个结构体变量名,你也可以在一个代码里混用Node/node来定义结构体变量名
int x;
int y;
} node;
node v[1005];
//只有这样才可以用v[i].x,v[i].y,
//不可以如下:
typedef struct node{ //node是结构体类型名
int x;
int y;
}v[1005];
bool cmp(node a, node b){
return a.x < b.y;
}
//这样的话它不认识v[i].x,v[i].y,
//上述代码这也可以这么写:
struct node{ //node是结构体类型名
int x;
int y;
};//先声明结构体类型
node v[1005];//再定义结构体变量名
bool cmp(node a, node b){
return a.x < b.y;
}
struct node{ //node是结构体类型名
int x;
int y;
}v[1005];
//可以用v[i].x,v[i].y,
bool cmp(node a, node b){
return a.x < b.y;
}
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct Sum{
int s,c,d;
bool operator<(const Sum &t) const{//重载<
if(s!=t.s) return s<t.s;
if(c!=t.c) return c<t.c;
return d<t.d;
}
}sum[2500010];
int main(int argc, char** argv) {
int n,m=0;
cin>>n;
for(int c=0;c*c<=n;c++){
for(int d=c;d*d+c*c<=n;d++){
sum[m++]={c*c+d*d,c,d};
}
}
sort(sum,sum+m);
for(int a=0;a*a<=n;a++){
for(int b=a;b*b+a*a<=n;b++){//b=a,因为输出a,b,c,d按照升序
int k=n-a*a-b*b;
int l=0,r=m-1;
while(l<r){ //二分模板
int mid=(l+r)/2;
if(sum[mid].s>=k) r=mid;
else l=mid+1;
}
if(sum[l].s==k){
printf("%d %d %d %d",a,b,sum[l].c,sum[l].d);
return 0;
}
}
}
return 0;
}
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct Sum{
int s,c,d;
}sum[2500010];
bool cmp(Sum a,Sum b){//自定义函数排序
if(a.s==b.s) return a.c<b.c;
if(a.c==b.c) return a.d<b.d;
return a.s<b.s;
}
int main(int argc, char** argv) {
int n,m=0;
cin>>n;
for(int c=0;c*c<=n;c++){
for(int d=c;d*d+c*c<=n;d++){
sum[m++]={c*c+d*d,c,d};
}
}
sort(sum,sum+m,cmp);
for(int a=0;a*a<=n;a++){
for(int b=a;b*b+a*a<=n;b++){//b=a,因为输出a,b,c,d按照升序
int k=n-a*a-b*b;
int l=0,r=m-1;
while(l<r){ //二分模板
int mid=(l+r)/2;
if(sum[mid].s>=k) r=mid;
else l=mid+1;
}
if(sum[l].s==k){
printf("%d %d %d %d",a,b,sum[l].c,sum[l].d);
return 0;
}
}
}
return 0;
}
哈希查找(O(n的平方))
加强数据这个也过不了了,哈希查找O(1),二分查找O(logn),哈希最快,但是这个题二分比哈希快,可能是数据集的问题吧,我也不是很清楚,有大佬可以解释解释哈
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
unordered_map<int,PII> s;
int main(int argc, char** argv) {
int n;
cin>>n;
for(int c=0;c*c<=n;c++){
for(int d=c;d*d+c*c<=n;d++){
int t=c*c+d*d;
if(s.count(t)==0) s[t]={c,d};
}
}
for(int a=0;a*a<=n;a++){
for(int b=a;b*b+a*a<=n;b++){//b=a,因为输出a,b,c,d按照升序
int t=n-a*a-b*b;
if(s.count(t)){
printf("%d %d %d %d",a,b,s[t].x,s[t].y);
return 0;
}
}
}
return 0;
}
运算符重载那里不理解,大神能不能解释一下,球球
我可以这样理解吗,重载运算符如果是 <,然后如果operator 里面 return >就是降序,<就是升序;如果是>,里面<是降序,>是升序;就是里外不一致是降序,一致是升序