题目描述
题意是要求四个整数的平方和等于给定的n,a<b<c<d;这四个数可以为0
单纯的暴力枚举时间复杂度为3个根号n相乘就会超时,通过思考可以转换成2个n的时间复杂度
先枚举后两个c d平方和,再枚举前两个a,b的平方和;
枚举过程中本身就是字典序,只要两组平方和匹配的第一组数就是所求答案
匹配有两种方法二分和哈希
方法一使用哈希的话时间复杂度为O1,在枚举ab的过程中查找判断输出
方法二将cd平方和储存在数组中,在枚举ab的过程中使用二分查找进行匹配
代码如下
样例
哈希
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5e6+6;
int C[N],D[N];
int n;
int main()
{
scanf("%d",&n);
memset(C,-1,sizeof C);
for(int c=0;c*c<=n;c++)
for(int d=c;d*d+c*c<=n;d++)
{
int s=c*c+d*d;
if(C[s]==-1)C[s]=c,D[s]=d;
}
for(int a=0;a*a<=n;a++)
for(int b=a;b*b+a*a<=n;b++)
{
int s=n-a*a-b*b;
if(C[s]!=-1)
{ printf("%d %d %d %d\n",a,b,C[s],D[s]);
return 0;
}
}
return 0;
}
二分
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5e6+6;
struct sum
{
int s,c,d;
bool operator<(const sum & tt)const
{
if(tt.s!=s)return s<tt.s;
if(tt.c!=c)return c<tt.c;
return d<tt.d;
}
}sums[N];
int n;
int main()
{
scanf("%d",&n);
int k=0;
for(int c=0;c*c<=n;c++)
for(int d=c;d*d+c*c<=n;d++)
sums[k++]={c*c+d*d,c,d};
sort(sums,sums+k);
for(int a=0;a*a<=n;a++)
for(int b=a;a*a+b*b<=n;b++)
{
int ss=n-a*a-b*b;
int l=0,r=k;
while(l<r)
{
int mid=l+r>>1;
if(sums[mid].s>=ss)r=mid;
else l=mid+1;
}
if(sums[l].s==ss)
{
printf("%d %d %d %d\n",a,b,sums[l].c,sums[l].d);
return 0;
}
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考y总
C++ 代码
blablabla