解题报告圣诞礼物

1、圣诞解题湖南沙郡中学【问题描述】给出上下两个圆盘，有互补结构：上面的圆盘的圆周上排列着长度不同，且长度在 1.n 之间的针,下面圆盘的圆周上有对应深度的孔，当两个圆盘都在初始的位置时，两个圆盘可以完全的吻合，但是先将下面的圆盘转动了若干的位置，使得两圆盘不一定对应起来。现在你可以向左转动上面的圆盘若干位，或 drop上面的圆盘，将上面的圆盘压下来，如果完全吻合，完成任务；否则，诉两个圆盘此时的距离，因为上面的圆盘不可能完全的压下来，有些孔的深度比针的长度小。问题是要你最多 Drop 5 次就完成任务。详细内容，见问题描述 圣诞【问题分析】此题是交互式试题。首先注意到问题限定程序在 5 次 dr

2、op 内完成任务，就会想是否有很好的构造解法，但很遗憾，从题目中找不到什么规律。那么就只有依靠筛选法了，如何筛呢？是否可行？设上方圆盘为圆盘 1，下方圆盘为圆盘 2。设S0 表示初始状态，Si 表示由初始状态向左转动 i 位得到的圆盘的状态，Sip表示Si 状态的第 p 位的高度绝对值(凸出为正，凹入为负)。设 Xi 集合为满足前 i 次 drop 结果的圆盘 2 可能状态的集合。下面给出解题的基本流程：1i0，X0 = S0.Sn-1。2选Sj Xi, 将圆盘 1 转动到Sj。3k = drop，如果 k = 0, 自动退出；否则，继续执行。4Xi+1 = ;5对于所有的SpXi，如果 hp

3、, j = k，则Xi+1 = Xi+1 + Sp。6i i+1，转入 2。其中的 hj, p表示：如果圆盘 1 状态为Sj，圆盘 2 状态为Sp 时，压下上面圆盘后，两圆盘的距离。计算式为：如果确定了第 2 步的选择后，此算法是不是基本上就完工了呢？若不考虑时间复杂度，上面的算法是可行的。基本上对于所有的情况，最多只要 drop3，4 步左右就可以完成任务。上面的筛法效率很高，每次被筛掉的元素很多，当 N=100000 时，一般只要筛一次就只剩下几百个元素了。因此，此算法对任何数据基本上可保证程序在 5 次 drop 内完成任务。但是看流程的第 6 步，发现此算法的时间复杂度为 O(N2)，

4、还是太高了！这个时间复杂度是承受不了的！关键原因就是 h 的求解太繁琐了。但是此时没有更好的 h 的求解方法，那么是否可以不通过 h 来判断某个状态是否满足要求呢？这种想法是可行的！分析一下：如果当前将圆盘放下后，得到两圆盘间的距离为 k，那么下面圆盘的可行的状态有哪些呢？可能的状态只能是：圆盘 2 深度为 1 的孔和圆盘 1 长度为 k+1的针相对（简记为 1 对 k+1），此外还有 2 对 k+2，3 对 k+3 nk 对 n。例如圆盘 1 的当前状态为：3 4 2 5 1，k = 2。那么圆盘 2 的可行的状态为： 1 3 4 2 5，4 2 5 1 3，2 5 1 3 4。根据圆盘1

5、的当前状态和k 就可以算出满足当前下压情况圆盘2 的可能状态，这样就可以筛掉一些不满足情况的状态。那么如果按照上面的筛选方式，复杂度就仅为 O(N)。不妨把此种筛选法称为k 值筛选法。但是发现，上面的筛选方式并不完全准确的，因为并不是通过上面筛选的状态就是满足当前 Drop 值的情况的状态，比如上的例子中的圆盘 2 的状态 4 2 5 1 3，就不是可行的状态，因为这种情况下，两圆盘的距离为 4，不等于 k, 实际上是不满足此次 Drop 值的。所以说明这种判断方式筛得不很干净。实际上用 k 值筛选法来做的效率并不高，很多的情况下，Drop 的次数在 4次以上，怎么办？可以求出近似的 h 值，

6、用这个近似的值来筛选：当计算 hj,p（即上下两圆盘的分别在Sj, Sp 状态下两圆盘的距离）时，不考虑所有的针，只考虑圆盘 1 最长 10 根针分别此时正下方的（可以根据Sj, Sp 算出此时每根针下方的孔的深度），多长在外面，如果这 10 根针所剩长度的最大值已经超过了 k（当前两圆盘的距离）,那么就可以判断足要求的状态。同理，可以考虑圆盘 2 最浅的几个孔的情况。Sp 是不满由于 10 是常数，那么此筛选法的复杂度还为 O(N)的。这种筛选法叫部分筛选法。这种筛选法也是确，但是因为考虑的是最长的10 根针和最浅的10 个孔，所以排除不合理状态的效率还是比较高的。但是一般不会单独使用此筛选

7、法，可以先用 k 值筛选法，再用部分筛选法，这样两者结合后就得到了比较好的效果，这样结合后的筛选法，统称为 k-部分筛42 53 4 2 5 1选法。这种 k-部分筛选法的效率很高, 对几万个随机数据都可以在 4 次 Drop 内解决。由于上面的两种方法都不是最准确的，所以为了更加的保险，考虑先用 k-部分筛选法，再用 h 值筛选法筛一遍。但是这样并不好，实际情况表明，在进行完了第一次 k-部分筛选法以后，还可能剩下很多的状态，这个时候用 h 值筛选法在时间上是通不过的。而一般的进行了 2，3 次 k-部分筛选法以后，剩下的状态已经相当的少了，这时再用 h 值筛选法加工是比较理想的。那么可以这

8、样重新组合一下：在第一次的筛选中，仅用 k-部分筛选法筛选，在以后的筛选中，先用 k-部分筛选法筛选，再用 h 值筛选补充筛选。N2这样三种筛法结合起来后，用 h 值筛选法时的实际计算总次数就达不到了，时间上基本达到了要求， 而同时又可以尽量完全的筛掉了不满足情况的状态，实际运行效果也相当的好。【小结】此题用了几种筛选的方法，各种方法各有千秋，所以要取短，同时筛法是解决交互式问题一种重要方法。，补己之【程序】uses xmas_p; constinputfile = xmas.dat; maxn = 100000;vartime, m, min, l, max, tp, t, k, n, i,

9、 j : long;x, c, a, b : array0 . maxn of long;a, 表示初始的针的状态，x表示当前情况下可能状态集合，b 表示各根长度的在初始状态中的位置procedure minus_h; begintp := 0;for i := 1 to t doif cxi 0 then beginmax := 0;for j := 0 to n - 1 doh 值筛选if aj - a(j + xi) mod n max then beginmax := aj - a(j + xi) mod n; if max k then breakend;if max = k the

10、n begininc(tp); xtp := xi endend; t := tpend;procedure minus_some;部分筛选法var d : begineger;if n 10 then d := 10 else d := n; for i := 1 to t doif cxi 0 then beginmax := 0;for j := n downto n - d +1 doif abj - a(bj + xi) mod n k then break;if abj - a(bj + xi) mod n k then cxi := 0; for j := 1 to d doif

11、 a(bj - xi + n) mod n - abj k then break;if a(bj - xi + n) mod n - abj k then cxi := 0 end;end;beginstartgame;assign(input, inputfile); reset(input); readln(n);for i := 0 to n - 1 do beginread(ai);bai := i end;close(input);randomize;roe(random(n - 1) + 1); k := drop;fillchar(c, sizeof(c), 0); for i := k + 1 to n doc(bi - k - bi + n) mod n := 1;k 值筛选minus_some; t := 0;for i := 0 to n - 1 do if ci 0 thenbegininc(t); xt := i end;while k 0 do beginl :