5
22
2018
0

补一波数论

HDU6025 Coprime Sequence

题意:最大化数列中删除掉一个数后的GCD。数列长度n=10^5,T=10

题解:暴力枚举删除每个数,问题转化为O(1)求出数列中剩余数的GCD。

做法是预处理出前缀GCD和后缀GCD,则除去a[i]之外其余数的GCD'[i]=gcd(前缀[i],后缀[i])

 

期望DP也放在这里吧:

►总结:转移方程有时比较灵活。一般求概率是正推,求期望是逆推。

poj 2096 期望入门题Collecting Bugs

题意:程序的bug有n个子集,s个种类。每一个bug属于每个子集的概率为1/n,每一个bug属于每个种类的概率为1/s,问每个子集且每个种类都有bug的期望。

题解: dp[i][j]表示已经找到i种bug,j个系统的bug,达到目标状态的天数的期望

dp[n][s]=0;要求的答案是dp[0][0]; 

dp[i][j]可以转化成以下四种状态:

1)dp[i][j],发现一个bug属于已经有的i个分类和j个系统。概率为(i/n)*(j/s);

2)dp[i][j+1],发现一个bug属于已有的分类,不属于已有的系统.概率为 (i/n)*(1-j/s);

3)dp[i+1][j],发现一个bug属于已有的系统,不属于已有的分类,概率为 (1-i/n)*(j/s);

4)dp[i+1][j+1],发现一个bug不属于已有的系统,不属于已有的分类,概率为 (1-i/n)*(1-j/s);

整理便得到转移方程

Category: 高考 | Tags: | Read Count: 387

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com