构造+模拟,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的使用,某个…...
关于网络的基础知识
大家好,在当今数字时代,网络已经成为我们生活中不可或缺的一部分,它连接着世界的每一个角落,让信息、资源和人们彼此之间无阻碍地交流和共享。然而,对于许多人来说,网络仍然是一个神秘而复杂的领域…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...
js 设置3秒后执行
如何在JavaScript中延迟3秒执行操作 在JavaScript中,要设置一个操作在指定延迟后(例如3秒)执行,可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法,它接受两个参数: 要执行的函数&…...
运行vue项目报错 errors and 0 warnings potentially fixable with the `--fix` option.
报错 找到package.json文件 找到这个修改成 "lint": "eslint --fix --ext .js,.vue src" 为elsint有配置结尾换行符,最后运行:npm run lint --fix...


