草庐IT

四平方和（蓝桥杯C/C++B组真题详解）（三种做法）

CTGU-Yoghurt 2023-04-10 原文

目录

题目详细：​编辑

题目思路：

暴力：

代码详解：

哈希：

二分：

题目详细：

题目思路：

这个题目大家可能马上就可以想到暴力做

例如这样

暴力：

#include<iostream>
#include<cmath>
using namespace std;

int main(){
    int n;
    cin>>n;
    
    int t=sqrt(n)+1;
    for(int a=0;a<=t;a++)
        for(int b=a;a*a+b*b<=n;b++)
            for(int c=b;a*a+b*b+c*c<=n;c++){
                int d=n-a*a-b*b-c*c;
                int qd=sqrt(d);
                if(qd*qd==d){
                    printf("%d %d %d %d",a,b,c,qd);
                    return 0;
                }
                
            }
    return 0;
}

这样写的话

在题目不卡你数据的时候

可以通过题目

大部分的样例

但仍然不是很好的写法

（浅提一句：在比赛时如果时间不够就可以采用这种写法，以取得更高分数为目标）

那我们要怎么做这道题呢？

首先题目要求的是四个数的平方和

我们枚举每一个数的话一定会太慢

那么我就可以通过枚举两个数

先枚举c和d的所有情况并记录下来

然后再枚举a和b的所有情况

在枚举a和b的所有情况的时候

我们就可以在记录下来的c和d

里面去找是否存在满足条件

使 n=a^2+b^2+c^2+d^2

如果找到则就是正确答案

（注：因为枚举a和b的时候为按照顺序去找，所以我们一旦找到满足条件的a、b、c、d那么他就是最小的abcd字典序）

代码详解：

哈希：

#include<iostream>
#include<cmath>

using namespace std;

const int N=5e6+6;

struct node{
    int v,c,d;
}mp[N];

int main(){
    int n;
    cin>>n;

    for(int c=0;c*c<=n;c++)
        for(int d=c;c*c+d*d<=n;d++){
            int t=n-(c*c+d*d);
            if(!mp[t].v) {
                mp[t].v=1;
                mp[t].c=c;
                mp[t].d=d;
            }
        }

    for(int a=0;a*a<=n;a++)
        for(int b=a;a*a+b*b<=n;b++){
            int t =a*a+b*b;
            if(mp[t].v) {
                printf("%d %d %d %d",a,b,mp[t].c,mp[t].d);
                return 0;
            }
        }
    return 0;
}

二分：

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=5e6+6;

struct node{
    int v,c,d;
    bool operator<(const node&t) const {
        if(v!=t.v) return v<t.v;
        if(c!=t.c) return c<t.c;
        return d<t.d;
    }
}mp[N];

int main(){
    int n;
    cin>>n;

    int pos=0;
    for(int c=0;c*c<=n;c++)
        for(int d=c;c*c+d*d<=n;d++)
            mp[pos++]={n-c*c-d*d,c,d};

    sort(mp,mp+pos);

    for(int a=0;a*a<=n;a++)
        for(int b=a;a*a+b*b<=n;b++){
            int t =a*a+b*b;
            int l=0,r=pos-1;

            while(l<r){
                int mid=l+r>>1;
                if(mp[mid].v>=t) r=mid;
                else l=mid+1;
            }

            if(mp[l].v==t) {
                printf("%d %d %d %d",a,b,mp[l].c,mp[l].d);
                return 0;
            }
        }
    return 0;
}

PS:如果采用二分的写法，那么对于记录下来的c和d，需要进行排序。另外对于为什么用从c、d种选择出来的数一定满足从 a<=b<=c<=d 的原因就比如（a=1，b=2，c=0，d=0）我们一定可以先找到（a=0,b=0,c=1,d=2）满足题目要求的答案，故为最正解。

PPS:寒假摆烂玩宝可梦真好

蓝桥真题ampquotlt

有关四平方和（蓝桥杯C/C++B组真题详解）（三种做法）的更多相关文章

  1. ruby - 如何更优雅地记下这三种情况？ - 2

    是否可以让这段代码更紧凑？我在这里错过了什么吗？ifvaluemax_ratemax_rateelsevalueend 最佳答案 这里有一些完全不同的东西:[min_rate,value,max_rate].sort[1] 关于ruby-如何更优雅地记下这三种情况？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/13309740/

  2. 华为OD机试真题 C++ 实现【带传送阵的矩阵游离】【2023 Q2 | 200分】 - 2

            所有题目均有五种语言实现。C实现目录、C++实现目录、Python实现目录、Java实现目录、JavaScript实现目录题目n行m列的矩阵，每个位置上有一个元素你可以上下左右行走，代价是前后两个位置元素值差的绝对值.另外，你最多可以使用一次传送阵(只能从一个数跳到另外一个相同的数)求从走上角走到右下角最少需要多少时间。输入描述：第一行两个整数n,m，分别代表矩阵的行和列。后面n行，每行m个整数，分别代表矩阵中的元素。输出描述：一个整数，表示最少需要多少时间。

  3. 蓝桥杯备赛（二） - 2

    目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言：  在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC  已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析  这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy

  4. 物联网MQTT协议详解 - 2

    一、什么是MQTT协议MessageQueuingTelemetryTransport：消息队列遥测传输协议。是一种基于客户端-服务端的发布/订阅模式。与HTTP一样，基于TCP/IP协议之上的通讯协议，提供有序、无损、双向连接，由IBM（蓝色巨人）发布。原理：（1）MQTT协议身份和消息格式有三种身份：发布者（Publish）、代理（Broker）（服务器）、订阅者（Subscribe）。其中，消息的发布者和订阅者都是客户端，消息代理是服务器，消息发布者可以同时是订阅者。MQTT传输的消息分为：主题（Topic）和负载（payload）两部分Topic，可以理解为消息的类型，订阅者订阅（Su

  5. Tcl脚本入门笔记详解（一） - 2

    TCL脚本语言简介•TCL（ToolCommandLanguage）是一种解释执行的脚本语言（ScriptingLanguage）,它提供了通用的编程能力：支持变量、过程和控制结构；同时TCL还拥有一个功能强大的固有的核心命令集。TCL经常被用于快速原型开发，脚本编程，GUI和测试等方面。•实际上包含了两个部分：一个语言和一个库。首先，Tcl是一种简单的脚本语言，主要使用于发布命令给一些互交程序如文本编辑器、调试器和shell。由于TCL的解释器是用C\C++语言的过程库实现的，因此在某种意义上我们又可以把TCL看作C库，这个库中有丰富的用于扩展TCL命令的C\C++过程和函数，所以，Tcl是

  6. 【详解】Docker安装Elasticsearch7.16.1集群 - 2

    开门见山|拉取镜像dockerpullelasticsearch:7.16.1|配置存放的目录#存放配置文件的文件夹mkdir-p/opt/docker/elasticsearch/node-1/config#存放数据的文件夹mkdir-p/opt/docker/elasticsearch/node-1/data#存放运行日志的文件夹mkdir-p/opt/docker/elasticsearch/node-1/log#存放IK分词插件的文件夹mkdir-p/opt/docker/elasticsearch/node-1/plugins若你使用了moba，直接右键新建即可如上图所示依次类推创建

  7. 【Elasticsearch基础】Elasticsearch索引、文档以及映射操作详解 - 2

    文章目录概念索引相关操作创建索引更新副本查看索引删除索引索引的打开与关闭收缩索引索引别名查询索引别名文档相关操作新建文档查询文档更新文档删除文档映射相关操作查询文档映射创建静态映射创建索引并添加映射概念es中有三个概念要清楚，分别为索引、映射和文档（不用死记硬背，大概有个印象就可以）索引可理解为MySQL数据库；映射可理解为MySQL的表结构；文档可理解为MySQL表中的每行数据静态映射和动态映射上面已经介绍了，映射可理解为MySQL的表结构，在MySQL中，向表中插入数据是需要先创建表结构的；但在es中不必这样，可以直接插入文档，es可以根据插入的文档（数据），动态的创建映射（表结构），这就

  8. 蓝桥杯C/C++VIP试题每日一练之报时助手 - 2

    ?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5

  9. 最强Http缓存策略之强缓存和协商缓存的详解与应用实例 - 2

    HTTP缓存是指浏览器或者代理服务器将已经请求过的资源保存到本地，以便下次请求时能够直接从缓存中获取资源，从而减少网络请求次数，提高网页的加载速度和用户体验。缓存分为强缓存和协商缓存两种模式。一.强缓存强缓存是指浏览器直接从本地缓存中获取资源，而不需要向web服务器发出网络请求。这是因为浏览器在第一次请求资源时，服务器会在响应头中添加相关缓存的响应头，以表明该资源的缓存策略。常见的强缓存响应头如下所述：Cache-ControlCache-Control响应头是用于控制强制缓存和协商缓存的缓存策略。该响应头中的指令如下：max-age：指定该资源在本地缓存的最长有效时间，以秒为单位。例如：Ca

  10. IDEA 2022 创建 Spring Boot 项目详解 - 2

    如何用IDEA2022创建并初始化一个SpringBoot项目？目录如何用IDEA2022创建并初始化一个SpringBoot项目？0. 环境说明1.  创建SpringBoot项目 2.编写初始化代码0. 环境说明IDEA2022.3.1JDK1.8SpringBoot1.  创建SpringBoot项目        打开IDEA，选择NewProject创建项目。        填写项目名称、项目构建方式、jdk版本，按需要修改项目文件路径等信息。        选择springboot版本以及需要的包，此处只选择了springweb。        此处需特别注意，若你使用的是jdk1

随机推荐