四平方和 刷题笔记

/*
四平方和
直接暴力搜索 可能会超时 
使用二分辅助搜索 
先枚举出  c*c+d*d并存入数组
用式子算出  a*a+b*b还剩下多少查找sum数组里面是否存在符合条件的数
查找方式使用二分搜索
当逼近答案后 检查一下是否为所需的数 如果是 直接输出
*/ 

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2500010;

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

int n, m;

int main()
{
    cin >> n;

    for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ )
            sum[m ++ ] = {c * c + d * d, c, d};
// 
    sort(sum, sum + m);

    for (int a = 0; a * a <= n; a ++ )
        for (int b = 0; a * a + b * b <= n; b ++ )
        {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (sum[mid].s >= t) r = mid;
                else l = mid + 1;
            }
            if (sum[l].s == t)
            {
                printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/431116.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

社交媒体的未来图景:探索Facebook的数字化之旅

社交媒体已经成为现代社会不可或缺的一部分&#xff0c;其影响力已经深入到人们生活的方方面面。而在众多社交媒体平台中&#xff0c;Facebook无疑是其中的巨头&#xff0c;其数字化之旅更是引领着整个社交媒体行业的发展方向。本文将深入探讨社交媒体的未来图景&#xff0c;以…

事务处理

Oracle从入门到总裁:https://blog.csdn.net/weixin_67859959/article/details/135209645 事务处理 事务是保证数据完整性的一种手段。 事务具备 ACID 原则&#xff08;包括原子性、一致性、独立性及持久性&#xff09;&#xff0c;保证一个人更新数据的时候&#xff0c;其他…

C# 中 TryParse 将字符串转换为特定类型的方法

在 C# 中&#xff0c;TryParse 是一个用于将字符串转换为特定类型的方法。它用于尝试解析字符串并将其转换为指定类型的值&#xff0c;而不会引发异常。如果解析成功&#xff0c;它将返回 true 并将解析结果存储在输出参数中&#xff1b;如果解析失败&#xff0c;它将返回 fals…

C# 中 Math.Round 数学函数

在 C# 中&#xff0c;Math.Round 是一个数学函数&#xff0c;用于对一个浮点数进行四舍五入操作。它接受一个浮点数作为输入&#xff0c;并返回一个最接近输入值的整数或指定小数位数的浮点数。 Math.Round 方法有多个重载&#xff0c;其中最常用的重载有以下两种形式&#xf…

就业班 2401--3.5 Linux Day11--DNS解析

DNS域名解析服务 少壮不努力&#xff0c;老大徒伤悲。一、 1.DNS介绍 DNS 是域名系统 (Domain Name System) 的缩写&#xff0c;是因特网的一项核心服务&#xff0c;它作为可以将域名和IP地址相互映射的一个分布式数据库&#xff0c;能够使人更方便的访问互联网&#xff0c;…

「项目实践」如何实现导购推荐“千人千面”

前言 在电商背景下&#xff0c;为用户提供精准的导购推荐不仅能极大提升购物体验&#xff0c;也成为推动业务增长的关键驱动力。随着人工智能和数据科学的快速发展&#xff0c;实现“千人千面”的个性化推荐已不再是无法触及的梦想。如何在众多商品中准确捕捉用户的偏好&#…

进口及国内细胞分析仪厂家名录大全-贝克曼、安捷伦、希森美康、迈瑞.....

流式细胞仪是一种测量层流中细胞的设备&#xff08;细胞仪&#xff09;&#xff0c;其通过将每个细胞排列在鞘液中&#xff0c;加以激光束照射&#xff0c;可测量散射光和荧光&#xff0c;从而获得有关每个细胞的信息&#xff0c;包含细胞结构&#xff08;如大小、粒度、表面积…

Java知识点总结(二)

ID生成策略 主键自增id 主键自动增长&#xff0c;不用手工设值、数字型&#xff0c;占用空间小、检索非常有利、有顺序&#xff0c;不会重复&#xff0c;但在迁移旧数据是会出现id冲突 UUID 基于时间&#xff0c;计数器和地址生成32位的id redis生成id 原子性自增&#xff0c;并…

记录一次排查负载均衡不能创建的排查过程

故障现象&#xff0c;某云上&#xff0c;运维同事在创建负载均衡的时候&#xff0c;发现可以创建资源&#xff0c;但是创建完之后&#xff0c;不显示对应的负载均衡。 创建负载均衡时候&#xff0c;按f12发现console有如下报错 后来请后端网络同事排查日志发现&#xff0c;是后…

探秘X-XSS-Protection头对抗跨站脚本攻击

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 探秘X-XSS-Protection头对抗跨站脚本攻击 前言XSS攻击的威胁X-XSS-Protection头的作用X-XSS-Protection头的配置报告模式&#xff08;Report-Only&#xff09;攻击与绕过X-XSS-Protection的方法 前言 …

(学习日记)2024.03.04:UCOSIII第六节:main函数+前六节总结

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…

android开发教程视频,android组件化和插件化

第一阶段&#xff1a;Android 基础知识回顾&#xff1a; 回顾Android 开发编程&#xff0c;深入理解Android系统原理和层次结构&#xff0c;深入分析Handler源码和原理&#xff1b;回顾Java&#xff0c;C/C&#xff0c;Kotlin、dart 在Android开发中必用的语言&#xff0c;熟悉…

DQL语言学习(2024/3/5)one

1.基础查询&#xff1a; select 查询列表 from 表名&#xff1b; 查询列表可以是&#xff1a;①表中的字段、②常量值、③表达式、④函数 ①查询表中的单个字段&#xff0c;多个字段&#xff0c;所有字段 select *from 表名&#xff1b; ③查询表达式: select 100*98; ④…

软件设计师10--计算机组成与体系结构章节回顾

软件设计师10--计算机组成与体系结构章节回顾 章节重要内容考情分析 章节重要内容 考情分析

css使用

一、什么是CSS <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><style>div{color: red;}</style> </head> <body><div>Hello CSS</div></…

MySQL——性能调优

性能调优&#xff08;重要&#xff09; SQL 优化的目的 减少磁盘 IO&#xff1a;尽可能避免全表扫描、尽量使用索引、尽量使用覆盖索引减少回表操作减少 CPU 和内存的消耗&#xff0c;尽可能减少排序、分组、去重之类的操作&#xff0c;尽量减少事务持有锁的时间 优化途径&…

QEMU设备直通pass through的地址映射转换

[内核:HVA]->[QEMU:HVA]的mmap地址映射 $ sudo cat /proc/2047239/maps | grep -i vfio address perms offset dev inode pathname 7f4b5444a000-7f4b5445a000 rw-s 9da50000 00:0e 13037 anon_inode:[vfi…

稀碎从零算法笔记Day7-LeetCode:罗马数字转整数

题型&#xff1a;字符串转化、找规律 链接&#xff1a;13. 罗马数字转整数 - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;LeetCode 题目描述 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 …

【HTML】day01

列表 作用&#xff1a;布局内容排序整齐的区域。 列表分类&#xff1a;无序列表、有序链表、定义列表 无序列表 <ul><li>test</li><li>test</li><li>test</li><li><h1>h1</h1></li></ul><!DOCTYPE…

DolphinScheduler——奇富科技的调度实践

目录 一、技术架构 二、业务挑战 2.1 调度任务量大 2.2 运维复杂 2.3 SLA要求高 三、调度优化实践 3.1 重复调度 3.2 漏调度 3.3 Worker服务卡死 3.4 任务重复运行 四、服务监控 4.1 方法耗时监控 4.2 任务调度链路监控 五、用户收益 原文大佬的这篇调度系统案例…