首页 > ACM题库 > HDU-杭电 > hdu 2538 确定排名待解决[解题报告]C++
2014
02-10

hdu 2538 确定排名待解决[解题报告]C++

确定排名

问题描述 :

今年的NBA西部的竞争是如此激烈,以至于在最后一轮之前,前8的球队里多达6只球队还没有确定自己的排名。在本题中,给出了在最后一轮之前各只球队的胜场数以及最后一轮的对阵情况,要求给出各只球队排在第几名的概率。假设每场比赛两方获胜的概率各是50%。
在本题中,与NBA不同的是,排名的唯一标准是胜场数,当几只球队胜场数相同时,算这几只球队并列排在(可能)最靠前的位置上。

输入:

输入包含多组数据。第一行是一个整数N(2<=N<=24,偶数),表示球队的数目,N=0代表输入结束。随后有1行包含N个整数,分别代表N只球队的胜场数(不超过200)。每组数据的最后一行是N只球队最后一轮的对阵情况(格式参考样例),球队的序号从1开始,共有N/2场比赛,每只球队出现且仅出现一次。

输出:

输入包含多组数据。第一行是一个整数N(2<=N<=24,偶数),表示球队的数目,N=0代表输入结束。随后有1行包含N个整数,分别代表N只球队的胜场数(不超过200)。每组数据的最后一行是N只球队最后一轮的对阵情况(格式参考样例),球队的序号从1开始,共有N/2场比赛,每只球队出现且仅出现一次。

样例输入:

2
2 0
1-2
4
3 2 1 0
1-2 3-4
0

样例输出:

1.0000 0.0000
0.0000 1.0000
1.0000 0.0000 0.0000 0.0000
0.5000 0.5000 0.0000 0.0000
0.0000 0.2500 0.7500 0.0000
0.0000 0.0000 0.5000 0.5000

提示:
建议输出保留到小数点后4位。
输出格式要求不是很严格,只要保证能够区分出每个数,而且结果都正确,就应该会被判为正确。
输出数据较多,尽量用printf代替cout。


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  5. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?