目录

题目链接

一些话

        切入点 

流程

套路

ac代码

题目链接

1221. 四平方和 - AcWing题库

一些话

啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～～数～啦！我草，又~在～水～字～数～啦！我草，

切入点 

// 如果把 0包括进去，就正好可以表示为 4个数的平方和。
// 要求你对 4个数排序：0≤a≤b≤c≤d
//并对所有的可能表示法按  a,b,c,d为联合主键升序排列最后输出第一个表示法。
//0

// 输出满足性质的情况，这符合枚举的前提条件，
// 只看范围枚举可能超时，但实际上因为是算平方和还有0≤a≤b≤c≤d这个条件，枚举的情况有很多可以被剪去，实际的时间
// 是可以支持三重暴力枚举的（也可能是数据太弱了）

// 选择暴力还是有不小的风险，此题最保险的做法是用二分

流程

// 先枚举c,d得到平方和，把结果存起来（平方和与字母）(也可以枚举a，b）（但后面的c，d枚举要稍微修改）

三元组且要排序，就很容易想到用结构体存

重载>运算符，按平方和->c ->d的顺序排序后，再枚举另外两个字母，
// 用n减去这个平方和,然后二分查找结构体里有没有存和这个结果相同的数据，有的话就缩小右边界，找到最左的下标.
//最后输出当前枚举的a，b，和下标对应的结构体里存的c，d

套路

结构体重载运算符实现多关键字排序

struct Sum{int s,c,d;bool operator<(Sum & t){if(s != t.s) return s < t.s;if(c != t.c) return c < t.c;return d < t.d;}
}sum[N];

ac代码

// 14:35-15:53wa// 16：14~29ac// 16:30 ~ 16:40ac
// 如果把 0包括进去，就正好可以表示为 4个数的平方和。
// 要求你对 4个数排序：0≤a≤b≤c≤d
//并对所有的可能表示法按  a,b,c,d为联合主键升序排列最后输出第一个表示法。// 输出满足性质的情况，这符合枚举的前提条件，0
#include 
#include 
#include 
using namespace std;
const int N = 5e6 + 10;
struct Sum{int s,c,d;bool operator<(Sum & t){if(s != t.s) return s < t.s;if(c != t.c) return c < t.c;return d < t.d;}
}sum[N];
int main(){int n,k = 0;cin >> n;for(int c = 0;c * c <= n;c++){for(int d = c;d * d + c * c <= n;d++){sum[k++] = {c * c + d * d,c,d};}}sort(sum,sum+k);for(int a = 0;a * a <= n;a++){for(int b = a;b * b + a * a <= n;b++){int t = n - a * a - b * b;int l = 0,r = k;while(l < r){int mid = l + r >> 1;if(sum[mid].s >= t) r = mid;else l = mid + 1;}if(sum[l].s == t){cout << a << " " << b << " " << sum[l].c << " " << sum[l].d << endl;return 0;}}}
}

我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在，又~在