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

集训队作业1——qoj#11722

news 2026/6/13 11:56:20

Hamilton 解题报告

题目大意

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

$\forall 1\leq i<n$，$(i,i+1)$ 之间有边权为 $0$ 的边；
$\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$ 的情况：

只有 $a\leadsto b$，此时要求 $a=1,b=n$。

答案为 $1$ 的情况：

$a\leadsto 1\Rightarrow n\leadsto b$，此时要求 $a+1=b$；
$a\leadsto 1\Rightarrow a+1\leadsto b$，此时要求 $b=n$；
$a\leadsto b-1\Rightarrow n\leadsto b$，此时要求 $a=1$ 且 $\gcd(n,b-1)=1$。

答案为 $2$ 的情况：

$a\leadsto 1\Rightarrow b-1\leadsto a+1\Rightarrow n\leadsto b$，要求 $\gcd(a+1,n)=1$；
$a\leadsto 1\Rightarrow a+1\leadsto b-1\Rightarrow n\leadsto b$，要求 $\gcd(b-1,n)=1$；
$a\leadsto b-1\Rightarrow 1\leadsto a-1\Rightarrow n\leadsto b$，要求 $\gcd(a-1,n)=1$；
$a\leadsto b-1\Rightarrow a-1\leadsto 1\Rightarrow n\leadsto b$，要求 $\gcd(a-1,b-1)=1$；
$a\leadsto 1\Rightarrow b+1\leadsto n\Rightarrow a+1\leadsto b$，要求 $\gcd(a+1,n)=1$（这实际上和1解决的是同一种情况）；
$a\leadsto 1\Rightarrow n\leadsto b+1\Rightarrow a+1\leadsto b$，要求 $\gcd(a+1,b+1)=1$。
还有部分 $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$ 的情况）：

$n$ 为奇数：$1\Rightarrow b-1\leadsto 2\Rightarrow n\leadsto b$；
$b$ 为偶数：$1\Rightarrow n\leadsto b+1\Rightarrow 2\leadsto b$。

对于 $a>1$（权值和为 $3$）：

$n$ 为奇数：$a\leadsto2\Rightarrow n\leadsto b+1\Rightarrow 1\Rightarrow a+1\leadsto b$；
$b$ 为偶数：$a\leadsto2\Rightarrow b+1\leadsto n\Rightarrow 1\Rightarrow a+1\leadsto b$；
$a$ 为偶数：$a\leadsto2\Rightarrow a+1\leadsto b-1\Rightarrow 1\Rightarrow n\leadsto b$；