当前位置: 首页 > news >正文

C. Build Permutation【整数理论、构造、思维】

链接
理论基础
结论:在区间[n,2n]上,至少存在一个完全平方数。结论:在区间[n,2n]上,至少存在一个完全平方数。结论:在区间[n,2n]上,至少存在一个完全平方数。
构造⌈n⌉2构造\lceil \sqrt{n}\rceil^2构造n2
∵n⩽⌈n⌉\because \sqrt n \leqslant \lceil \sqrt{n}\rceilnn
∴n⩽⌈n⌉2\therefore n\leqslant \lceil \sqrt{n}\rceil^2nn2
⌈n⌉⩽n+1\lceil \sqrt{n}\rceil \leqslant \sqrt{n} + 1nn+1
⌈n⌉2⩽n+2n+1\lceil \sqrt{n}\rceil^2 \leqslant n+2\sqrt n+1n2n+2n+1
何时2n⩾n+2n+1何时2n\geqslant n+2\sqrt n+1何时2nn+2n+1
即n−2n−1⩾0即n-2\sqrt n-1\geqslant0n2n10
(n−1)2⩾2(\sqrt n-1)^2\geqslant 2(n1)22
当n⩾7的时候成立,而且取不到等号当n\geqslant 7的时候成立,而且取不到等号n7的时候成立,而且取不到等号
然后枚举0到6所有数0123456发现均可以找到不到2n的平方数然后枚举0到6所有数0~1~2~3~4~5~6发现均可以找到不到2n的平方数然后枚举06所有数0 1 2 3 4 5 6发现均可以找到不到2n的平方数
分别为−−−−−−0126543分别为------0~1~2~6~5~4~3分别为0 1 2 6 5 4 3
分析
这里从最后的数开始寻找,[n, 2n],必定有一个平方数,与这个数配对的数可以是0~n的所有数,我们从后往前配对,一旦配对成功就倒置使得这些数的和均为平方数即可。面对剩余的序列如法炮制,同样是从最后一个开始找然后配对使得这些数的和均在以最后一个数为n的[n, 2n]区间内的一个数,由于倒置的和均等于头尾的和所有中间这部分倒置的和就是合法的。
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 5;
int vis[N];
bool check(int x) {int sq = sqrt(x);return sq * sq == x;
}
void solve() {int n;cin >> n;for (int i = 0; i < n; i++) vis[i] = 0;map<int, int> mp; for (int i = n - 1; i >= 0; i--) {if (vis[i]) continue;//如果已经配对过的话int p = i;//从这个点开始往前找while (!check(p + i)) p--;//找到第一个恰好是平方的数int sum = p + i;//注意这里是ifor (int j = p; j <= i; j++) {//到i不是到n-1vis[j] = 1;mp[j] = sum - j;}}for (int i = 0; i < n; i++) {cout << mp[i] << " \n"[i == n - 1];}
}
int main(){ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) solve();return 0;
}

相关文章:

C. Build Permutation【整数理论、构造、思维】

链接 理论基础 结论&#xff1a;在区间[n,2n]上&#xff0c;至少存在一个完全平方数。结论&#xff1a;在区间[n,2n]上&#xff0c;至少存在一个完全平方数。结论&#xff1a;在区间[n,2n]上&#xff0c;至少存在一个完全平方数。 构造⌈n⌉2构造\lceil \sqrt{n}\rceil^2构造⌈…...

关于ETL的两种架构(ETL架构和ELT架构)

ETL&#xff0c;是英文 Extract-Transform-Load 的缩写&#xff0c;用来描述将数据从来源端经过抽取&#xff08;extract&#xff09;、转换&#xff08;transform&#xff09;、加载&#xff08;load&#xff09;至目的端的过程。ETL一词较常用在数据仓库&#xff0c;但其对象…...

android系统目录

环境&#xff1a;android studio引入android系统源码android和ubuntu策略路由的差异android源码编译问题&#xff08;单编&#xff09;repo(android源码)命令使用和注意事项wifi&#xff1a;wifi的加密类型梳理android11 wifisetting 流程跟踪android wifi热点settingandroid n…...

【C/C++】中【typedef】用法大全

总结一下typedef用法&#xff0c;一共七种&#xff0c;分别是&#xff1a;为基本数据类型起别名、为结构体起别名、为指针类型起别名、为数组类型起别名、为枚举类型起别名、为模版函数起别名。 目录 一、为基本数据类型起别名 二、为结构体起别名 三、为指针类型起别名 四…...

超实用的公众号运营攻略分享,纯干货

很多小伙伴抱怨&#xff0c;公众号运营真的越来越难做了&#xff01; 每天会因为少得可怜的阅读量发愁&#xff0c;每天会因为纠结写什么选题发愁&#xff0c;每天更会因为公众号没有什么起色而感到无力。 现阶段公众号运营趋于饱和状态&#xff0c;公众号创建门槛低&#xf…...

编写NodeJs脚本实现接口请求

要编写运行脚本,需要先搭建开发环境 环境搭建 nodeJs脚本运行,当然需要先安装nodejs环境 官方地址在这里: nodejs官网 打开官网地址,可以看到下面一句话: Node.js is an open-source, cross-platform JavaScript runtime environment. 在打开的页面,可以直接下载最新的…...

【无人机】回波状态网络(ESN)在固定翼无人机非线性控制中的应用(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

YAML 文件简介

简介 我们在安装 kubernetes 集群的时候使用了一些 YAML 文件来创建相关的资源&#xff0c;但是对 YAML 文件还是非常陌生。所以我们先来简单看一看 YAML 文件是如何工作的&#xff0c;并使用 YAML 文件来定义一个 kubernetes pod&#xff0c;然后再来定义一个 kubernetes dep…...

Python四大主题之一【 Web】 编程框架

目前Python的网络编程框架已经多达几十个&#xff0c;逐个学习它们显然不现实。但这些框架在系统架构和运行环境中有很多共通之处&#xff0c;本文带领读者学习基于Python网络框架开发的常用知识,及目前的4种主流Python网络框架&#xff1a;Django、Tornado、Flask、Twisted。 …...

【C++】哈希表

1. unordered系列关联式容器 在C98中&#xff0c;STL提供了底层为红黑树结构的一系列关联式容器&#xff0c;在查询时效率可达到 &#xff0c;即最差情况下需要比较红黑树的高度次&#xff0c;当树中的节点非常多时&#xff0c;查询效率也不理想。最好的查询是&#xff0c;进行…...

深度学习入门(六十七)循环神经网络——注意力机制

深度学习入门&#xff08;六十七&#xff09;循环神经网络——注意力机制前言循环神经网络——注意力机制课件心理学注意力机制注意力机制是显式地考虑随意线索非参注意力池化层Nadaraya-Watson 核回归&#xff1a;总结教材&#xff08;注意力提示&#xff09;1 生物学中的注意…...

阿里云云通信风控系统的架构与实践

作者&#xff1a;铭杰 阿里云云通信创立于 2017 年&#xff0c;历经 5 年发展已经孵化出智能消息、智能语音、隐私号、号码百科等多个热门产品。目前&#xff0c;已成为了国内云通信市场的领头羊&#xff0c;在国际市场上服务范围也覆盖了 200 多个国家。随着业务的不断壮大&am…...

【性能测试】loadrunner(一)知识准备

【性能测试】loadrunner&#xff08;一&#xff09;知识准备 目录&#xff1a;导读 1.0. 前言 1.1 性能测试术语介绍 1.2 性能测试分类 1.3 HTTP我们需要知道的 1.4 Loadrunner 12.55安装 1.0. 前言 ​ 在性能测试中&#xff0c;牵扯到了许多比较杂的知识点&#xff0c;…...

【Vue3源码】第五章 ref的原理 实现ref

【Vue3源码】第五章 ref的原理 实现ref 上一章节我们实现了reactive 和 readonly 嵌套对象转换功能&#xff0c;以及shallowReadonly 和isProxy几个简单的API。 这一章我们开始实现 ref 及其它配套的isRef、unRef 和 proxyRefs 1、实现ref 接受一个内部值&#xff0c;返回一…...

[Flink]部署模式(看pdf上的放上面)

运行一个wordcountval dataStream: DataStream[String] environment.socketTextStream("hadoop1", 7777) //流式数据不能进行groupBy,流式数据要来一条处理一次.0表示第一个元素,1表示第二个元素 //keyBy(0)根据第一个元素进行分组 val out: DataStream[(String, In…...

Linux 查看 CPU 信息,机器型号,内存等信息

平时用的可能少&#xff0c;但需要记住&#xff0c;使用的命令&#xff0c;转载https://my.oschina.net/hunterli/blog/140783&#xff0c;以记录学习 系统 # uname -a # 查看内核/操作系统/CPU信息 # head -n 1 /etc/issue # 查看操作系统版本 # cat /proc/…...

三维量子力学 量子力学(3)

动量ppp有三个分量&#xff0c;为pxp_xpx​等。它们分别满足与位置坐标的对易关系&#xff0c;比如px−iℏ∂∂xp_x-i\hbar\frac{\partial }{\partial x}px​−iℏ∂x∂​。可以用位置坐标梯度算符表示即p−iℏ∇\bm{p}-i\hbar\nablap−iℏ∇。位置矢量用r\bm{r}r表示。 在d3r…...

Blazor入门100天 : 身份验证和授权 (6) - 使用 FreeSql orm 管理ids数据

目录 建立默认带身份验证 Blazor 程序角色/组件/特性/过程逻辑DB 改 Sqlite将自定义字段添加到用户表脚手架拉取IDS文件,本地化资源freesql 生成实体类,freesql 管理ids数据表初始化 Roles,freesql 外键 > 导航属性完善 freesql 和 bb 特性 本节源码 https://github.com/…...

Java文件IO操作:File类的相关内容

Java文件IO操作一、File类1.相对路径和绝对路径2.路径分隔符&#xff08;同一路径下、多个路径下&#xff09;3.实例化4.常见方法一、File类 File类继承自Object类&#xff0c;实现了Serializable接口和Comparable接口&#xff1b; File类属于java.io包&#xff1b; File类是文…...

竣达技术 | 巡检触摸屏配合电池柜,电池安全放首位!

机房蓄电池常见的故障 1.机房电池着火和爆炸 目前在数据机房蓄电池爆炸着火事故频发&#xff0c;导致业主损失严重。一般机房电池是由于其中一节电池裂化后未妥善管理&#xff0c;电池急剧恶化导致爆炸着火。由于电池是串联及并联在使用&#xff0c;只要一节着火燃烧整片瞬间…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...