BearChild's Blog

Red is good Time Limit: 10 Sec Memory Limit: 64 MB Description 桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。 Input 一行输入两个数R,B。 Output 在最优策略下平均能得到多少钱。输出答案时,小数点后第六位后的全部去掉,不要四舍五入。 Sample Input 5 1 Sample Output 4.166666 HINT R,B<=5000 Solution 这显然是一道简单的期望DP。我们令 f[i][j] 表示剩下 i 个红牌和 j 个黑牌时的最优答案。那么显然： 其中 i/(i+j) 和 j/(i+j) 表示选择到的概率。 最后由于卡内存，我们滚动一下数组即可。 Code 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std; ...

Tree Time Limit: 20 Sec Memory Limit: 512 MB Description Input Output Sample Input 4 2 　　1 2 　　2 3 　　3 4 　　1 4 　　3 4 Sample Output 9 　　5 HINT N <= 100000, Q <= 100000. Solution 首先，这必然是一道期望DP。 由于E(Σx) = ΣE(x)。所以我们令 f[u] 表示从 u -> fa 的期望步数，令 g[u] 表示从 fa -> u 的期望步数。显然，求出这两个东西，再求个LCA就解决改题了。 1. 如何求 f： 我们先给出普通的关系：， 然后我们 左右两边同乘d，移项一下即可得到：f[u] = 1 + Σ(1 + f[x])。 这个方程表示什么呢？1/d的概率直接走到fa，花1步走到其它点，然后再回来。 2. 如何求 g： 我们先给出普通的关系：， 然后我们 左右两边同乘d，移项一下即可得到：g[u] = 1 + (1 + g[fa]) + Σ(1 + f[x])。注意，如果 u ...

亚瑟王 Time Limit: 20 Sec Memory Limit: 512 MB Description 小 K 不慎被 LL 邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。 　　他决定，在脱坑之前，最后再来打一盘亚瑟王。既然是最后一战，就一定要打得漂亮。 　　众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。 　　作为一个非洲人，同时作为一个前 OIer，小 K 自然是希望最大化造成伤害的期望值。 　　但他已经多年没写过代码，连 Spaly都敲不对了，因此，希望你能帮帮小 K，让他感受一下当欧洲人是怎样的体验。 　　本题中我们将考虑游戏的一个简化版模型。 　　玩家有一套卡牌，共 n张。游戏时，玩家将 n 张卡牌排列成某种顺序，排列后将卡牌按从前往后依次编号为 1~n。 　　本题中，顺序已经确定，即为输入的顺序。 　　每张卡牌都有一个技能。 　　第 i 张卡牌的技能发动概率为 pi，如果成功发动，则会对敌方造成di点伤害。也只有通过发动技能，卡牌才能对敌方造成伤害。 　　基于现实因素以及小K非洲血统的考虑，pi不会为 0，也不会为 1，即 0 < pi &l ...

守卫者的挑战 Time Limit: 2 Sec Memory Limit: 128 MB Description 打开了黑魔法师Vani的大门，队员们在迷宫般的路上漫无目的地搜寻着关押applepi的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为K的包包。 　擂台赛一共有N项挑战，各项挑战依次进行。第i项挑战有一个属性ai，如果ai>=0，表示这次挑战成功后可以再获得一个容量为ai的包包；如果ai=-1，则表示这次挑战成功后可以得到一个大小为1 的地图残片。地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把 【获得的所有的】地图残片都带走（没有得到的不用考虑，只需要完成所有N项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。并且他们至少要挑战成功L次才能离开擂台。 　队员们一筹莫展之时，善良的守卫者Nizem帮忙预估出了每项挑战成功的概率，其中第i项挑战成功的概率为pi%。现在，请你帮忙预测一下，队员 ...

换教室 Time Limit: 20 Sec Memory Limit: 512 MB Description Input 第一行四个整数n,m,v,e。n表示这个学期内的时间段的数量;m表示牛牛最多可以申请更换多少节课程的教室; v表示牛牛学校里教室的数量;e表示牛牛的学校里道路的数量。 第二行n个正整数,第i(1≤i≤n)个正整数表示c,即第i个时间段牛牛被安排上课的教室;保证1≤ci≤v。 第三行n个正整数,第i(1≤i≤n)个正整数表示di,即第i个时间段另一间上同样课程的教室;保证1≤di≤v。 第四行n个实数,第i(1≤i≤n)个实数表示ki,即牛牛申请在第i个时间段更换教室获得通过的概率。保证0≤ki≤1。 接下来e行,每行三个正整数aj,bj,wj,表示有一条双向道路连接教室aj,bj,通过这条道路需要耗费的体力值是Wj; 保证通过学校里的道路,从任何一间教室出发,都能到达其他所有的教室。 保证输入的实数最多包含3位小数。 Output 输出一行,包含一个实数,四舎五入精确到小数点后恰好2位,表示答案。你的 输出必须和标准输出完全一样才算正确。 Sample Inpu ...

Summer Reading Time Limit: 20 Sec Memory Limit: 512 MB Description Input Output Sample Input 7 　　0 1 0 0 0 3 0 Sample Output 3 　　1 1 2 2 3 3 3 HINT Solution Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include<bits/stdc++.h>using namespace std;typedef long long s64;const int ONE = 1000005;const int MOD = 1e9 + 7;int n;int a[ONE];int vis[ONE], ans[ONE];struct power{ i ...

Tautonym Puzzle Time Limit: 50 Sec Memory Limit: 256 MB Description 定义一个序列贡献为1，当且仅当这个序列 由两个相同的串拼接而成，比如123123。 请构造一个序列，使得它子序列的贡献和为n。 要求序列长度<=200，权值<=100. Input 一行一个n。 Output 第一行为长度len，表示你构造出的序列长度。 第二行为你构造出的序列。 Sample Input 7 Sample Output 4 　　1 1 1 1 HINT n <= 1e12 Solution 构造题到恰好为n的。一般有两种方法： 　　　　1. 可以构造出2^n，并且每部分互不影响； 　　　　2. 有方法添加若干元素使得原有答案*2或+1。 我们先考虑第一种方法。 　　显然我们把 n 化为二进制。并且发现连续 x 个相同的数提供的贡献为2^(x-1)-1，并且若干个连续的不影响。 　　这样 s 需要1+2+……+log2(n)+(log2(n) * 2)（用于补1），极限是900。不能满足条件。 我们再考虑第二种方法。 ...

上帝造题的七分钟 Time Limit: 20 Sec Memory Limit: 128 MB Description “第一分钟，X说，要有矩阵，于是便有了一个里面写满了0的n×m矩阵。 　　第二分钟，L说，要能修改，于是便有了将左上角为(a,b)，右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。 　　第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。 　　第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。 　　第五分钟，和雪说，要有耐心，于是便有了时间限制。 　　第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。 　　第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。” 　　 ——《上帝造裸题的七分钟》 　　所以这个神圣的任务就交给你了。 Input 输入数据的第一行为X n m，代表矩阵大小为n×m。 　　从输入数据的第二行开始到文件尾的每一行会出现以下两种操作： 　　　　L a b c d delta —— 代表将(a,b),(c,d)为 ...

异色弧 Time Limit: 20 Sec Memory Limit: 256 MB Description Input Output 仅一行一个整数表示答案。 Sample Input 8 　　1 2 3 1 2 3 2 1 Sample Output 8 HINT Main idea 给定若干个点，每个点有一个颜色，颜色一样的可以组成一个区间，询问有几个交。 Solution BearChild只会70分的做法，记录N表示区间个数，效率为O(Nlog(N))。这里介绍一下。 我们基于将所有区间提取出来计算，可以用一个vector存一下记录相同颜色的，然后相同颜色的任意组合即可组成可行的区间。 首先我们考虑容斥：颜色不同的相交个数 = 不考虑颜色的总相交个数 - 颜色相同的相交个数。然后我们分段来解： 1. 不考虑颜色的总相交个数： 　　　　我们考虑带log的算法，先将所有区间按照右端点（细节：若相同则将左端点大的放在前面，保证不会算入答案）排序，然后顺序往后做，每次用树状数组在区间左端点+1，区间(右端点-1)处-1（细节：右端点-1处是为了处理前一个的右端点=这一个的左端 ...

开锁 Time Limit: 10 Sec Memory Limit: 256 MB Description A君有n个盒子，每个盒子被一把锁锁着，每个盒子内都有一把钥匙。 对于每个盒子而言有且仅有一把钥匙能打开锁着它的锁，而打开它后便能拿着放置在这个盒子内的钥匙去开启其他盒子。 现在A君打算随机选择k个盒子并用魔法将它们打开，并用所得到的钥匙去尝试开启其他所有的盒子(开启一个盒子后，新得到的钥匙还能继续尝试使用)。 A君想知道：最终他能打开所有盒子的概率是多少，请你帮助他。 Input Output Sample Input 4 　　5 1 　　2 5 4 3 1 　　5 2 　　2 5 4 3 1 　　5 3 　　2 5 4 3 1 　　5 4 　　2 5 4 3 1 Sample Output 0.000000000 　　0.600000000 　　0.900000000 　　1.000000000 HINT Main idea 一个宝箱内有一个可以开启别的宝箱的钥匙，可以选择k个宝箱，询问能开启所有宝箱的概率。 Solution 我们一看就知道这是一道概率DP的题目。 我 ...