构造+模拟,CF1148C. Crazy Diamond
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
Problem - 1148C - Codeforces
二、解题报告
1、思路分析
题目提示O(5n)的解法了,事实上我们O(3n)就能解决,关键在于1,n的处理
我们读入数据a[],代表初始数组,p[i]代表 i 的下标
如果p[i] != i
说明需要交换
a[p[i]] 一定能跟a[1]或者a[n]交换, a[i]也一定能跟1或n交换
假设 a[i] 的可交换位置为x,a[p[i]] 的可交换位置为y(x、y只可能为1、n)
那么我们使得元素i从p[i] -> y -> x -> i 就在3步之内让i到达了下标i
此时a[1] 和 a[n]可能不满足a[1] = 1, a[n] = n
事实上我们将每个元素调整完后再调整1和n即可
这也是为什么能从O(5n)优化到O(3n)
2、复杂度
时间复杂度: O(3n)空间复杂度:O(n)
3、代码详解
#include <bits/stdc++.h>
using PII = std::pair<int, int>;
const int N = 3e5 + 10;
int p[N], a[N], n, s;
std::vector<PII> path;void swap(int x, int y) {std::swap(p[a[x]], p[a[y]]);std::swap(a[x], a[y]);path.emplace_back(x, y);
}int main () {std::cin >> n;path.reserve(5 * n);for (int i = 1; i <= n; i ++ ) std::cin >> a[i], p[a[i]] = i;for (int i = 1; i <= n / 2; i ++ ) {if (p[i] != i) {if (p[i] <= n / 2) {swap(p[i], n);swap(i, n);}else {swap(1, p[i]);swap(1, n);swap(i, n);}}}for (int i = n / 2 + 1; i <= n; i ++ ) {if (p[i] != i) {if (p[i] > n / 2) {swap(1, p[i]);swap(1, i);}else {swap(p[i], n);swap(1, n);swap(1, i);}}}if (a[1] != 1) swap(1, n);std::cout << path.size() << '\n';for (auto [x, y] : path) std::cout << x << " " << y << '\n';return 0;
}
相关文章:
构造+模拟,CF1148C. Crazy Diamond
一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 1148C - Codeforces 二、解题报告 1、思路分析 题目提示O(5n)的解法了,事实上我们O(3n)就能解决,关键在于1,n的处理 我们读入数据a[],代表初始数组…...
CAD二次开发(2)-将直线对象添加到CAD图形文件
1. 准备工作 创建一个类库项目,如下: 2. 分析Line对象 Line类的初始化方法和参数 using Autodesk.AutoCAD.DatabaseServices; Line line new Line();Line 继承Curve 继承Entity 继承DBObject 继承Drawable 继承RXObject 初始化方法有两个…...
代码随想录二刷 Day05 | 242.有效的字母异位词,349. 两个数组的交集,202. 快乐数,1. 两数之和,454.四数相加II,383. 赎金信
题目与题解 参考资料:哈希表理论基础 Tips: 一般哈希表都是用来快速判断一个元素是否出现集合里哈希表生成原理:先通过哈希函数将变量映射为hashcode,如果二者hashcode相同,再通过哈希碰撞方法(拉链法&…...
2024年四川省三支一扶报名流程图解✅
2024年四川省三支一扶报名流程图解✅ 🔴时间安排 1、报名时间:5月31日—6月4日17:00 2、资格初审时间:5月31日—6月5日17:00 3、准考证打印时间:6月25日—6月29日 4、笔试时间:6月30日 5、笔试成绩:7…...
js Dom基础
获取元素 1、getElementById() 通过id属性获取一个元素节点对象 <div id"div1"></div> <script> var div1 document.getElementById(div1) </script> 2、 getElementsByTagName()可以根据标签名来获取一组元素节点对象 这个方法会给我们返…...
pytest识别测试用例的机制以及和unittest的区别
pytest识别测试用例的机制 文件 以test_开头或以_test结尾的python文件,即test_xxx.py或xxx_test.py类,在第一点识别到的文件中的类,且满足一下任一条件: 1)以Test_开头,且没有__init__()初始化函数的类&a…...
民国漫画杂志《时代漫画》第17期.PDF
时代漫画17.PDF: https://url03.ctfile.com/f/1779803-1248612629-85326d?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了,截止1937年6月战争来临被迫停刊共发行了39期。 ps:资源来源网络!...
[AIGC] Spring Boot 2 自定义 Starter 指南
Spring Boot 包含一系列的 “Starter POMs”,它们都是一些方便的依赖描述符,你可以在你的应用中导入。在一些情况下,你可能想创建自己的自定义 starter。以下是创建自己的 Spring Boot Starter 的步骤。 文章目录 1. 创建基本的 Maven 项目2.…...
HCIP综合实验命令
目录 一、配置IP地址 二、配置DHCP 三、配置静态路由(内网通) 四、配置缺省路由 (外网通) 五、配置缺省 (全网通) 六、防环配置 七、配置远程登录 八、修改优先级 九、配置MP-GROUP 十、配置ppp进…...
JS移动端设置mouseover,mouseleave有效么
在移动设备的浏览器环境中,mouseover 和 mouseleave 事件的行为与桌面浏览器有所不同,主要是因为移动设备的交互方式主要是基于触摸的,而不是基于鼠标的。 在移动设备上,当用户触摸屏幕时,通常会触发 touchstart 事件…...
IAR9.30安装和注册相关
下载解压licpatcher64工具,把licpatcher64.exe拷贝到IAR的安装目录中双击运行。 示例IAR9.30.1默认安装如下如下,一共三个分别拷贝运行,不要遗漏。 C:\Program Files\IAR Systems\Embedded Workbench 9.1\arm\bin C:\Program Files\IAR Syst…...
HTTP Digest Access Authentication Schema
HTTP Digest Access Authentication Schema 背景介绍ChallengeResponse摘要计算流程总结参考 背景 本文内容大多基于网上其他参考文章及资料整理后所得,并非原创,目的是为了需要时方便查看。 介绍 HTTP Digest Access Authentication Schemaÿ…...
MySql超大Sql文件导入效率优化
对于MySQL中超大SQL文件的导入,效率优化是至关重要的,因为不当的操作可能导致导入过程耗时过长,甚至失败。以下是一些建议来优化MySQL超大SQL文件的导入效率: 调整max_allowed_packet参数: 这个参数定义了MySQL服务器和…...
【leetcode1944--队列中可以看到的人数】
有n人排成一个队列,从左到右编号为0到n-1,height数组记录每个人的身高,返回一个数组,记录每个人能看到几个人。 类比:山峰问题,高的后面的矮的看不见。 从后往前,最后一个元素入栈,…...
基于51单片机的室内空气质量检测-仿真设计
本设计是基于单片机的空气质量检测设计,主要实现以下功能: 可实现通过SGP30测量二氧化碳及甲醛浓度,当超过设置的最大值时,进行报警及通风和净化空气处理 可实现通过MQ-4测量甲烷浓度,当超过设置的最大值时࿰…...
day22二叉树part08 | 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点
**235. 二叉搜索树的最近公共祖先 ** 这里利用上了二叉搜索树的特性,从上到下遍历,最近的公共祖先一定是满足p->val < root->val < q->val的 class Solution { public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, Tr…...
【Linux】Linux环境基础开发工具_2
文章目录 四、Linux环境基础开发工具2. vimvim的常见模式 未完待续 四、Linux环境基础开发工具 2. vim vim 是Linux下的一款 多模式编辑器 ,可以用来写代码,是 vi 的升级版。 此时无法输入,需要切换模式。 如上图,i 就是切换成…...
长方形边框 上方中间有缺口 css
<div class"text_6">大234234师掌4234柜</div><div class"text-wrapper_1"><span class"paragraph_1">四川慧创云戈科技有限公司推出的“大师掌柜”,是一个以餐饮外卖为切入口,专注实体小店新零售…...
2024-05-29 架构-程序设计-思考
摘要: 最近在抽出时间做一个数据库的driver, 其中有些问题驱动的软件代码的思考,是很值得回味的。 做的系统,所思考的问题,所设计的解决方案,其实都是可以看作是对解决问题方式。而不仅仅是某个类库的API的使用,某个…...
关于网络的基础知识
大家好,在当今数字时代,网络已经成为我们生活中不可或缺的一部分,它连接着世界的每一个角落,让信息、资源和人们彼此之间无阻碍地交流和共享。然而,对于许多人来说,网络仍然是一个神秘而复杂的领域…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...


