构造+模拟,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的使用,某个…...
关于网络的基础知识
大家好,在当今数字时代,网络已经成为我们生活中不可或缺的一部分,它连接着世界的每一个角落,让信息、资源和人们彼此之间无阻碍地交流和共享。然而,对于许多人来说,网络仍然是一个神秘而复杂的领域…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...


