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\);
除了分类讨论外,另一种可能的思路是暴力枚举断边(上面用到的断边只有五种可能)并枚举每段之间的顺序、每段内的方向并检验,可以避免讨论。
参考资料
无。