题目解析：

对于该题目是蓝桥杯第七届的赛题，但是我思考了一会并没有思路，真的很菜，但是这题的做法很多.

1. 最暴力的方法是三层循环即代码1，数据加强后现在已经过不了了，时间复杂度位O(n^3)；

2. 第二种方法是使用哈希表，因为哈希表时间查找位O(1)所以总的时间复杂度位O(n)，但是数据加强后这个也过不了了，这里不懂为什么，明明哈希的时间效率很高？？，代码2；

3. 第三种做法是二分，这种方法我自己可能想不到，因为自己对二分应该还比较陌生，二分的作用和哈希表一样目的是找值，通过不断的减少R-l的值无限逼近正确值，这里注意值的取值范围是[l,r]这里是闭区间，数据加强后，二分可以过，二分的时间复杂度位O(logn),本题中时间复杂度位O(nlogn),不懂为什么二分能过但是哈希不能？？，代码3；

4. 第四种方法是开两个数组，应该就是y总的空间换时间，这个时间复杂度确实很低O(n),所以他可以过，代码4。

以上四种代码，除了二分是对数据全部存入并进行排序，其他做法是只存储cc+dd第一次出现的c,d，这时候c一定是最小的值，根据题意，字典键值，就是先看a,再看b,在看c,只有前边的数据都相等才看c!!!但是我第一次审题时，并不会，甚至可以说我都不明白题意啥意思，真的是做题做少了，对于该题我应该先分析时间复杂度，在进行问题的分析，解决。

代码1,虽然超时，但是思路我得借鉴：

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e7;
int main(){
    int n;
    cin>>n;
    for(int a=0;a*a<=n;a++){
        for(int b=a;b*b+a*a<=n;b++){
            for(int c=b;c*c+b*b+a*a<=n;c++){
                int p=n-a*a-b*b-c*c;
                int k=sqrt(p);     //我个笨蛋这里不会！！！，现在已经明白了
                if(a*a+b*b+c*c+k*k==n){
                    cout<<a<<' '<<b<<' '<<c<<' '<<k<<endl;
                    return 0;
                }
            }
        }
    }
}

代码2,虽然超时，但是思路我得借鉴：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e7;
int main(){

    int n;
    cin>>n;
unordered_map<int,int>res;
for(int i=0;i*i<=n;i++){
    for(int j=i;j*j+i*i<=n;j++){
        if(res.find(i*i+j*j)==res.end()){
            res[i*i+j*j]=i;
        }
    }
}
for(int a=0;a*a<=n;a++){
    for(int b=a;b*b+a*a<=n;b++){
        if(res.find(n-a*a-b*b)!=res.end()){
            int c=res[n-a*a-b*b];

            int d=sqrt(n-a*a-b*b-c*c);

                cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
                return 0;
            }
        }
    }

return 0;
}

代码3：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e7;
struct Sum{
    int s,c,d;
    bool operator<(const Sum&sum)const{
        if(s!=sum.s)
        return s<sum.s;//后序需要进行二分，二分要求数据升序排列
        if(c!=sum.c)
        return c<sum.c;//这两部实现字典序，即同一s，在数组中按照c大小进行排序，如果c大小相同就按照d大小排序
        if(d!=sum.d)
        return d<sum.d;
    }
}sum[N];
int m=0;
int n;
int main(){

    cin>>n;

    for(int c=0;c*c<=n;c++){
        for(int d=c;d*d+c*c<=n;d++){//等于号'='一定不能忘，刚开始就因为这个等于号一直除bug，因为这四个数中可以有0.所以一定要枚举到sqrt(n)
            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++){
            int l=0;
            int r=m-1;
            while(l<r){
                int mid=(l+r)/2;
                if(sum[mid].s>=n-a*a-b*b){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            if(sum[l].s==n-a*a-b*b){
                cout<<a<<' '<<b<<' '<<sum[l].c<<' '<<sum[l].d<<endl;
                return 0;
            }
        }
    }
    return 0;

}

代码4,这里我必须要明白C,D两个数组是靠什么连接在一起，并且查询的时间复杂度位O(1)：

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e7;
int C[N];
int D[N];
int main(){

    int n;
    cin>>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 p=c*c+d*d;
            if(C[p]==-1){//只保存第一次出现p的c,d因为这时候的c更小，且d>c所以这一组一定是符合要求的
                C[p]=c;
                D[p]=d;
            }
        }
    }
    for(int a=0;a*a<=n;a++){
        for(int b=a;b*b+a*a<=n;b++){
            int q=n-a*a-b*b;
            if(C[q]!=-1){
                cout<<a<<' '<<b<<' '<<C[q]<<' '<<D[q]<<endl;
                return 0;
            }
        }
    }
}