专栏首页奇妙的算法世界第七届蓝桥杯省赛C++A/B组 四平方和

第七届蓝桥杯省赛C++A/B组 四平方和

题意描述

题目链接

思路

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=5*1e6+10;
struct sum{
    int c,d,s;
    bool operator<(const sum &W)const{
        if(s!=W.s) return s<W.s;
        if(c!=W.c) return c<W.c;
        return d<W.d;
    }
}Sum[N];
int main(){
    int n;scanf("%d",&n);
    int idx=0;
    for(int i=0;i*i<=n;i++){
        for(int j=i;j*j+i*i<=n;j++){
            Sum[idx++]={i,j,i*i+j*j};
        }
    }
    sort(Sum,Sum+idx);
    for(int i=0;i*i<=n;i++){
        for(int j=i;j*j+i*i<=n;j++){
            int l=0,r=idx;
            while(l<r){
                int mid=l+r>>1;
                int x=Sum[mid].c,y=Sum[mid].d;
                if(x*x+y*y+i*i+j*j>=n) r=mid;
                else l=mid+1;
            }
            int x=Sum[l].c,y=Sum[l].d;
            if(x*x+y*y+i*i+j*j==n){
                printf("%d %d %d %d\n",i,j,x,y);
                return 0;
            }
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • codeforces 722C(带权并查集+反向思维)

    You are given an array consisting of n non-negative integers a 1, a 2, …, a n.

    dejavu1zz
  • SCU2511(单调栈)

    我们维护一个单调递减栈,使用一个数组来记录第i只牛所能听到的噪音,最后求最大值即可

    dejavu1zz
  • HDU3410(单调栈)

    由于题目的数据范围较大,所以我们不能用暴力解法,可以考虑维护一个递减单调栈,可以使用两遍单调栈,先从左到右维护,然后再从右到左维护一遍。我们可以先用一个变量来记...

    dejavu1zz
  • ​LeetCode刷题实战69:x 的平方根

    https://blog.csdn.net/qq_41231926/article/details/82861877

    程序IT圈
  • BZOJ 1083: [SCOI2005]繁忙的都市【Kruscal最小生成树裸题】

    1083: [SCOI2005]繁忙的都市 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2925  Sol...

    Angel_Kitty
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • 【 HDU - 4456 】Crowd (二维树状数组、cdq分治)

    给你一个n行n列的格子,一开始每个格子值都是0。有M个操作,p=1为第一种操作,给格子(x,y)增加z。p=2为询问与格子(x,y)的曼哈顿距离不超过z的格子值...

    饶文津
  • 剑指offer(01-15题)优化题解

    思路: 选定一个维度(行或列)先找到需要查找的元素所在的行(列),再从该行(列)找到该元素的该元素具体的列(行)位置。复杂度O(n)。

    bigsai
  • 懂二进制

    题目描述 世界上有10种人,一种懂二进制,一种不懂。那么你知道两个int32整数m和n的二进制表达,有多少个位(bit)不同么? 输入例子: 19...

    AI那点小事

扫码关注云+社区

领取腾讯云代金券