Advertisement

UVa 1609 不公竞赛(Foul Play)

阅读量:

题意:
采用淘汰赛制进行n支队伍的比赛,在每一阶段中所有参赛选手都会被分配到一组进行对决,在决出胜者晋级进入下一阶段的比赛直至决出冠军为止。
已知各队之间的胜负关系(不存在平局的情况),你 particularly关注一号队(记为T1),但他并非最强的一方;然而T1仍然可以直接击败其他至少一半的对手(即数量上不少于总对手的一半)。同时,在那些无法直接击败T1的一号强手ti(i=2,3,...,k),总能找到一支Tj(j≠i)已经被T1淘汰过的参赛者ti' ,使得ti' 能够直接击败ti并晋级下去;最终需要你根据以上要求设计具体的比赛对阵表。(以示例为例:当n=8时,请依次列出各轮的比赛对阵情况)

分析:
条件1:Team 1 consistently defeats at least half of the opposing teams.
条件2:Within the teams that have been defeated by Team 1, there will inevitably be some that can defeat the teams they cannot defeat in their own contests.

只要保持这个条件总存在,就可以递归。

step1: 选出一号队可以打败的队伍t’ 使得t’ 可以打败t 但是一号队打不败

全部评论 (0)

还没有任何评论哟~