互联网络
uva 165 Stamps
题意： 现有k种邮票面额，一封信上最多贴h张邮票。 求能贴出的最大连续区间，即[1,max_value]这个区间内的所有面额都能贴出来。 并输出k种面额，h+k<=9. 思路： 这是一个经典的数学问题：连续邮资问题。 1）面额为1的邮票肯定要选进去（不然连1都贴不出来，还怎么连续）。 此...
uva 104 Bandwidth
题意： 给一个图，将其节点以任一序列排列。 1）计算每个节点距离相邻节点的最大距离dis[i] 2）计算出当前序列中，所有节点的dis[i]，并求出最大的dis[i]:max_dis 求最小的max_dis，并且输出此序列。 节点数不超过8个 思路： 节点数不超过八个，那直接进行全排列，求解最小值...
uva 812 Trade on Verweggistan
题意： 给w个货架，每个货架上有bi个货物，每次只能拿最上面的货物，每个货物有个价值，所有货物的售价均为10。 问：能获得的最大利润，以及能获得这个利润需要多少个货物。（有多种组合时只需输出前10种） 思路： 最开始我是先将最大价值预处理了出来，然后dfs查找方案数，结果超时了，后来发现复杂度是O(w*...
LightOj_1317 Throwing Balls into the Baskets
题目链接题意： 有N个人，M个篮框，每个人投进球的概率是P。 问每个人投K次后，进球数的期望。 思路： 每个人都是相互独立的，求出一个人进球数的期望即可。 进球数和篮框的选择貌似没有什么关系，所以给的这个M并没有什么卵用。。。。 每个人进球数的期望为：E=sigma（i*C(K,i)*p^i*(1-...
LightOj_1284 Lights inside 3D Grid
题目链接题意： 给一个X*Y*Z 的立方体，每个单位立方体内都有一盏灯，初始状态是灭的，你每次操作如下： 1）选择一个点(x1,y1,z1) 再选择一个点（x2,y2,z2） 将这两个点所形成的立方体内所有的灯全部转换状态（灭的变亮的，亮的变灭的） 问...
LightOj_1287 Where to Run
题目链接题意： 有n个街口和m条街道，你后边跟着警察，你需要进行大逃亡（又是大爱的抢银行啊），在每个街口你都有≥1个选择， 1）停留在原地5分钟。 2）如果这个街口可以到xi这个街口，并且，通过xi可以遍历完所有未走过的街口，那么就加入选择。 每个选择都是等概率的。 求警察抓住你所用时间的期...
LightOj_1265 Island of Survival
题目链接题意： 在孤岛生存，孤岛上有t头老虎，d头鹿，每天会出现随机出现两只生物（包括你自己），如果出现了一只老虎，那么你将被吃掉，如果两只老虎，则两只老虎会同归于尽，其他情况你都将生存下来。 当孤岛上没有老虎时，就视为你生存成功。 问你生存成功的最大概率。 思路： 仔细想一想，生存下来其实只和老虎有关，因为...
LightOj_1104 Birthday Paradox
题目链接题意： 若一年有n天，问至少需要多少个人才能满足其中两个人生日相同的概率大于等于0.5？ 思路： 经典问题：生日悖论 换成其互斥事件：m个人，每个人生日都不相同的概率≤0.5时最小人数。 这就是邮票收集问题的变形：每个邮票至少出现一次的概率小于等于0.5 等价于： 找到最小的...
LightOj_1079 Just another Robbery
题目链接题意： 抢银行（这个背景最爱了），有n家银行，每家银行抢劫被抓的概率是p[i]，你认为当你被抓的概率低于P的时候是安全的。 问，你最多能抢劫到多少money。 思路： 抽象成背包问题，每家银行只有两种选择，要么抢，要么不抢。 被抓的概率有点难求，因为还要考虑之前没有被抓。这里换成求互斥事件：不...
LightOj_1027 A Dangerous Maze
题目链接题意： 你在一个迷宫里，开始的时候你面前有n个门，选择每个门的概率相等，有两种结果： 1）回到|x|分钟之前(x为负时) 2）x分钟之后出迷宫(x为正时) 每次回到|x|分钟之前，你都记不得你曾经选过哪扇门 问走出迷宫所用时间的期望。 思路： 因为每次都不记得曾经的选择，所以每次的期望都是...
LightOj_1274 Beating the Dataset
题目链接题意： 给一个文档，这个文档由yes、no组成，共有s个byte，共有n个yes、no。 假设yes的个数为yes_num,no的个数为no_num。 将这n个数进行排列，对于每个排列，将其右移一个结果，并在最左端补上yes，再将其与原排列进行对比，看有多少个不同的。 计算所有排列中不同...
Sublime Text 3 安装及简单配置
SublimeText3，一款不错的文本编辑器，加上各种插件和IDE就能化身各种语言的编译器，界面以及多种插件的灵活组合搭配更是让程序员们在码代码这种枯燥的生活中增加一点调剂。 下载地址 点击DownLoad下的windowsorwindows64bit如果你的系统是32位，那么点击前者。 如果网页打不开或者...
Uva_11722 Joining with Friend
题目链接题意： 两个人坐火车，在某个城市到站的时间段分别为[t1,t2],[s1,s2]，停在站台的时间均为w。 问，若两人能见面的概率。 思路： 一道基础的几何概型，p=s(m)/s(n)。 令x1=t1,x2=t2。 令y1=s1,y2=s2。 这样这四条直线就围成一个矩形，若两人见面，则应该...
Uva_11021 Tribles
题目链接题意： 现在有k只麻球，每只麻球只能存活一天，第二天就会死去，死去之前可能生下x只小麻球(x=0,1,2,...,n 1),概率分别为P[0],P[1],...,P[n-1]。 现求，m天之后，所有麻球全死去的概率，包括m天之前就已经全部死去。 思路: 每只麻球都是相互独立的，那么可以...
