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

集训队作业1——qoj#11722

Hamilton 解题报告

题目大意

以如下方式给出一张带权无向图:点集为 \(\{1,2,\dots,n\}\),边有两种:

  1. \(\forall 1\leq i<n\)\((i,i+1)\) 之间有边权为 \(0\) 的边;

  2. \(\forall 1\leq i<j\leq n\)\(\gcd(i,j)=1,j-i>1\)\((i,j)\) 之间有边权为 \(1\) 的边。

现在给定起点 \(a\) 和终点 \(b\) (保证 \(a\neq b\)),构造一条从 \(a\) 开始,以 \(b\) 结束的权值和最小的哈密顿路径(即经过每个点恰好一次),或报告无解。

\(2\leq n\leq 2\times10^5\)\(1\leq a,b\leq n\)

解题过程

不妨设 \(a<b\),否则交换 \(a,b\) 并将路径首位翻转即可。

观察到边权为 \(1\) 的边实际上是很多的,所有可以猜想路径权值和较小。注意到路径权值和实际上就是有多少条 \((i,i+1)\) 的边没有经过,称种边为"断边"。由于 \(a,b\) 为路径端点,所以 \((a,a+1)\)\((a-1,a)\) 中至少一条断边,\((b,b+1)\)\((b-1,b)\) 中至少一条断边,即当 \(1<a<b<n\)\(b-a>1\) 时答案至少为 \(2\),故可以分类讨论所有答案不超过 \(2\) 的情况。

(下文中 \(a\to b\) 表示边权为 \(0\) 的边,要求 \(|a-b|=1\)\(a\Rightarrow b\) 表示边权为 $1 $ 的边,要求 \(\gcd(a,b)=1\)\(a\leadsto b\) 表示通过 \(0\) 的边从 \(a\)\(b\) 的路径,即 \(a<b\) 时为 \(a\to a+1\to\dots\to b\)\(a>b\) 时为 \(a\to a-1\to\dots\to b\)\(a=b\) 时即表示单点 \(a\)):

答案为 \(0\) 的情况:

  1. 只有 \(a\leadsto b\),此时要求 \(a=1,b=n\)

答案为 \(1\) 的情况:

  1. \(a\leadsto 1\Rightarrow n\leadsto b\),此时要求 \(a+1=b\)

  2. \(a\leadsto 1\Rightarrow a+1\leadsto b\),此时要求 \(b=n\)

  3. \(a\leadsto b-1\Rightarrow n\leadsto b\),此时要求 \(a=1\)\(\gcd(n,b-1)=1\)

答案为 \(2\) 的情况:

  1. \(a\leadsto 1\Rightarrow b-1\leadsto a+1\Rightarrow n\leadsto b\),要求 \(\gcd(a+1,n)=1\)

  2. \(a\leadsto 1\Rightarrow a+1\leadsto b-1\Rightarrow n\leadsto b\),要求 \(\gcd(b-1,n)=1\)

  3. \(a\leadsto b-1\Rightarrow 1\leadsto a-1\Rightarrow n\leadsto b\),要求 \(\gcd(a-1,n)=1\)

  4. \(a\leadsto b-1\Rightarrow a-1\leadsto 1\Rightarrow n\leadsto b\),要求 \(\gcd(a-1,b-1)=1\)

  5. \(a\leadsto 1\Rightarrow b+1\leadsto n\Rightarrow a+1\leadsto b\),要求 \(\gcd(a+1,n)=1\)(这实际上和1解决的是同一种情况);

  6. \(a\leadsto 1\Rightarrow n\leadsto b+1\Rightarrow a+1\leadsto b\),要求 \(\gcd(a+1,b+1)=1\)

  7. 还有部分 \(a=1\) 的剩余情况。

考虑剩余情况,即上面的互质条件都不满足,最简单的例子就是 \(n\) 为偶数,\(a,b\) 均为奇数。

简单举例尝试一下,可以发现这种情况似乎不存在构造。事实上,这就是本题的无解情况,证明如下:采用上面的“断边”来刻画哈密顿路径,那么每条断边的端点一定是一奇一偶,又因为 \(1\) 为奇数,\(n\) 为偶数,所以设断点将 \([1,n]\) 分成了 \(c\) 段(这意味着如果存在路径,版权和为 \(c-1\)),那么段的左右端点加起来共有 \(c\) 个奇数 \(c\) 个偶数。又因为起点 \(a\) 终点 \(b\) 均为奇数,所以剩余的 \(c-2\) 个奇数 \(c\) 个偶数分成 \(c-1\) 对,必然有一对偶数,那么此时就不可能互质,这两个点之间不可能存在边。

上面的证明也提示了考虑奇偶性,所以对于剩余的情况考虑将 \((1,2)\) 设为断边,这样 \(2\) 和所有奇数之间都有权值为 \(1\) 的边:

对于 \(a=1\)(这就是上面没讨论的权值和为 \(2\) 的情况):

  1. \(n\) 为奇数:\(1\Rightarrow b-1\leadsto 2\Rightarrow n\leadsto b\)

  2. \(b\) 为偶数:\(1\Rightarrow n\leadsto b+1\Rightarrow 2\leadsto b\)

对于 \(a>1\)(权值和为 \(3\)):

  1. \(n\) 为奇数:\(a\leadsto2\Rightarrow n\leadsto b+1\Rightarrow 1\Rightarrow a+1\leadsto b\)

  2. \(b\) 为偶数:\(a\leadsto2\Rightarrow b+1\leadsto n\Rightarrow 1\Rightarrow a+1\leadsto b\)

  3. \(a\) 为偶数:\(a\leadsto2\Rightarrow a+1\leadsto b-1\Rightarrow 1\Rightarrow n\leadsto b\)

除了分类讨论外,另一种可能的思路是暴力枚举断边(上面用到的断边只有五种可能)并枚举每段之间的顺序、每段内的方向并检验,可以避免讨论。

参考资料

无。

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

相关文章:

  • 如何设置将浏览器网页临时禁用网页mathjax渲染直接查看latex编译前的文本
  • 《IDEA 2025破解 长效使用指南:2099 年有效期配置实战之JetBrains全家桶有效》​
  • Helloworld
  • 基于菲涅尔积分的角锥喇叭方向图计算
  • Flask的ORM工具SQLAlchemy
  • 使用 Rust 和 Tesseract OCR 实现英文数字验证码识别
  • 构建复合AI系统以实现可扩展工作流
  • Python HTTPS 爬虫实战,requests aiohttp Selenium 抓取技巧、HTTPS 问题与抓包调试(python https爬虫、反爬、抓包、证书处理)
  • GreatSQL 优化技巧:最值子查询与窗口函数相互转换
  • Windows Time 时间同步时出错
  • CCS开发环境和TMS320系列DSP实现IP-IQ谐波与无功电流检测
  • 多机动模型PHD滤波算法
  • Navicat17无限试用重置14天
  • 基于Electron的Web打印解决方案:web-print-pdf技术分享
  • CF455D Serega and Fun
  • 实验任务
  • 61.【.NET8 实战--孢子记账--从单体到微服务--转向微服务】--新增功能--提取金额 - 实践
  • 使用 Ansible 部署 Elasticsearch 集群
  • 免费无广告!这款开源工具让文件转换像复制粘贴一样简单!
  • 时序InSAR形变结果合并操作说明 - ENVI
  • CSP-S 2025 #2
  • 完整教程:38.应用层协议HTTP(一)
  • 在Vue.js中设置方法时访问$vuetify实例
  • 纷享销客CRM任务系统:破解快消品终端动销管理难题
  • 第一周博客作业-介绍自己
  • AI大模型应用简介 - 努力-
  • React 基础核心概念(8 个)——从入门到能写业务组件(上)| 葡萄城技术团队
  • 2 day - when
  • 罗氏线圈选型技术指南:精准电流测量的关键抉择​​
  • 普科PK-CWT/150罗氏线圈在工业电机驱动保护中的应用方案