厦门大学“网宿杯“17届程序设计竞赛 F-这题多捞啊

这题多捞啊

https://ac.nowcoder.com/acm/contest/5945/F

数学

这一题我是列出一些例子后归纳猜出来的,,,,,,如果要证明的话,就我个人来说感觉还是有、难度的。
下面给出我的证明,并不严谨。

题意:
给定一个正整数n,请求出所有满足如下两个条件的正整数集合x[1],x[2]...x[n]:

  1. x[1]+x[2]+...+x[n]=2n
  2. 不存在一个划分将集合划分成和相等的两部分,也就是说,集合的任意子集和均不为n。
    请按照集合中元素升序排序后字典序从小到大的顺序输出答案,若不存在这样的集合请不要输出任何字符

分析

我们先拿一些具体的例子试一试吧,看能不能找到突破口。
n == 1 :[2]
n == 2 :[1,3]
n == 3 :[1,1,4] 、[2,2,2]
n == 4 :[1,1,1,5]
n == 5 :[1,1,1,1,6] 、 [2,2,2,2,2]
。。。。。。。。。
我们似乎得到了什么规律了
首先对任意n,[1,1,1,1,1,1,........,n+1]一定是正确的(n-1个1,1个n+1)
而当n为奇数时[2,2,2,2,2,2,2.....]也是正确的(n个2)
n==1时两者重合了
这两点都不难理解,重要的是接下来的一个归纳:
除了这两种其他的任何集合都会有和为n的子集,不满足情况!!!!!!!!!!!

下面我们来证明这个归纳!!
我们从这开始[1,1,1,1,1,1,.....,n+1] 这是我们目前的序列
我们有n-1个1,1个n+1
我们从n+1向前扔k个1, n>=k>=1
这k个1一共落在了b个位置上, k>=b>=1
那么我们现在还拥有:
A、n-1-b 个 1
B、一个 n+1-k
C、b个总和为k+b,单个最小为2的数
我们要证明这些数一定能凑成n
首先我们有了n-1-b个1了那么这意味着什么?
意味着如果我们用B和C中的元素凑成
[b+1,b+2,b+3,b+4,.......,n-1,n]
中的任意一个数值游戏结束!!!!!
而有趣的是,我们A,B,C中所有元素的数值总和为2n
那么B和C的元素的总和为2n - (n-1-b)
为n+1+b !!!!!!!!!!(看上面的区间)
正好为:(b+1) + n、(b+2) + (n-1)、(b+3) + (n-2) 、(b+4) + (n-3) 。。。。。。。
而B和C中至少也有两个元素,那么只要区间[b+1,b+2,b+3,b+4,。。。。n-1,n]
保持对称性的情况下,一定能找到n即一定不成立!!!!!!
那么什么时候不保持对称性呢?b+1 == n即b == n-1
也就是说,[1,1,1,1,1,......,n+1]最后一位向前n-1位都发了一个1
大家都变为了[2,2,2,2,2,2,2,2,2,2,.....]
n位奇数时true,为偶数时false
证明完毕!!!!!!!!!!

证明并不严谨,可能会有漏洞,,,,如果发现希望指出,谢谢

全部评论

相关推荐

杨柳哥:这不是普通人,那这个钱的是天才
点赞 评论 收藏
分享
冷艳的小师弟在看机会:jd测评乱点直接被挂了,哭死~
点赞 评论 收藏
分享
蚂蚁 基架java (n+6)*16 签字费若干
点赞 评论 收藏
分享
2 收藏 评论
分享
牛客网
牛客企业服务