GrassTreeFlower-CSDN博客

Now Cain is unexpectedly trapped in a cave with N paths. —— 给出N条逃跑路径，每条路径有一个困难值Ci，Cain要逃跑，一开始其有战斗值f，他可以花费一个单位的时间来等概率随机选择其中一条路径逃跑，如果其战斗值f大于Ci，则在经过Ti时间（公式如上）后成功，如果小于等于，则失败（不会多花时间），且战斗值f增长Ci，问逃跑所需要的时间的期望。

2015-12-08 17:08:44 444

原创 SGU 495 Kids and Prizes [期望]

ICPC (International Cardboard Producing Company) is in the business of producing cardboard boxes. —— N个箱子里装着礼物，M个人过来挑箱子，每个人是独立的，当一个人选了一个有礼物的箱子，他会拿走礼物，并把空箱子放回去，也就是说下一个人选这个箱子的话会得不到礼物，问最终M个人得到礼物个数的期望。

2015-12-08 16:50:04 462

原创 POJ 3071 Football [概率DP]

Consider a single-elimination football tournament involving 2n teams —— 给出1<<n只队伍，他们两两之间开始比赛，赢的作为新的1<<（n-1）只队伍，继续两两比赛，其中队伍I打败队伍J的概率为Pij，问最后赢的概率最大的队伍是那一支（从1编号到1<<N）

2015-12-08 16:33:05 391

原创 CodeForces 148D Bag of mice [概率DP]

The dragon and the princess are arguing about what to do on the New Year's Eve. —— 龙与女王因是否去看精灵跳舞产生了分歧，于是决定采取从袋子里抓老鼠的方法来决定去不去看，袋子里有w只白老鼠，b只黑老鼠，谁先抓到白老鼠谁赢，而龙在从袋子里抓老鼠的时候会有一只老鼠会跑掉，现在女王先抓，问最后女王赢的概率。（一开始题意读不懂，后来才知道draw有抓的意思）

2015-12-08 16:22:17 435

原创 POJ 2151 Check the difficulty of problems [概率DP]

一场ACM比赛中，有M道题，T只队伍，现在知道每只队伍对于每一题的AC概率，问全场每个队伍都A出至少一题且至少有一只队伍A了N道题的概率。

2015-12-04 20:11:24 493

原创 HDU 3853 LOOPS [简单概率DP]

Akemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl). —— 给出一个矩阵，每个点每一步有P0的概率在原点，P1的概率向右走，P2的概率向左走，问从左上角走到右下角的期望步数。

2015-12-04 16:23:01 633

原创 HDU 4035 Maze [概率DP]

When wake up, lxhgww find himself in a huge maze. —— 给出一个迷宫，路径为一棵树，树上有N个节点，从1出发，每走到一个节点可能会发生三种事件：Ki的概率发生被杀回到起点1；Ei的概率发生成功逃出迷宫；剩下的概率发生随机选择一条路径到下一个节点。(等概率选择)问逃出迷宫前需要走的步数的期望值。

2015-12-04 14:59:18 585

原创 HDU 4089 Activation [有环的概率DP]

After 4 years' waiting, the game "Chinese Paladin 5" finally comes out. —— 现在一队人在排队等待进入游戏，但是服务器每一个时刻有概率发生下面4种事件：P1的概率发生队首的人进入游戏失败，下一时刻继续进入（相等于什么都不发生；P2的概率发生队首的人掉线，但是他会马上重连，并进入队尾；P3的概率发生队首的人成功连入游戏，这个人会从队伍中消失；P4的概率发生服务器挂掉.....现在Tomato正在排的队伍有N个人，他现在

2015-12-03 16:26:28 433

原创 Codeforces Round #334 (603B) Moodular Arithmetic [基础数学]

As behooves any intelligent schoolboy, Kevin Sun is studying psycowlogy, cowculus, and cryptcowgraphy at the Bovinia State University (BGU) under Farmer Ivan. —— 给出方程f(kx%p)=kf(x)%p ，问在集合A->B上不同的映射函数f 有几种，其中A=B={0,1,2..p-1}，p为素数（除了2），k为小于p的一个常数

2015-12-02 14:27:53 909

原创 Codeforces Round #334 (603A) Alternative Thinking [贪心]

Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length n. —— 给出一个01串，先在你可以取反其中一个Substring（0变1,1变0），问这样操作后最长的0,1间隔子序列最长是多少。

2015-12-02 14:02:32 778

原创 Codeforces Round #334 (604B) More Cowbell [贪心]

Kevin Sun wants to move his precious collection of n cowbells from Naperthrill to Exeter, where there is actually grass instead of corn. —— 给出N个已排序的奶牛铃铛的大小，现在把它们装到箱子里，一个箱子最多装两个铃铛，且不能铃铛的大小和不能超过箱子大小，问在使用K个箱子的前提下，问盒子最小多大。

2015-12-02 13:55:28 744

原创 ZOJ 3380 Patchouli's Spell Cards [基础DP+大数]

Patchouli Knowledge, the unmoving great library, is a magician who has settled down in the Scarlet Devil Mansion (紅魔館). —— M个不同的球，N种颜色，现在给球染色，问至少有L个球同一种颜色的概率。

2015-12-01 20:31:36 636

原创 HDU 4405 Aeroplane chess [概率DP+并查集]

Hzz loves aeroplane chess very much. ——飞行棋盘长度为N+1，标号从0到N，中间有M条飞行线，可以从Xi直接飞到Yi（可以连续飞），现在丢骰子，问走到>=N的投掷期望次数。

2015-12-01 00:08:34 425

原创 HDU 4336 Card Collector [概率DP]

In your childhood, do you crazy for collecting the beautiful cards in the snacks? ——每天你吃一包零食，零食中可能会出现一张要收集的卡片，卡片共N张，第I张出现的概率为Pi，ΣPi<=1，保证一包零食中最多只有一张卡片（可能没有），问收集完所有卡片的期望天数。

2015-11-30 21:14:05 615

原创 ZOJ 3582 Back to the Past [概率DP]

Recently poet Mr. po encountered a serious problem, rumor said some of his early poems are written by others. —— 现有一月光宝盒，盒子上两面各有孔N枚，一开始孔都是暗的，每一天每个孔都有等概率P的机会亮起（已亮起的不会再熄灭），当两面亮起的孔各不少于M个，就会回到过去，问你回到过去前所需要的天数的期望。

2015-11-30 20:58:40 559

原创 POJ 2096 Collecting Bugs [概率DP]

Ivan is fond of collecting. —— 给出N,S，表示bug有N类，被包含在S个子系统中，现在来debug，每一天你会发现一个bug，等概率的属于其中一类，以及其中一个子系统，问在所有类和子系统中至少发现一个bug的期望天数。

2015-11-30 20:37:39 610

原创 ZOJ 3329 One Person Game [概率DP]

There is a very simple and interesting one-person game. 给出3个骰子，每个骰子的面数已知，并且对于每个骰子来说每一面出现的概率是相等的，当三个骰子分别为A,B,C时，计数器清0，否则加上三个骰子的点数和，问计数器大于N的期望投掷数。（提取求解项的系数，化解公式）

2015-11-29 18:06:20 408

原创 HDU ACM组队安排 [基础DP+打表]

如果已知集训队队员的数量n，请你帮教练计算出所有可能的组队方案有多少种。原则是每支队伍至少一人，最多三人。

2015-11-29 17:52:33 697

原创 HDU 逆袭指数 [暴力]

这依然是关于高富帅小明曾经的故事——给出一个数N，问因子中最长的连续乘积，例如24，输出2*3*4 （即一个等差序列的乘积，差为1）

2015-11-29 17:42:01 476

原创 ZOJ 3551 Bloodsucker [概率DP]

In 0th day, there are n-1 people and 1 bloodsucker. Every day, two and only two of them meet. 有N个村民，其中1个是吸血鬼，每天都有恰好两个村民互相碰面，如果碰面的是吸血鬼和正常人，则有p的概率让后者变为吸血鬼，问全部村民变成吸血鬼的期望天数。

2015-11-20 17:42:08 438

原创 POJ 3744 Scout YYF I [概率DP]

YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy's base. 一条路上每个点标号为1,2,3....，你一开始站在1往正方向出发，有P的概率走到下一格，（1-P）的概率走到下一格的下一格，现在路上可能会有一些地雷，给出N个地雷的坐标，问你不踩地雷走过这条路的概率。

2015-11-20 13:02:04 466

空空如也

空空如也