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

题解 | #J.Permutation and Primes# 2023牛客暑期多校8

J.Permutation and Primes

构造

题目大意

给定一个正整数 n n n ,构造一个 n n n 的排列,使得每对相邻元素的和或差的绝对值为一奇素数

解题思路

两个数的和或差是奇数,那么它们的奇偶性一定是不同的,因此所求排列中,奇数和偶数是交错分布的

对于排列的构造,首先考虑能不能通过自然排列转化而成//

赛时首先想到奇偶分开后,将全体偶数向左或向右循环移动 2 2 2 ~ 3 3 3 位,这样可以保证绝大部分位置和左右两边之差为 3 3 3 5 5 5 //当时以为要切了,结果剩余的数字考虑了两年半还是没有找到符合题意而不失一般性的构造方法

然后考虑分段调整。在上面思想的基础上,发现如果元素个数为 8 8 8 个,那么全体偶数左移 2 2 2 位和右移 2 2 2 位的结果都为: 1 , 6 , 3 , 8 , 5 , 2 , 7 , 4 1,6,3,8,5,2,7,4 1,6,3,8,5,2,7,4 。并且如果下一段长度为 8 8 8 的序列也按照这种规则变换顺序,那么 4 4 4 和下一段长度为 8 8 8 的序列的开头 9 9 9 之差为 5 5 5 ,符合题意,从而解决了边界问题

n n n 8 8 8 取余,记 n = 8 k + r n=8k+r n=8k+r 。解决前 r r r 个数的排列后,之后每 8 8 8 个数按 1 , 6 , 3 , 8 , 5 , 2 , 7 , 4 1,6,3,8,5,2,7,4 1,6,3,8,5,2,7,4 的顺序变换即可

时间复杂度

O ( n ) O(n) O(n)

参考代码

参考代码为已AC代码主干,其中部分功能需读者自行实现

ll rem[8][8]={{},{1},{1,2},{1,2,3},{1,4,3,2},{5,2,1,4,3},{5,2,1,4,3,6},{7,2,5,6,3,4,1}};
ll pl[9]={0,1,6,3,8,5,2,7,4};
void solve(){ll n;cin >> n;ll r=n%8,d=n/8;vector<ll> v;FORLL(i,0,r-1) v.emplace_back(rem[r][i]);FORLL(i,0,d-1){FORLL(j,1,8){v.emplace_back(8*i+pl[j]+r);}}FORLL(i,0,n-1) cout << v[i] << Presentation(i,n-1);
}

相关文章:

题解 | #J.Permutation and Primes# 2023牛客暑期多校8

J.Permutation and Primes 构造 题目大意 给定一个正整数 n n n &#xff0c;构造一个 n n n 的排列&#xff0c;使得每对相邻元素的和或差的绝对值为一奇素数 解题思路 两个数的和或差是奇数&#xff0c;那么它们的奇偶性一定是不同的&#xff0c;因此所求排列中&#…...

用vim打开后中文乱码怎么办

Vim中打开文件乱码主要是文件编码问题。用户可以参考如下解决方法。 1、用vim打开.vimrc配置文件 vim ~/.vimrc**注意&#xff1a;**如果用户根目录下没有.vimrc文件就把/etc/vim/vimrc文件复制过来直接用 cp /etc/vim/vimrc ~/.vimrc2、在.vimrc中加入如下内容 set termen…...

自然语言处理: 第六章Transformer- 现代大模型的基石

理论基础 Transformer&#xff08;来自2017年google发表的Attention Is All You Need (arxiv.org) &#xff09;&#xff0c;接上面一篇attention之后&#xff0c;transformer是基于自注意力基础上引申出来的结构&#xff0c;其主要解决了seq2seq的两个问题: 考虑了原序列和目…...

01-Hadoop集群部署(普通用户)

Hadoop集群部署&#xff08;普通用户&#xff09; 环境准备 1&#xff09;准备3台客户机&#xff08;关闭防火墙、静态IP、主机名称&#xff09; 如果这一步已经配置过了&#xff0c;可以忽略 # 1 关闭防火墙 systemctl stop firewalld.service # 关闭当前防火墙 systemctl…...

DC电源模块关于的电路布局设计

BOSHIDA DC电源模块关于的电路布局设计 DC电源模块是现代电子设备中常用的电源模块之一&#xff0c;其功能是将市电或其他输入电源转换成定电压、定电流的直流电源输出&#xff0c;以满足电子设备的供电需求。电路布局的设计是DC电源模块的重要组成部分&#xff0c;它直接影响…...

MATLAB实现免疫优化算法(附上多个完整仿真源码)

免疫优化算法是一种基于免疫学原理的优化算法。该算法的基本思想是通过模拟人类免疫系统的功能&#xff0c;来寻找最优解。 MATLAB是一种专门用于数学计算和数据处理的软件工具&#xff0c;它具有强大的数学计算和数据分析能力&#xff0c;可以方便地实现各种优化算法。 本文…...

登录界面中图片验证码的生成和校验

一、用pillpw生成图片验证码 1、安装pillow pip install pip install pillow2、下载字体 比如&#xff1a;Monaco.ttf 3、实现生成验证码的方法 该方法返回一个img ,可以把这个img图片保存到内存中&#xff0c;也可以以文件形式保存到磁盘&#xff0c;还返回了验证码的文字…...

go的make使用

在 Go 语言中&#xff0c;make 是一个用于创建切片、映射&#xff08;map&#xff09;和通道&#xff08;channel&#xff09;的内建函数。它提供了一种初始化和分配内存的方式&#xff0c;用于创建具有特定长度和容量的数据结构。下面将详细介绍 make 函数的使用方法和各种情况…...

竞赛项目 深度学习实现语义分割算法系统 - 机器视觉

文章目录 1 前言2 概念介绍2.1 什么是图像语义分割 3 条件随机场的深度学习模型3\. 1 多尺度特征融合 4 语义分割开发过程4.1 建立4.2 下载CamVid数据集4.3 加载CamVid图像4.4 加载CamVid像素标签图像 5 PyTorch 实现语义分割5.1 数据集准备5.2 训练基准模型5.3 损失函数5.4 归…...

一元三次方程求解

一元三次方程求解 题目描述提示输入输出格式输入格式输出格式 输入输出样例输入样例输出样例 算法分析A C 代码 题目描述 有形如&#xff1a; a x 3 b x 2 c x d 0 ax^3bx^2c^xd0 ax3bx2cxd0一元三次方程。给出该方程中各项的系数 ( a a a&#xff0c; b b b&#xff0c;…...

基于java在线音乐网站设计与实现

在线音乐网站的设计与实现 摘 要 随着互联网趋势的到来&#xff0c;各行各业都在考虑利用互联网将自己推广出去&#xff0c;最好方式就是建立自己的互联网系统&#xff0c;并对其进行维护和管理。在现实运用中&#xff0c;应用软件的工作规则和开发步骤&#xff0c;采用SSM框架…...

Python爬虫如何更换ip防封

作为一名长期扎根在爬虫行业动态ip解决方案的技术员&#xff0c;我发现很多人常常在使用Python爬虫时遇到一个困扰&#xff0c;那就是如何更换IP地址。别担心&#xff0c;今天我就来教你如何在Python爬虫中更换IP&#xff0c;让你的爬虫不再受到IP封锁的困扰。废话不多说&#…...

涛思数据联合长虹佳华、阿里云 Marketplace 正式发布 TDengine Cloud

近日&#xff0c;涛思数据联合长虹佳华&#xff0c;正式在阿里云 Marketplace 发布全托管的时序数据云平台 TDengine Cloud&#xff0c;为用户提供更加丰富的订购渠道。目前用户可通过阿里云 Marketplace 轻松实现 TDengine Cloud 的订阅与部署&#xff0c;以最低的成本搭建最高…...

特殊符号的制作 台风 示例 使用第三方工具 Photoshop 地理信息系统空间分析实验教程 第三版

特殊符号的制作 首先这是一个含有字符的&#xff0c;使用arcgis自带的符号编辑器制作比较困难。所以我们准备采用Adobe Photoshop 来进行制作符号&#xff0c;然后直接导入符号的图片文件作为符号 我们打开ps&#xff0c;根据上面的图片的像素长宽比&#xff0c;设定合适的高度…...

IoTDB1.X windows运行失败问题的处理

在windows运行 IoTDB1.x时 会出现如图所示的问题 为什么会出现这样的问题&#xff1f;java没有安装还是未调用成功&#xff0c;我是JAVA8~11~17各种更换都未能解决问题&#xff0c;最后对其bat文件进行查看&#xff0c;发现在conf\datanode-env.bat、conf\confignode-env.bat这…...

pdf转图片【java版实现】

一、引入依赖 引入需要导入到项目中的依赖&#xff0c;如下所示&#xff1a; <!-- pdf转图片 --><dependency><groupId>net.sf.cssbox</groupId><artifactId>pdf2dom</artifactId><version>1.7</version></dependency>…...

python3.6 安装pillow失败

问题描述 python3 安装 pillow 失败 错误原因 python3.6 不支持 pillow9.0 以上的版本 解决方法&#xff1a; 指定版本安装 e.g., pillow8.0 pip3 install pillow8.0...

巨人互动|Meta海外户Meta的业务工具转化API

Meta的业务工具转化API是一项创新技术&#xff0c;它可以帮助企业实现更高效的业务工具转化和集成。通过这个API&#xff0c;企业可以将不同的业务工具整合到一个统一的平台上&#xff0c;提高工作效率和协作能力。本文小编将介绍Meta的业务工具转化API的功能和优势。 巨人互动…...

【JAVA】包、权限修饰符、final关键字、常量、枚举、抽象类、接口

1 包 包是用来分门别类的管理各种不同类的&#xff0c;类似于文件夹、建包利于程序的管理和维护。建包语句必须在第一行建包的语法格式&#xff1a;package 公司域名倒写.项目名称。包名建议全部小写相同包下的类可以直接访问&#xff0c;不同包下的类必须导包&#xff0c;才可…...

6.s081/6.1810(Fall 2022)Lab5: Copy-on-Write Fork for xv6

前言 本来往年这里还有个Lazy Allocation的&#xff0c;今年不知道为啥直接给跳过去了。. 其他篇章 环境搭建 Lab1: Utilities Lab2: System calls Lab3: Page tables Lab4: Traps Lab5: Copy-on-Write Fork for xv6 参考链接 官网链接 xv6手册链接&#xff0c;这个挺重要…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

2.3 物理层设备

在这个视频中&#xff0c;我们要学习工作在物理层的两种网络设备&#xff0c;分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间&#xff0c;需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质&#xff0c;假设A节点要给…...