当前位置: 首页 > 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;这个挺重要…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...