mcfx's blog

题解、Writeup、游记和碎碎念

一个有趣的问题的(部分)证明

http://ljt12138.blog.uoj.ac/blog/5059

对于第二个问题,当 n8n\ge 8 时,可以如下构造:

对于 11 的个数为偶数和奇数的两种数,按 11 的个数从小到大,其次大小从大到小排序。pp 个人在偶数堆中从前向后选,qq 个人在奇数堆中从后向前选。

显然只需要验证 p+q=2n3p+q=\lfloor\frac{2^n}{3}\rfloormax(p,q)2n2\max(p,q)\le 2^{n-2} 的正确性。

用程序可以容易的证明 nn 较小情况的正确性(https://paste.ubuntu.com/p/XndFcftKF9/)。

pp 个人中最后一个选择的数 xx11 的个数为 iiqq 个人中最后选择的数 yy11 的个数为 jj,那么显然 j>ij>i

j>i+2j>i+2 时,显然不会有数相邻;而 j=i+1j=i+1 时,只要证明 x>yx>y,那么 yy 去掉某个 11 之后一定比 xx 小,也就证明了不可能有两个数相邻。

只要预处理组合数,就可以在 O(n)O(n) 时间内知道某个 xx 对应的 yy,然后再找到比这个 yy 小的最大的 xx,这样不停迭代,最终就可以验证这个的正确性(https://paste.ubuntu.com/p/gHmTyZbvGr/)。

日期: 2019-06-05

标签: 算法

这是一篇旧文,原始文章及评论可在 https://oldblog.mcfx.us/archives/265/ 查看。