文章目录

UOJ #282 长度测量鸡 做题笔记

发布于

题意

给出一个长度为 $\dfrac{n\left(n + 1\right)}2$ 的直尺,要在 $0$ 和 $\dfrac{n\left(n + 1\right)}2$ 之间选择 $n - 1$ 个刻度,使得 $1$ 到 $\dfrac{n\left(n + 1\right)}2$ 中任意一个长度都可以由某两个刻度(包括 $0$ 和 $\dfrac{n\left(n + 1\right)}2$)之间的距离表示出来。问是否有解。

$1 \leq n \leq 2500$

题解

首先结论:仅当 $n \leq 3$ 时有解。
当 $n = 1$ 时可以直接量出来。
当 $n = 2$ 时可以分为长为 $1$ 和 $2$ 的两段。
当 $n = 3$ 时可以分为长为 $1, 3, 2$ 的三段。

证明 $n \geq 4$ 时无解:
为方便下文描述,设 $l = \dfrac{n\left(n + 1\right)}2$。
首先,$\dbinom{n + 1}2 = l$,个长度只能用一种方式表示。
当 $n \geq 4$ 时,$l \geq 10$

现在需要表示 $l - 1$,因此 $1$ 或 $l - 1$ 有刻度。由于对称可以设 $1$ 有刻度。同时还可以测量出长度 $1$。
现在需要表示 $l - 2$,因此 $2$、$l - 2$、$l - 1$ 中必有一个刻度。而 $2$ 和 $l - 1$ 会让 $1$ 可以被再次表示。所以只能选择 $l - 2$。同时,$2$ 和 $m - 3$ 也能被测量出。
现在需要表示 $l - 4$,同理,只能选择 $4$。同时,$3$、$4$ 和 $m - 6$ 也能被测量出。
现在需要表示 $l - 5$,此时 $3, 5, l - 5, l - 4, l - 1$ 中必有一刻度。分析可得,这些点都不能选。

因此不能表示 $l - 5$。
而 $l \geq 10$,所以可以表示的 $1, 2, 3, 4$ 都不是 $l - 5$。
所以 $n \geq 4$ 时无解。


暂无评论

发表评论