圣诞礼物xmas解题报告

1、圣诞（xmas）解题摘要题意简述（略，见原题）分析初步算法构造首先，明确一下，由于题目中叙述的圆盘是环状的，不好描述，所以一个线性的数组来，即随便确定 A1为圆盘 A 上某个银针的长度后，依次顺时针向后的银针长度分别是 A2,A3AN，同样可以确定描述 B 盘的状态的数组 B。但是这样的描述方法忽略了“圆盘是圆的”这个公理因此它是可以转动的。于是，以数组 A 为例，若将 A2描述的银针作为另一个数组 A描述的第一个银针：A1=A2，以后以此类推：A2=A3，A3=A4，AN=A1，那么虽然 A 和 A是不相等的，但它们描述的却是同一个圆盘，也可以说他们是“循环同构”2的。于是，圆盘 A 的一次

2、循环 A(1)为上述的 A，即将圆盘 A 逆时针转一格得到的描述，读作“A 的一次循环”。同样 A(2)为 A(1)的一次循环，并可以推出 A(k)是 A(k-1)的一次循环，特别的 A(0)就是 A 本身。于是，很容易指导 A 的不同的描述方法一共有 N 种：A，A(1)，A(2)，A(N-1)。同样，可以得出一个结论，A 和 B 是循环同构的，即有 A(k)=B，0kN-1，3这里的 k 就是测试文件 xmas.in 的中的 M，而的目的也正是寻找这个 M！于是，可以得到比较容易的 O(N2)算法：首先设指针 p 从 0 开始，试探性的 Drop，看看 B 盘的状态是不是 A(0)，如果失

3、败，指针 p 加 1，此时有了 A 盘状态是 A(0)时的返回值，那么就可以判断 B 有没有可能是 A(1)，4如果 A(1)有可能与 B 相等，则将 A 盘转到 A(1)状态再次 Drop 试探，否则将 p 继续向后移动，直到找到一个 A(p)，满足以前所有调用 Drop 的返1234这里的LIMIT 是程序中定的一个次数上界，具体解释详见下文。关于循环同构概念的定义，可以参看今年集训队中以后表示循环次数的上标字母，若不加特殊说明，则范围均为0,N-1。这个判断方法比较简单，只要设A(1)是B 盘，A(0)是 A 盘，一次 O(N)级的模拟求得一个 Drop 后返回值并判断是否和真实值相等即

4、可。算法普通 O(N)筛法优化后的算法基本思路筛筛时间复杂度O(N)O(LIMIT)1空间复杂度O(N)O(N)回值，那么就将 A 盘转到 A(p)状态，并再次试探性的 Drop，这样将指针 p 不停的向后滑动，每次发现一个满足以前所有 Drop 返回值的状态 p 就再次试探的 Drop，最后总能找到题目中给出的 M。这种算法充分利用了以前给出的信息，完全有能力在 5 次 Drop 以内找到 M，但是由于题目中给出的 N 高达 100 000，O(N2)的算法显然是不能接受的！新思路的提出上面的 O(N2)算法优点在于充分利用了以前询问的信息，但是这也是它最大的弱点，由于其“贪婪”的使用了全部

5、信息，不可避免的花费了很多时间。于是少用一些信息，提高一些效率！的新思路就是，设某次 Drop 的返回值为 d，那么这个最大值 d 一定只可能是 A 盘中长度为 N 的银针对应插到 B 中深度为 N-d 的孔，或是长度为 N-1 的针插到深度 N-d-1 的孔，或是，或是长度为 d+1 的针插到深度为 1 的孔。下面分步处理上述的每一种情况，设有函数 indexA，是 A 的反函数，即有对任意 x1，N，indexAAx=x，同理设有 indexB。那么当前处理 A 中长度为 len 的针对应插到 B 中深度为 len-d 的循环同构的，成立的。的情况，d+1lenN。也就是 indexAle

6、n=indexBlen-d。由于 A 和 B 是很容易可以推出 B 中对应 A1的位置 q，也就是说 A1对应 Bq是可能设当前有根据以前的 Drop 得到的信息可以得出这样一个集合：Q=q|A1与 Bq对应有可能是成立的这样可以根据新的一次 Drop 得到的信息，求出根据本次信息得到的所有可能的 q 的集合 Q。在用它与已知的可能的对应集合 Q 求交集：集合。Q，就可以得到新的可能位置的如此一次次的在已知的集合 Q 中选择一个元素，并将 A 转到对应的位置并试探的 Drop，然后得到新的集合，并再选一个元素一次次的缩小 Q 的范围，最后总能找到确定的 M。来看看这个算法为什么优秀：算法询问效

7、果上，由于在一般随机数据中，每次 Drop 的返回值都非常大，于是上文说的最大值的产生情况就非常少，于是 Q中的元素就很少，理所当然的，新得到的 Q 的范围大大缩小了。在时间效率上，由于每次“筛”的过程中，算法只关心如何产生最大值，但是某种对应情况可能产生了比返回值还要大的长度，不符合已知的信息，但是算法仍然予以保留，也就是说浪费了一些信息，但是了一阶，可以说是得大于失！却将时间复杂度降算法的改进在大多数情况下，这个算法它都能在 5 次 Drop 以内出解，解决的测试数据也是轻数据，一般的在 Q 中选取而易举，但是一些数据却能让它为力。如附件中的最小元素的程序（不加随机化）大概需要 log2N

8、 次才能够出解，当 N 达到极限的时候，显然不能够满足题目的要求。即使在程序中加入了随机化，其还是有出现超过 5 次的概率的！由于的知识有限，无法估计算法情况下算法需要询问的次数，即使是原始的 O(N2)算法。但是可以做到的是降低算法在就是加入一定的优化。优化策略一就是随机化啦，这是非常有效的，如果不加，一些数据就会必定超过 Drop 次数，加入环境下询问次数超过 5 次的概率，也了随机化，就很难找出使算法失败的数据那么你只能靠运气了，当然如果加上了下面的优化，你的运气会越来越好！优化策略二这是一个非常小的优化，但是似乎效果非常好，有的时候算法本次询问了 A1对应 Bq的情况，但是在筛的过程中

9、，q 却没有被筛去！于是优化策略三的任务就是q！比较强的一个优化了，上文的，一般随机数据中，Drop 返回的值一般都很大，但在一些数据中，可能并不尽如人意。但是当返回值不大的时候何不从来看问题：同样设返回值为 x，那么 A 盘中长为 N 的银针对应 B 盘中深度小于 N-x 的孔的情况都是不可能的！如果 x 比较小，虽然正面的筛法不如人意，但是的范围，就可以筛掉一大堆不可能的情况！来看，1(N-x)却是一个可观当然，每次 Drop 以后总是以 A 盘中的长为 N 的银针来筛显然不是很好，同样可以使用随机化算法，附件中的程序就是每次 Drop 以后在(N-9)N 中任选一个来筛的。优化策略四也是

10、一个强劲的优化！其实当 N 比较小的时候，O(N2)的算法还是非常优秀的（不妨称为原始算法），于是想到是否可以在程序中点缀似的添加一些原始算法的呢？感觉上这个非常奇妙！其实际效果也是非常好的。实现上，这么做：每次 Drop 以后，先使用上面的所有方法筛一遍，在最终的集合中选择一些点用原始算法来检查，当然，总步数优化策略五过一个上限否则就超时了。终极优化！这个优化是建立在上面的优化（策略四）基础之上的，即对优化策略四的一些改进。一般来说，大家在使用该策略的时候，为了编成简单，都不自觉地这样实现：每次找到一个最小的，然后利用从前每次 Drop 得到的信息，试图筛去 q 这个元素，（当然，有些信息可

11、能在上一轮的筛中被使用过，则不需要再次利用）。这种方法看上去十分正确，但是仔细一分析，还是有一些之处的：其最大的缺点在于将 Q 中的一部分元素（设为集合 P）利用以前的所有 Drop 信息用原始算法筛了一遍。由于原始算法在筛的效果上是最好的它充分利用了一次 Drop 得到的所有信息。因此某个元素经过一次原始算法的考验（也就是仅使用一次 Drop 的信息）而没有被筛去，可以认为这个元素与最终的差距是非常小的。于是在本轮 Drop 之后的优化策略四中，大可不必再利用其他几次 Drop 的信息使用原始算法，而留下使用原始算法的机会给 Q 中的其它元素。关于测试其实，O(N)级的普通算法加上一般的随机

12、化在中已经完全够用了，但是本着精益求精的精神，还是对这个算法做了不少优化。优化后的算法效果如何？还是要看实际运行情况。因此测试这个环节还是非常重要的，大体是这样：被测试程序有两个，一个就是的主角，xmas.dpr，最终版本，还有一个是对照的版.dpr，就是首先提到的 O(N)级算法再加上一般的随机化。本，测试点总共有 2 个，首先的一个是数据中 N 达到极限（100 000）的随机测试点5，还有一个是情况6。具体测试过程：对每个程序，每个数据，均执行 1000 次，下程序需要的询问次数，56也就是xmas6.in。这里要感谢同学提供这个数据。分为 1 次，2 次，3 次，4 次，5 次和超过

13、5 次六种情况，最后统计出每种情况出现的概率，以便比较两个程序的优劣，同时由于没有完成感到很遗憾，这也算是一种补偿吧。的“估算程序情况需要次数”，具体及对的分析见附表。小结本次冬令营出现了很多开放性题目，本题也算是一例，虽然算法并不保证正确出解，只能通过随机化来“碰运气”，但是通过优化，可以将运气的干扰降低到最小比例。当然，值得一提的是，上文中提到的“少用一些信息，提高一些效率”是一种非常优秀的，在以后的交互式题目中，应该会有着广泛的应用，值得大家注意。附：程序附：测试情况1 原始数据表格：（统计出现次数）2 概率统计表：（统计出现次数概率）7多于 5 次的按 6 次算，对整体结果影响不大。测

14、试点程序随机数据数据.dprxmas.dpr.dprxmas.dpr1 次0%0%0%0%2 次0%1.1%0%1.3%3 次0.4%90.3%35.8%74.5%4 次56.4%8.6%44.4%21.9%5 次43.1%0%17.7%2.2%多于 5 次0.1%0%2.1%0.1%平均次数74.4293.0753.8613.253测试点程序随机数据数据.dprxmas.dpr.dprxmas.dpr1 次00002 次0110133 次49033587454 次564864442195 次4310多于 次算法普通 O(N)筛法优化后的算法程序附：测试情况分析首先说一下设计的两个测试数据的侧重点。随机数据主要的是程序平均询问次数，而数据则是专门设计的，重在程序不出解（即询问次数多于 5）的概率：如果在运气很差的时候，未优化的程序最多可能询问 log2N17 次左右。（当然，这种情况在优化后的程序中根本不可能出现。）下面来看一下的随机数据上，从：来看，两个程序的不出解概率分别为 0.1%和 0%，可以视为在时不可能出现。但是来看平均次数，未优化的程序平均询问次数高达 4.429 次，基本快要到达 5 次！而优化后的程序的平均次数则只有 3.075 次。数据