(二分)(结构体)(多关键字排序)1221. 四平方和

简介: (二分)(结构体)(多关键字排序)1221. 四平方和

题目链接

1221. 四平方和 - AcWing题库


一些话

切入点

// 如果把 0包括进去,就正好可以表示为 4个数的平方和。

// 要求你对 4个数排序:0≤a≤b≤c≤d

//并对所有的可能表示法按  a,b,c,d为联合主键升序排列最后输出第一个表示法。

//0<N<5∗106,


// 输出满足性质的情况,这符合枚举的前提条件,

// 只看范围枚举可能超时,但实际上因为是算平方和还有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<N<5∗106,
// 只看范围枚举可能超时,但实际上因为是算平方和还有0≤a≤b≤c≤d这个条件,枚举的情况有很多可以被剪去,实际的时间
// 是可以支持三重暴力枚举的(也可能是数据太弱了)
// 选择暴力还是有不小的风险,此题最保险的做法是用二分
// 先枚举两个字母得到平方和,把结果存起来(平方和与字母)按平方和-》c -》d的顺序排序后,再枚举另外两个字母,
// 用n减去这个平方和,然后二分查找结构体里有没有存和这个结果相同的数据,有的话就缩小右边界,找到最左的下标.
//最后输出当前枚举的a,b,和下标对应的结构体里存的c,d
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
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;
            }
        }
    }
}
目录
相关文章
|
6月前
【每日一题Day163】LC2367算术三元组的数目 | 二分查找 哈希表
【每日一题Day163】LC2367算术三元组的数目 | 二分查找 哈希表
29 0
|
5月前
|
移动开发 C++
【洛谷 P1157】组合的输出 题解(深度优先搜索+枚举子集)
该问题要求编程输出从1到n中选择r个元素的所有组合,组合按字典序排列。输入包含两自然数n和r(1&lt;n&lt;21, 0≤r≤n)。输出每个组合时,每个数字占据3个字符宽度。提供的AC代码使用C++,通过递归搜索方法枚举子集。样例输入为5 3,输出显示所有3个元素的组合。
45 0
|
6月前
|
C语言
c语言编程练习题:7-51 求奇数分之一序列前N项和
c语言编程练习题:7-51 求奇数分之一序列前N项和
66 0
|
6月前
|
算法 测试技术 C#
【线段树 区间位运算模板】3117划分数组得到最小的值之和
【线段树 区间位运算模板】3117划分数组得到最小的值之和
|
6月前
|
算法 测试技术 C#
【数学 排列组合】1643. 第 K 条最小指令
【数学 排列组合】1643. 第 K 条最小指令
【Leetcode -643.子数组最大平均值Ⅰ -645.错误的集合】
【Leetcode -643.子数组最大平均值Ⅰ -645.错误的集合】
51 0
|
人工智能 BI 索引
【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】
【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】
43 0
|
C语言
C语言:分数序列求和
题目:有一个分数序列:2/1 + 3/2 + 5/3 + 8/5 +...,求出这个数列的前 20 项之和。 背景:无。 思路:采用 for 循环,利用数学知识 分子:第 n 项 = 第 n - 1 项 + 第 n - 2 项。 分母:第 n 项 = 第 n - 1 项 + 第 n - 2 项。
238 0
(枚举)(模拟)(前缀和)(数组模拟哈希)(可二分)1236. 递增三元组
(枚举)(模拟)(前缀和)(数组模拟哈希)(可二分)1236. 递增三元组
66 0
|
人工智能
(数论)(枚举)(前缀和)1230. K倍区间
(数论)(枚举)(前缀和)1230. K倍区间
87 0