文件名称:KingdomXCitiesandVillages

  • 所属分类:
  • 其他小程序
  • 资源属性:
  • [Java] [源码]
  • 上传时间:
  • 2013-07-08
  • 文件大小:
  • 2kb
  • 下载次数:
  • 0次
  • 提 供 者:
  • st***
  • 相关连接:
  • 下载说明:
  • 别用迅雷下载,失败请重下,重下不扣分!

介绍说明--下载内容均来自于网络,请自行研究使用

Topcoder SRM 503 DIV1 500P 编程比赛题目分析及源码

LV2 500P 王国的城乡 KingdomXCitiesandVillages

题目大意:王国有多个城市和村庄,开始没有道路(连接两点的线段),假设建造道路的过程如下,先找出任意一个没有道路的村庄,将其与最近的点连接(这个点要是城市或直接间接连接到城市的村庄),如果距离相同就等概率任选一个。求总道路长度的期望。

分析:对于任何一个村庄只要求出它连接到系统的期望,最后求和即可。对到某个村庄A的距离进行排序,只需要处理小于最近城市的那些,因为如果距离长于城市,就不如直接连接城市了。排序后,对于任意的村庄B,要是被选择与A连接,说明比B离A近的那些村庄都还没有连接到系统。比如小于B的村庄有x个,那么所有情况就是(x+2)!,因为还有A和B要参与排序。小于B的x个要排在B后面,他们之间可以乱序,就是x!,所以概率就是x!/(x+2)!=1/(x+1)/(x+2),用概率乘上距离求和即可。最后不要忘记还有最近的那个城市,将概率的剩余部分给城市就行了。多个村庄相等的情况不需要考虑,可以假设有微小的差别,排序处理,结果是一样的。-Topcoder SRM 503 DIV1 500P programming contest problem analysis and source code

LV2 500P kingdom urban KingdomXCitiesandVillages

Subject to the effect: Kingdom of cities and villages, no roads begin (line connecting the two points), assuming that the process of construction of roads as follows, first find no roads at any one village to the nearest point of connection (at this point if the city ​ ​ or directly or indirectly connected to the city s village), if the distance is the same as the probability of either one on the other. Find the total road length of expectations.

Analysis: calculated for any one village as long as it is connected to the system s expectations, final summation can be. A village on the distance to a sort, just less than the nearest city to deal with those, because if the distance is longer than the city, it should be directly connected city. After sorting, for any village B, if the connection is selected with the A, B from A descr iption than those n
(系统自动生成,下载前可以参看下载内容)

下载文件列表





KingdomXCitiesandVillages.java

相关说明

  • 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
  • 本站是交换下载平台,提供交流渠道,下载内容来自于网络,除下载问题外,其它问题请自行百度更多...
  • 请直接用浏览器下载本站内容,不要使用迅雷之类的下载软件,用WinRAR最新版进行解压.
  • 如果您发现内容无法下载,请稍后再次尝试;或者到消费记录里找到下载记录反馈给我们.
  • 下载后发现下载的内容跟说明不相乎,请到消费记录里找到下载记录反馈给我们,经确认后退回积分.
  • 如下载前有疑问,可以通过点击"提供者"的名字,查看对方的联系方式,联系对方咨询.

相关评论

暂无评论内容.

发表评论

*主  题:
*内  容:
*验 证 码:

源码中国 www.ymcn.org