四平方和题解(二分习题)

四平方和

在这里插入图片描述

暴力做法

Y总暴力做法，蓝桥云里能通过所有数据

总结：暴力也分好坏，下面这份代码就是写的好的暴力
如何写好暴力:1. 按组合枚举 2. 写好循环结束条件，没必要循环那么多次

#include<iostream>
#include<cmath>using namespace std;int n;int main(){std::ios::sync_with_stdio(false);cin.tie(0);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){cout<<a<<" "<<b<<" "<<c<<" "<<d<<" ";return 0;}}return 0;
}

我自己写的暴力做法，只能过87.5% o(╥﹏╥)o

#include<iostream>
#include<cmath>using namespace std;int n;int main(){std::ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(int a=0;a*a<=n;a++)for(int b=0;b*b<=n;b++)for(int c=0;c*c<=n;c++)for(int d=0;d*d<=n;d++){if(a*a+b*b+c*c+d*d==n){cout<<a<<" "<<b<<" "<<c<<" "<<d;return 0;}}return 0;
}

分析

参考题解

这道题目最重要的思路是空间换时间（这是算法竞赛里一个非常重要的思想！！！）
本来，我们需要枚举 a b c d 四个数字，因为第四个数字可以计算出来，所以至少需要三重循环，即 O(n3)，但是这肯定是要超时的，所以就想办法优化循环的次数

重点来了:
一个比较好的思路是把三重循环拆成两次二重循环。在第一次二重循环中，计算一下c^2+d^2,然后记录下来，在第二次对a和b的循环中可以直接使用，而不需要再次计算。如此一来，时间复杂度就被大大的简化了。

至于如何记录 c^2+d^2 ，则可以考虑使用哈希表，或者数组+二分的做法。不得不说，实在是太巧妙了！！

二分做法

//四平方和
//二分
#include<bits/stdc++.h>using namespace std;const int N = 5e6 + 10;struct Sum{int s, c, d;// 下面这个重载用来解决按字典序输出的问题// 首先根据 c*c+d*d排序，为什么按c*c+d*d排序呢？// 因为我们的c是从小到大枚举，d从c开始枚举；也就是说我们的c和d是按字典序枚举的// 所以c*c+d*d中的c和d一定是符合字典序的// 如果c*c+d*d相同，那么就比较c；如果c*c+d*d和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;}
}record[N * 2];int n;int main()
{cin >> n;int k = 0;// 用来记录结构体数组里的元素个数(也就是说record里有多少个元素)// 预处理(其实就是打表)for(int c = 0; c * c <= n; c++){for(int d = c; c * c + d * d <= n; d ++){record[k++] = {c * c + d * d, c, d};}}// 排序sort(record, record + k);for(int a = 0; a * a <= n; a ++){for(int b = a; a * a + b * b <= n; b++){int t = n - a * a - b * b;// k表示record里的元素个数int l = 0, r = k - 1;while(l < r){int mid = l + r >> 1;if(record[mid].s >= t) r = mid;else l = mid + 1;}if(record[l].s == t){printf("%d %d %d %d\n", a, b, record[l].c, record[l].d);return 0;}}}return 0;
}

哈希做法

使用C++自带的unordered_map过不了，不过模拟哈希表却可以过。

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;// 开放地址法的N一般为原先的两倍，在本题应该为2*5e6
// 但这里我怕爆内存，只好跟原来一样了；
// 注意N得为质数,5e6的质数为5e6+11
/* 求质数的代码：for(int i=5e6;;i++){bool flag=true;for(int j=2;j*j<=i;j++){if(i%j==0){flag=false;break;}if(flag){cout<<i<<endl;break;}}}*/
const int N=5e6+11,null=0x3f3f3f3f;int h[N];typedef pair<int,int> PII;PII s[N];int n;int find(int x){int k=(x%N+N)%N;while(h[k]!=null&&h[k]!=x){k++;}return k;}int main(){cin>>n;memset(h,null,sizeof h);// 打表for(int c=0;c*c<=n;c++)for(int d=c;c*c+d*d<=n;d++){int k=find(c*c+d*d);if(h[k]==null) {h[k]=c*c+d*d;s[k].first=c,s[k].second=d;}}for(int a=0;a*a<=n;a++)for(int b=a;a*a+b*b<=n;b++){int t=n-a*a-b*b;int k=find(t);if(h[k]!=null){cout<<a<<" "<<b<<" "<<s[k].first<<" "<<s[k].second;return 0;}}return 0;
}