论简单单淘汰赛制在icpc中的应用与解决方案 |
您所在的位置：网站首页 › icpc竞赛赛制 › 论简单单淘汰赛制在icpc中的应用与解决方案 |
|
简单单淘汰赛制，即一些队伍两两比赛，一次直接淘汰败者，最终剩下一个队伍的赛制 在acm中我们有时候会遇见要解决此类问题的题目，对此有些心得想写下来 简单分析：首先分析这种赛制需要计算的答案 可能是最终的胜者是谁，每个人获胜的概率是多少 再来分析这个问题的本质，实际上因为每个人只要输一次就会不再参加比赛，即每次数量减少的总是当前参赛者的1/2，那么就可以很好的用一棵二叉树表示，暂且不考虑轮空的情况，也就是参赛总人数为2的次方，那么这棵树就会是一棵满二叉树，对数据结构有所了解甚至说只用知道递归就可以很轻松的从条件中寻找出结果，直接build一棵满二叉树及其容易，叶子节点有n个（叶子节点代表的就是初始状态），满二叉树的大小（总节点数）就为n*2-1，那么复杂度就是总节点数（每个节点只用遍历一次就可以知道它的状态） void build(int pos, int l, int r) { if (l == r) { p[pos] = a[l];//p是树的节点，l是原序列 return; } int mid = l + r >> 1; build(pos 1; build(lson, l, mid); build(rson, mid + 1, r); pushup(pos); } int main(int argc,char *argv[]) { int t; scanf("%d", &t); for (int kase = 1; kase |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |