[综合] 紫书 例题 10-10 UVa 10491（概率计算）

公式很好推，表示被高中生物遗传概率计算虐过的人 这个公式简直不需要动脑 #include<cstdio> usingnamespacestd;intmain() {doublea,b,c;while(~scanf("%lf%lf%lf",&a,&b,&c)){do...

[综合] 紫书 例题 10-11 UVa 11181（概率计算）

这道题不能凭感觉做了。要套公式 r个人买了东西叫事件E，第i个人买东西的概率叫做事件Ei 求得是P（E|Ei），则P（E|Ei）=P（E|Ei）/P（E） 那么P（E）可以枚举求得，用递归求排列，然后把每一种 排列的概率加起来就是总的概率 然后P（E|Ei）就是要求在排列中当前这个事件会发生 所以可...

[综合] 紫书 例题 10-12 UVa 1637（概率计算）

以9元组来代表当前状态，每一元是每一堆剩下的牌数 枚举当前状态所有可以拿掉牌的情况，然后递归下去求 概率，当牌拿完的时候概率为1 那么这里的实现非常的秀，用到了vector来代表9元组 然后还用到了map来实现记忆化搜索 #include<cstdio> #include<vect...

[综合] 紫书 例题 10-13 UVa 830（递推）

首先我们按照这三个U的位置来分类，当前三个U在i，i+1,i+2。 那么先看三个U前面，前面不能有三个U，因为我们不能重复计算 那么就是所有的组合减去有U的情况 为了叙述方便，我们设答案为f（n），没有三个U的方案数为g（n） 那么显然g（n）=2的n次方-f（n） 然后我们看三个U后面，后面就任意...

[综合] 紫书 例题 10-14 UVa 12034（组合数+递推）

这道题有点类似动态规划，设答案为f（n） 第一个人有i个人，就有c（n，i）种可能 然后后面有f（n-i）种可能，所以相乘，然后枚举所有可能加起来就ok了。 #include<cstdio> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usin...

[综合] 紫书 例题 10-15 UVa 1638（递推）

从大到小安排杆子 分三种情况 （1）插到最左边，那么左边看到了杆子会多一个 （2）插到最右边，那么右边看到了杆子会多一个 （3）插到中间边，那么不影响左边和右边看到的杆子数 具体看代码 #include<cstdio> #defineREP(i,a,b)for(inti=(a);i<...

[综合] 紫书 例题 10-16 UVa 12230（数学期望）

感觉数学期望的和化学里面求元素的相对原子质量的算法是一样的 就是同位素的含量乘上质量然后求和得出 这道题因为等待时机是0到2*l/v均匀分配的，所以平均时间就是l/v 再加上过河的l/v，最后加上步行的时间就ok了 #include<cstdio> #defineREP(i,a,b)fo...

[综合] 紫书 例题 10-17 UVa 1639（数学期望+对数保存精度）

设置最后打开的是盒子1，另外一个盒子剩下i个 那么在这之前打开了n+n-i次盒子 那么这个时候的概率是C（2*n-i,n)p^(n+1)（1-p）^(n-i) 那么反过来最后打开的是盒子2，那么概率是C（2*n-i,n)p^(n-i)（1-p）^(n+1) 那么当前的概率就是两个加起来，然后乘以权值...

[综合] 紫书 例题 10-17 UVa 1639（数学期望+分数处理+处理溢出）

设当前有k个，那么也就是说拿到其他图案的可能是（n-k）/n 那么要拿到一个就要拿n/（n-k）次 所以答案就是n（1/n+1/(n-1)......1/2+1/1） 看起来很简单，但是实现有很多细节 一开始我是写了一个分数加法的函数 然后发现中间过程会溢出 所以要做两个操作 （1）分母为1和n不算...

[综合] 紫书 例题 10-18 UVa 11346（连续概率）

就是面积计算，没什么好说的。 #include<cstdio> #include<cmath> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;intmain() {intT;scanf("%d",&...

[综合] 紫书 例题 10-20 UVa 10900（连续概率）

分两类，当前第i题答或不答 如果不回答的话最大期望奖金为2的i次方 如果回答的话等于p*下一道题的最大期望奖金 那么显然我们要取最大值 所以就要分类讨论 我们设答对i题后的最大期望奖金为d[i] 显然临界点，也就是这两种情况相等的时候 p0=2^i/d[i+1] 那么因为题目说概率在t到1之间 所以...

[综合] 紫书 例题 10-21 UVa 11971（连续概率）

感觉这道题的转换真的是神来之笔 把木条转换成圆，只是切得次数变多一次 然后只要有一根木条长度为直径就租不成 其他点的概率为1/2^k当前这个点的有k+1种可能 所以答案为1-（k+1）/2^k #include<cstdio> #include<cmath> #defineR...

[综合] 紫书 例题 10-22 UVa 1640（数位统计）

这道题的题解有几个亮点 一个是每次只统计一个数字来简化思维 一个是统计当前位数的时候分三个部分来更新答案 具体看代码，有注释 #include<cstdio> #include<cstring> #include<algorithm> #defineREP(i,a...

[综合] 紫书 例题 10-24 UVa 1641（面积计算）

遍历一遍，遇到边界为奇数次时，格子在多边形内 偶数次时，在多边形外 #include<cstdio> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;intmain() {chars[105];intn,m;wh...

[综合] 紫书 例题 10-25 UVa 1363（找规律）

可以发现余数是成一段一段的等差数列的。 在商数同的时候，余数是成首项为第一个数的余数，公差 为商数的等差数列。 利用这个性质求解即可。 #include<cstdio> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i&l...

[综合] 紫书 例题 10-26 UVa 11440（欧拉函数+数论）

这里用到了一些数论知识 首先素因子都大于M等价与M！互质 然后又因为当k与M！互质且k>M!时当且仅当kmodM!与M！互质（欧几里得算法的原理） 又因为N>=M,所以N!为M!的倍数 所以只要求1到M！中与M！互质的数的个数,在乘上N!/M! 可以理解为每一块M！有这么多，然而N！中有...

[综合] 紫书 例题 10-27 UVa 10214（欧拉函数）

只看一个象限简化问题，最后答案乘4+4 象限里面枚举x，在当前这条固定的平行于y轴的直线中 分成长度为x的一段段。符合题目要求的点gcd（x，y）=1 那么第一段1<=y<=x，个数为phi（x）个，即是x的欧拉函数值 第二段x+1<=y<=2x，因为gcd(x+i,x)=g...

[综合] 紫书 例题 10-28 UVa 1393（简化问题）

这道题是对称的 所以只算“\”，最后答案再乘以2 然后每一条直线看作一个包围盒 枚举包围盒的长宽 有两种情况会重复 （1）包围盒里面有包围盒。 这个时候就是在一条直线上 那么我们就gcd（x，y）>1的时候舍去 因为在一条直线上只取gcd（x，y）=1这个点 以后注意一条直线上去重问题都可以用...

[综合] 紫书 例题 10-29 UVa 1642（最优连续子序列）

这类求最优连续子序列的题一般是枚举右端点，然后根据题目要求更新左端点， 一般是nlogn，右端点枚举是n，左端点是logn 难点在于如何更新左端点 用一些例子试一下可以发现 每次加进一个新元素的时候 前面的元素都要再取一遍gcd 然后gcd同的时候i尽量大 为了去重，我们需要排序，用相邻元素比较 保...

[综合] 紫书 习题 10-1UVa 111040（找规律）

通过观察可以得 图可以分成很多个上面一个，中间两个，下面三个的“模板” 这个时候最上面一个知道，最下面得左右知道 那么可以设下面中间为x，左边为a1,右边为a2，a1a2已知 那么可以得出最上面得一个为a1+a2+2x，那么最上面又是已知的 所以就可以推出x，那么这个模板的所有元素就可以推出来了 详...