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

CF1882E1 Two Permutations (Easy Version)

题目大意:

有两个排列,长度分别为 \(n,m\),每次你可以选择两个整数 \(1 \le i \le n, 1 \le j \le m\),并交换 \(p_{1} \sim p_{i - 1}\)\(p_{i + 1} \sim p_{n}\) 两个整体,\(q,j\) 同理。
请构造出一种不超过 \(10000\) 的操作次数,使得 \(\forall p_{i} = i, q_{j} = j\)
\(n,m \le 2500\)

解题思路:

这种类型的构造题往往是可以通过想想自己希望的形态。
首先,我们并不知道两个怎么做,所以先考虑一个排列怎么做。

Solution 1:

因为排序,我们又只有 \(O(n)\) 步,所以考虑能否快速的交换两个数,并不影响其他的位置。
我们最多只有 \(4n\) 步来解决这个问题,而我们要交换 \(n\) 次,所以希望找到 \(4\) 步之内的方案,越少越好。

通过手模若干种方案,我们发现假设要交换 \(A,B\),只需要在 \(A\) 操作一次,在 \(B\) 操作一次,在 \(A\) 再操作一次就可以了。
那么我们做到了 3 步交换。

我当时自己想的时候只考虑了不超过两步的,应该只要不超次数就做下去...

Solution 2:

换一种方向考虑,相当于从大小的角度换成位置的角度,要让 \(i\) 出现在 \(i + 1\) 之前一个位置。
那么相当于每次把 \(i + 1\) 拼在 \(i\) 后面。

我们还是只有 4 次来解决这个问题,如何在不改变 \(1 \sim i\) 的时候将 \(i + 1\) 拼上。
观察操作,发现每次将 \(p_{x}\) 拼在了 \(p_{x + 1} \sim p_{n}\) 后面,那么我们考虑先将 \(1 \sim i\) 移到最后,然后再对 \(i\) 操作一次。
而将 "..." 移到最后,也可以通过观察操作,即将 \(p_{1} \sim p_{x-1}\) 放到了最后。
那么假设 \(1 \sim i\)\(l \sim r\) 这些位置上,我们可以对 \(p_{r + 1}\) 操作一次,再对 \(p_{j} = i + 1\) 操作一次。

这样就可以 2n 步了。

那么我们考虑将一个排列推展到两个排列,自然也会出现构造出来的次数不同的情况。
于是我们希望让快的那个等等慢的那个,也就是快的那个要做一些无用操作。

因为是交换的 \(p_{1} \sim p_{i - 1}\)\(p_{i + 1} \sim p_{n}\) 两个整体,所以重复做一次会直接还原。
那么对于步数同奇偶的情况我们解决了。

http://www.hskmm.com/?act=detail&tid=30077

相关文章:

  • 2025年10月实验室净化订做厂家最新推荐排行榜,专业定制与高效服务口碑之选
  • 20234320 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 2025年10月清洗机厂家最新推荐排行榜,高压清洗机,超声波清洗机,工业清洗机,商用清洗机公司推荐!
  • 2025年10月上海殡葬服务一条龙最新权威推荐榜:专业贴心的全程陪伴与优质服务厂家选择指南
  • [GenAI] 大模型微调
  • 2025年10月气柱袋厂家最新推荐排行榜,缓冲包装气柱袋,防震气柱袋,充气气柱袋公司推荐!
  • [GenAI] LoRA微调
  • 2025年10月保洁公司最新权威推荐榜:专业清洁与高效服务的品质之选
  • 2025年10月粉末涂料厂家最新推荐排行榜,环氧粉末涂料,聚酯粉末涂料,丙烯酸粉末涂料,耐候性粉末涂料公司推荐
  • 基于单片机的汽车防碰撞刹车系统(论文+源码) - 实践
  • git submodule
  • 2025年10月确有专长培训机构最新推荐榜单:专业课程与高通过率口碑之选
  • 有源探头DC与RMS参数详解:选型与应用指南
  • Objective-C Runtime 中的关联对象(Associated Object)方法
  • 2025年10月无锡公考培训机构最新权威推荐榜单:专业师资与高通过率口碑之选
  • 2025年10月防腐木厂家最新推荐排行榜,专业生产户外景观木材,品质卓越值得信赖!
  • 数据敏感型企业为何优选吱吱企业即时通讯?其私有化部署优势详解
  • 学习第一天
  • AIVILIZATION相关文件记录
  • 2025年10月上海门头清洗服务公司最新权威推荐榜:专业清洁与高效服务口碑之选
  • python实现全端口扫描
  • 详细介绍:如何分析软件需求中的DFX需求?
  • 2025年10月环氧板定制厂家最新推荐排行榜:专业定制与优质服务的口碑之选!
  • 2025年10月点胶机厂家最新推荐排行榜,自动点胶机,桌面点胶机,三轴点胶机,高精度点胶机公司推荐!
  • 在运维工作中,如何批量将当前目录下所有的 .tar 镜像文件通过 docker load -i 导入到本地 Docker 环境中,并显示进度和结果。
  • ffmpeg源码分析:avformat_open_input()打开媒体流
  • 01_数据库基础知识
  • 2025年10月农机带厂家最新推荐排行榜,农业机械传动带,收割机皮带,拖拉机皮带,耐用高效品质之选!
  • 2025年10月清洗机厂家最新权威推荐榜:高压清洗机,超声波清洗机,工业清洗机,家用清洗机品牌精选!
  • 2025年10月恒温恒湿系统厂家最新推荐榜单,精加工车间/厂房/美术馆/仓库/计算机房/档案室/工业/工厂车间恒温恒湿系统公司推荐