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

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

PLC入门【4】基本指令2(SET RST)

04 基本指令2 PLC编程第四课基本指令(2) 1、运用上接课所学的基本指令完成个简单的实例编程。 2、学习SET--置位指令 3、RST--复位指令 打开软件(FX-TRN-BEG-C)&#xff0c;从 文件 - 主画面&#xff0c;“B: 让我们学习基本的”- “B-3.控制优先程序”。 点击“梯形图编辑”…...