当前位置: 首页 > news >正文

构造+模拟,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)的解法了&#xff0c;事实上我们O(3n)就能解决&#xff0c;关键在于1&#xff0c;n的处理 我们读入数据a[]&#xff0c;代表初始数组…...

CAD二次开发(2)-将直线对象添加到CAD图形文件

1. 准备工作 创建一个类库项目&#xff0c;如下&#xff1a; 2. 分析Line对象 Line类的初始化方法和参数 using Autodesk.AutoCAD.DatabaseServices; Line line new Line();Line 继承Curve 继承Entity 继承DBObject 继承Drawable 继承RXObject 初始化方法有两个&#xf…...

代码随想录二刷 Day05 | 242.有效的字母异位词,349. 两个数组的交集,202. 快乐数,1. 两数之和,454.四数相加II,383. 赎金信

题目与题解 参考资料&#xff1a;哈希表理论基础 Tips&#xff1a; 一般哈希表都是用来快速判断一个元素是否出现集合里哈希表生成原理&#xff1a;先通过哈希函数将变量映射为hashcode&#xff0c;如果二者hashcode相同&#xff0c;再通过哈希碰撞方法&#xff08;拉链法&…...

2024年四川省三支一扶报名流程图解✅

2024年四川省三支一扶报名流程图解✅ &#x1f534;时间安排 1、报名时间&#xff1a;5月31日—6月4日17:00 2、资格初审时间&#xff1a;5月31日—6月5日17:00 3、准考证打印时间&#xff1a;6月25日—6月29日 4、笔试时间&#xff1a;6月30日 5、笔试成绩&#xff1a;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文件&#xff0c;即test_xxx.py或xxx_test.py类&#xff0c;在第一点识别到的文件中的类&#xff0c;且满足一下任一条件&#xff1a; 1&#xff09;以Test_开头&#xff0c;且没有__init__()初始化函数的类&a…...

民国漫画杂志《时代漫画》第17期.PDF

时代漫画17.PDF: https://url03.ctfile.com/f/1779803-1248612629-85326d?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps:资源来源网络&#xff01;...

[AIGC] Spring Boot 2 自定义 Starter 指南

Spring Boot 包含一系列的 “Starter POMs”&#xff0c;它们都是一些方便的依赖描述符&#xff0c;你可以在你的应用中导入。在一些情况下&#xff0c;你可能想创建自己的自定义 starter。以下是创建自己的 Spring Boot Starter 的步骤。 文章目录 1. 创建基本的 Maven 项目2.…...

HCIP综合实验命令

目录 一、配置IP地址 二、配置DHCP 三、配置静态路由&#xff08;内网通&#xff09; 四、配置缺省路由 &#xff08;外网通&#xff09; 五、配置缺省 &#xff08;全网通&#xff09; 六、防环配置 七、配置远程登录 八、修改优先级 九、配置MP-GROUP 十、配置ppp进…...

JS移动端设置mouseover,mouseleave有效么

在移动设备的浏览器环境中&#xff0c;mouseover 和 mouseleave 事件的行为与桌面浏览器有所不同&#xff0c;主要是因为移动设备的交互方式主要是基于触摸的&#xff0c;而不是基于鼠标的。 在移动设备上&#xff0c;当用户触摸屏幕时&#xff0c;通常会触发 touchstart 事件…...

IAR9.30安装和注册相关

下载解压licpatcher64工具&#xff0c;把licpatcher64.exe拷贝到IAR的安装目录中双击运行。 示例IAR9.30.1默认安装如下如下&#xff0c;一共三个分别拷贝运行&#xff0c;不要遗漏。 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摘要计算流程总结参考 背景 本文内容大多基于网上其他参考文章及资料整理后所得&#xff0c;并非原创&#xff0c;目的是为了需要时方便查看。 介绍 HTTP Digest Access Authentication Schema&#xff…...

MySql超大Sql文件导入效率优化

对于MySQL中超大SQL文件的导入&#xff0c;效率优化是至关重要的&#xff0c;因为不当的操作可能导致导入过程耗时过长&#xff0c;甚至失败。以下是一些建议来优化MySQL超大SQL文件的导入效率&#xff1a; 调整max_allowed_packet参数&#xff1a; 这个参数定义了MySQL服务器和…...

【leetcode1944--队列中可以看到的人数】

有n人排成一个队列&#xff0c;从左到右编号为0到n-1&#xff0c;height数组记录每个人的身高&#xff0c;返回一个数组&#xff0c;记录每个人能看到几个人。 类比&#xff1a;山峰问题&#xff0c;高的后面的矮的看不见。 从后往前&#xff0c;最后一个元素入栈&#xff0c…...

基于51单片机的室内空气质量检测-仿真设计

本设计是基于单片机的空气质量检测设计&#xff0c;主要实现以下功能&#xff1a; 可实现通过SGP30测量二氧化碳及甲醛浓度&#xff0c;当超过设置的最大值时&#xff0c;进行报警及通风和净化空气处理 可实现通过MQ-4测量甲烷浓度&#xff0c;当超过设置的最大值时&#xff0…...

day22二叉树part08 | 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点

**235. 二叉搜索树的最近公共祖先 ** 这里利用上了二叉搜索树的特性&#xff0c;从上到下遍历&#xff0c;最近的公共祖先一定是满足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下的一款 多模式编辑器 &#xff0c;可以用来写代码&#xff0c;是 vi 的升级版。 此时无法输入&#xff0c;需要切换模式。 如上图&#xff0c;i 就是切换成…...

长方形边框 上方中间有缺口 css

<div class"text_6">大234234师掌4234柜</div><div class"text-wrapper_1"><span class"paragraph_1">四川慧创云戈科技有限公司推出的“大师掌柜”&#xff0c;是一个以餐饮外卖为切入口&#xff0c;专注实体小店新零售…...

2024-05-29 架构-程序设计-思考

摘要: 最近在抽出时间做一个数据库的driver, 其中有些问题驱动的软件代码的思考&#xff0c;是很值得回味的。 做的系统&#xff0c;所思考的问题&#xff0c;所设计的解决方案&#xff0c;其实都是可以看作是对解决问题方式。而不仅仅是某个类库的API的使用&#xff0c;某个…...

关于网络的基础知识

大家好&#xff0c;在当今数字时代&#xff0c;网络已经成为我们生活中不可或缺的一部分&#xff0c;它连接着世界的每一个角落&#xff0c;让信息、资源和人们彼此之间无阻碍地交流和共享。然而&#xff0c;对于许多人来说&#xff0c;网络仍然是一个神秘而复杂的领域&#xf…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...