15楼. 对于第一题:
题目虽然跟海盗分金币的解题思路差不多,都是逆推,
但数据量明显大了很多。
为了解题叙述方便,
将54321改为12345
即得分最大(排位最后)的淘汰。
得分小的(排位靠前)的下轮先选择。
我的祖国✨ 2018-7-20 回复 16楼. 以下出现蓝色的情况,选择人不会选择,因为最终路线不是最优路线。
剩余两人时,两次交换,不影响排位,12还会是12
图剩余三人时,为下轮优势,第一目标抢排名1,第二目标抢2,第3的被淘汰,
123会被抢成321
我的祖国✨ 2018-7-20 回复(2) 17楼. 剩余4人时的分析结果:
图剩余四人时,为下轮优势,第一目标抢排名3,第二目标抢2,第三目标1,第4被淘汰,
1234会被抢成1423
我的祖国✨ 2018-7-20 回复(1) 18楼. 五人正常选择结果:
图图剩余五人时,为下轮优势,第一目标抢排名4,第二目标抢3,第三目标1,第四目标2,第5淘汰,
12345会被抢成52134
所有黄色是可行线路,蓝色会被所在轮选择放弃,后续不能执行。
正常情况下
abcde→cbde(a)→cde(b)→ed(c)→e(d)
淘汰顺序为abcde。
我的祖国✨ 2018-7-20 回复(8) 19楼. 但实际上现在有人参与帮忙,淘汰顺序为dbcea,
分析第一轮的最终排序为cbead,对应图表的最终编号为42153,
如果e参与帮忙,上一轮应该是32154(否),43152(否),42351(否),42135(存在,只要第一步a没有和e交换都成立,况且a不会第一步就将自己换成排最后,弄得濒临出局的局面),所以e帮了a是成立的。后续几轮e都不用帮忙了,正常进行就会得到要求的结果。
如果e没帮忙帮忙,d留给e的顺序是32154(e在选择前的位置最有利,但必须交换,不得不将最优位置换给了a,自己选择第二有利位置),强迫e选择了和a交换变成42153,所以d在选择前的数据为52134(否),35124(否),32514(否),32145(存在,只要第一步a没有和d或e交换都成立,况且a不会第一步就将自己换成排最后,弄得濒临出局的局面,同样a不会直接选择最有利位置4,将自己树立成靶子,)所以d帮了啊,牺牲了自己,也成立。
如果de都是正常的,d是不可能第一轮就出局的。
因为bcde都没有得益,所以不可能是有人帮b或c或d或e的。
综上所述,d或e帮了a,都会出现这个结果。
我的祖国✨ 2018-7-20 回复(11) 21楼. 我想知道第四题对一般情况只问个上界是不是因为具体答案难以计算?
我可以给一个很大的上界。考虑一般n边形,对折一次。显然折线最多与每条边相交一次,于是形成了n条“新边”;显然“新边”之间不会相交于除顶点外的点。于是每条“新边”最多与n条“旧边”各相交一次,有n个交点。这n个交点把每条“新边”最终变为n^2条新边(应该可以证明)。同样每条“旧边”也变成n^2条新边。因此对折后多边形的边数的一个上界是2n^2。
迭代之后,4边形对折n次可以形成……
f(0)=4
f(n+1)=2*f(n)^2
没算错的话f(n)=2^(2^n-1)*(4)^(2^n-1)
这应该是一个上界……
东山老僧 2018-7-21 回复(2)