z55250825

一只蒟蒻

日志

关于我

z55250825

文章分类

【模拟测试】【夺冠概率】

2013-10-21 22:06:35| 分类： AC题目 | 标签： |举报 |字号大中小订阅

下载LOFTER 我的照片书 |

夺冠概率(Champion)

以下是1998年法国世界杯小组赛后的对阵表

1 Brazil -----+

                +-- ? --+

2 Chile ------+         |

                        +-- ? --+

 3 Nigeria ----+        |       |

                +-- ? --+       |

 4 Denmark ----+               |

                                +-- ? --+

 5 Holland ----+                |      |

                +-- ? --+       |       |

 6 Yugoslavia -+       |        |       |

                        +-- ? --+       |

 7 Argentina --+       |                |

                +-- ? --+               |

 8 England ----+                        |

                                        +-- World Champion

 9 Italy ------+                        |

                +-- ? --+               |

10 Norway -----+       |                |

                        +-- ? --+       |

11 France -----+       |        |        |

                +-- ? --+        |       |

12 Paraguay ---+                |        |

                                 +-- ? --+

13 Germany ----+                 |

                +-- ? --+        |

14 Mexico -----+       |         |

                        +-- ? --+

15 Romania ----+       |

                +-- ? --+

16 Croatia ----+

若我们知道这些球队两两对阵时的胜率，我们就可以计算出每支球队得到大力神杯的概率了。

输入格式：

前16行描述了参赛的16只队伍的国家名，名字不超过10个字符。

下接一个16*16的矩阵表示球队两两对阵时的胜率。

输出格式：

每支球队夺冠的概率。

样例输入：

Brazil

Chile

Nigeria

Denmark

Holland

Yugoslavia

Argentina

England

Italy

Norway

France

Paraguay

Germany

Mexico

Romania

Croatia

50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50

35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35

50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50

40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40

45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45

50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50

50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50

35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35

55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55

45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45

60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60

45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45

60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60

45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45

50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50

50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50

样例输出：

Brazil     p=8.54%

Chile      p=1.60%

Nigeria    p=8.06%

Denmark    p=2.79%

Holland    p=4.51%

Yugoslavia p=7.50%

Argentina  p=8.38%

England    p=1.56%

Italy      p=9.05%

Norway     p=3.23%

France     p=13.72%

Paraguay   p=3.09%

Germany    p=13.79%

Mexico     p=3.11%

Romania    p=5.53%

Croatia    p=5.53%

====================================================================

  这是已经看过的全概率公式。

  令F[I,J]表示第I支球队晋级到2^J强的时候的概率，运用全概率公式。

  F[I,J]=SIGMA(F[I,J+1]*F[K,J+1]*W[I,K])(K是可能在第I次与球队I对战的球队）；

  边界条件 F[I,5]=0;

  关键在于方便进行状态转移。咱傻所以咱就写了各个情况下会可能对战的球队。

 procedure prepare;
var i,j:longint;
begin
  son[1,0,0]:=8;
  for i:=1 to 8 do son[1,0,i]:=i;
  son[1,1,0]:=8;
  for i:=1 to 8 do son[1,1,i]:=i+8;
  son[2,0,0]:=4;
  for i:=1 to 4 do son[2,0,i]:=i;
  son[2,1,0]:=4;
  for i:=1 to 4 do son[2,1,i]:=i+4;
  son[3,0,0]:=4;
  for i:=1 to 4 do son[3,0,i]:=i+8;
  son[3,1,0]:=4;
  for i:=1 to 4 do son[3,1,i]:=i+12;
  son[4,0,0]:=2;
  for i:=1 to 2 do son[4,0,i]:=i;
  son[4,1,0]:=2;
  for i:=1 to 2 do son[4,1,i]:=i+2;
  son[5,0,0]:=2;
  for i:=1 to 2 do son[5,0,i]:=i+4;
  son[5,1,0]:=2;
  for i:=1 to 2 do son[5,1,i]:=i+6;
  son[6,0,0]:=2;
  for i:=1 to 2 do son[6,0,i]:=i+8;
  son[6,1,0]:=2;
  for i:=1 to 2 do son[6,1,i]:=i+10;
  son[7,0,0]:=2;
  for i:=1 to 2 do son[7,0,i]:=i+12;
  son[7,1,0]:=2;
  for i:=1 to 2 do son[7,1,i]:=i+14;
  for i:=8 to 15 do
   for j:=0 to 1 do
     son[i,j,0]:=1;
  for i:=8 to 15 do
    for j:=0 to 1 do
     son[i,j,1]:=(i-7)*2-(1-j);
end;
   但是还算是写出来了...

评论这张

转发至微博

阅读(70)| 评论(0)

历史上的今天

this.p={  m:2,
              b:2,
              loftPermalink:'',
              id:'fks_087064081095088069093083087069072087084067086085086075084095',
              blogTitle:'【模拟测试】【夺冠概率】',
              blogAbstract:'  \r\n<P style=\"TEXT-INDENT: 2em;\"   \><STRONG\>夺冠概率(Champion)</STRONG\></P\>\r\n<P style=\"TEXT-INDENT: 2em;\"   \><STRONG\> </STRONG\></P\>\r\n<P style=\"TEXT-INDENT: 2em;\"   \><STRONG\>以下是1998年法国世界杯小组赛后的对阵表</STRONG\></P\>\r\n<P style=\"TEXT-INDENT: 2em;\"   \><STRONG\> </STRONG\></P\><PRE\><STRONG\>1 Brazil -----+  </STRONG\></PRE\><PRE\><STRONG\>                +-- ? --+</STRONG\></PRE\><PRE\><STRONG\>2 Chile ------+         |</STRONG\></PRE\><PRE\><STRONG\>                        +-- ? --+</STRONG\></PRE\><PRE\><STRONG\> 3 Nigeria ----+        |       |</STRONG\></PRE\>',
              blogTag:'',
              blogUrl:'blog/static/150230809201392110221828',
              isPublished:1,
              istop:false,
              type:0,
              modifyTime:1382364395407,
              publishTime:1382364395375,
              permalink:'blog/static/150230809201392110221828',
              commentCount:0,
              mainCommentCount:0,
              recommendCount:0,
              bsrk:-100,
              publisherId:0,
              recomBlogHome:false,
              currentRecomBlog:false,
              attachmentsFileIds:[],
              vote:{},
              groupInfo:{},
              friendstatus:'none',
              followstatus:'unFollow',
              pubSucc:'',
              visitorProvince:'',
              visitorCity:'',
              visitorNewUser:false,
              postAddInfo:{},
              mset:'000',
              mcon:'',
              srk:-100,
              remindgoodnightblog:false,
              isBlackVisitor:false,
              isShowYodaoAd:false,
              hostIntro:'',
              hmcon:'0',
              selfRecomBlogCount:'0',
              lofter_single:'<iframe width="140" height="560" style="overflow:hidden;" src="http://www.lofter.com/mailEntry.do?blogad=1&blog" frameBorder="0"></iframe>'
            }

{list a as x}
    {if !!x}
    <div class="iblock nbw-fce nbw-f40">
      <a class="fc03 noul" target="_blank" hidefocus="true" href="http://blog.163.com/${x.visitorName}/">
      {if x.visitorName==visitor.userName}
      <img alt="${x.visitorNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.visitorName)}&r=${visitor.imageUpdateTime}"/>
      {else}
      <img alt="${x.visitorNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.visitorName)}"/>
      {/if}
      </a>
      <div class="cwd vname thide">
        {if x.moveFrom=='wap'}
          <a class="noul pnt" target="_blank" href="http://blog.163.com/services/wapblog.html?frompersonalbloghome"><span title="来自网易手机博客" class="iblock wapIcon"> </span></a>
        {elseif x.moveFrom=='iphone'}
          <a class="noul pnt" target="_blank"><span title="来自iPhone客户端" class="iblock iphoneIcon"> </span></a>
        {elseif x.moveFrom=='android'}
          <a class="noul pnt" target="_blank"><span title="来自Android客户端" class="iblock androidIcon"> </span></a>
        {elseif x.moveFrom=='mobile'}
          <a class="noul pnt" target="_blank" href="http://blog.163.com/services/emsblog.html?frompersonalbloghome"><span title="来自网易短信写博" class="iblock wapIcon"> </span></a>
        {/if}
        <a class="fc03 m2a"  target="_blank" hidefocus="true" href="http://blog.163.com/${x.visitorName}/">
          ${fn(x.visitorNickname,8)|escape}
        </a>
      </div>
    </div>
    {/if}
    {/list}

<#--最新日志，群博日志--> <#--推荐日志-->

<p class="fc06">推荐过这篇日志的人：</p>
    <div>
      {list a as x}
      {if !!x}
      <div class="iblock nbw-fce nbw-f40">
        <a class="fc03 noul" target="_blank" hidefocus="true" href="http://blog.163.com/${x.recommenderName}/">
        <img alt="${x.recommenderNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.recommenderName)}"/>
        </a>
        <div class="cwd thide">
          <a class="fc03 m2a" target="_blank" hidefocus="true" href="http://blog.163.com/${x.recommenderName}/">
            ${fn(x.recommenderNickname,6)|escape}
          </a>
        </div>
      </div>
      {/if}
      {/list}
    </div>
    {if !!b&&b.length>0}
    <p  class="fc06">他们还推荐了：</p>
    <ul>
    {list b as y}
      {if !!y}
        <li class="rrb"><span class="iblock">·</span><a class="fc03 m2a" target="_blank" href="http://blog.163.com/${y.recommendBlogPermalink}/?from=blog/static/150230809201392110221828">${y.recommendBlogTitle|escape}</a></li>
      {/if}
    {/list}
    </ul>
    {/if}

<#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇，下一篇--> <#-- 热度 -->

{list a as x}
    {if !!x}
    <div class="hotItem iblock nbw-fce nbw-f40">
      <a class="fc03 noul" target="_blank" hidefocus="true" href="http://blog.163.com/${x.publisherUsername}/">
      {if x.publisherUsername==visitor.userName}
      <img alt="${x.publisherNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.publisherUsername)}&r=${visitor.imageUpdateTime}"/>
      {else}
      <img alt="${x.publisherNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.publisherUsername)}"/>
      {/if}
      </a>
      <div class="cwd vname thide">
        <a class="fc03 m2a"  target="_blank" hidefocus="true" href="http://blog.163.com/${x.publisherUsername}/">
          ${fn(x.publisherNickname,8)|escape}
        </a>
      </div>
      <a class="f-myLikeIcons hottype {if x.type==1} js-liketype{elseif x.type==2} js-reblogtype{elseif x.type==3} js-sharetype{else}{/if}" target="_blank" hidefocus="true" href="http://blog.163.com/${x.publisherUsername}/"> </a>
    </div>
    {/if}
    {/list}

<#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->

页脚

我的照片书 - 手机博客 - 下载LOFTER APP - 订阅此博客

z55250825

导航

日志

【模拟测试】【夺冠概率】

历史上的今天

最近读者

热度

评论

页脚