集训队作业解题报告

1、POI2004Tournament解题一、问题描述有 n(1 n 100000)个智能程序将参加淘汰赛。淘汰赛赛程设置如下：每次选择两个没有被淘汰的程序进行比赛，胜利的程序留下，失败的淘汰，比赛没有平局。比赛一直进行到只剩下一个程序，这个程序就是冠军。如果在以前的历史中，程序 A 战胜了程序 B，那么在这次比赛中 A 便一定能够战胜 B。如果在以前的历史中，程序A 和程序 B 之间没有比赛，那么在这次比赛中，既有可能 A 战胜 B，也有可能 B 战胜 A。因此合理的安排淘汰赛程可能使某个程序取得冠军。任务：给出你程序以前的比赛m(1 m 106)条(即 A 曾经战胜 B)，判断哪些程序有可能获

2、得冠军。首先分析哪些方法可以确定一个程序是否取得冠军：事实 1任意的生成一个赛程安排，然后计算出比赛的结果，这样取胜的程序便是一个可以取得冠军的程序，而且一定存在一个这样的程序。事实 2如果一个程序能够战胜一个可能取得冠军的程序，那么这个程序也能够取得冠军。证明如下：设 u 是一个能够取得冠军的程序，其他程序可以分成两类：一类程序是一定能够战胜 u的程序，令这类程序为 A；另一类程序是能够被 u 战胜的程序，令这类程序为 B。能够使 u战胜的赛程安排一定是：首先用 B 类程序战胜 A 类程序，然后用 u 战胜未淘汰的 B 类程序。令 v 是一个有可能战胜 u 的程序。如果 v 属于 A，那么可

3、以如下安排让 v 取得冠军：首先用 B 类程序战胜 A / v的程序，然后用 u 战胜 B，最后用 v 战胜 u。如果 v 属于 B，类似的也可以安排赛程使得 v 取得胜利。根据上述的两个基本事实，可以得到如下算法求解出所有能够取得冠军的程序：算法 11任意生成一个赛程，计算比赛结果，找到一个能够取得冠军的程序 u，令 W = u，L = L / u。转步骤 2。2若 L 中存在一个点 u，能够战胜 W 中的一个点 v，则 W = Wu，L = L / u，继续转 2。否则转步骤 3。二、问题分析3W 便是能够取得冠军的所有程序的集合。证明上述算法的正确性，只需要证明如果一个程序不能够战胜至少

4、一个能够取得冠军的程序，那么这个程序一定不会取得冠军结论 1。证明如下：反设这个程序 u 能够取得冠军，那么程序 u 在最后一场比赛中一定战胜了某个程序 v。根据假设，v 一定是不可能取得冠军的程序。而 v 战胜了除 u, v 外所有的程序，根据事实 1，这其中一定存在能够取得冠军的程序。因此 v 一定间接的战胜了一个能够取得冠军的程序，而根据事实 2，v 一定是一个能够取得冠军的程序。因此结论 1 成立。算法 1 是基于迭代设计的，步骤 2 的复杂度为 O(n)，而步骤 2 可能迭代 n 次，因此算法 1 的时间复杂度为 O(n2)。因此仍需对算法进行优化。算法 1 是以计算可能取得冠军的程

5、序为中心，若计算那些不能取得冠军的程序，那会怎样呢？结论 1 可以重新表述为：如果一个程序能够被所有可以取得冠军的战胜，那么这个程序一定不会取得冠军，否则一定能够取得冠军。因此每次找到一个能够取得冠军的程序 u 时，对所有一定被 u 战胜的程序进行标记。那些没有标记的程序一定能够取得冠军，而标记了的程序还需要继续检查。由此到以计算不可能取得冠军的程序为中心的算法：令 countu表示一定能够战胜程序 u 的可能取得冠军的程序的个数。V 表示程序的全集。算法 21任意生成一个赛程，计算比赛结果，找到一个能够取得冠军的程序 u，令 W = u，L = L / u。转步骤 2。2枚举 W 中的所有程

6、序 u，对 u 一定能够战胜的程序 v，且 vV，有 countv countv+ 1。转步骤 3。3令 L1 = 所有 countv = |V / L|的程序。W = L / L1，L = L1。若|W| 0，则转步骤 2，否则转步骤 4。4L 为所有无法取得冠军的程序的集合。而 V / L 便是所有能够取得冠军的程序的集合。分析算法 2 的时间复杂度：步骤 1 只需要 O(m)的时间复杂度。而每个程序最多在步骤 2 中处理一次，因此步骤 2的时间复杂度为 O(m)。在步骤 3 中，在 L1 中的程序一定被 W 中的所有程序战胜，因此找出L1 中的所有程序，只需要在 W 中任选一个程序 u，然后判断 u 一定能战胜的程序中哪些属于 L1。因此步骤 3 的时间复杂度也为 O(m)。对集合的操作可以用链表实现，链表删除和插入元素都为 O(1