BZOJ NOI十连测 8thTest
TopCoder SRM 657

BZOJ NOI十连测 TheLastTest

YYY posted @ 2016年6月28日 20:36 in 算法竞赛 with tags 积分 组合数学 容斥原理 模拟退火 乱搞 数位DP 爬山 连续概率 , 243 阅读
---------------------------------------------------------------------
看到题就懵逼了..
 
---------------------------------------------------------------------
T1:
暴力枚举子集拿了60分
题解说"字符集比较大的时候,随机选几个起点爬山或者模拟退火就行了"
萌新瑟瑟发抖.jpg
---------------------------------------------------------------------
T2:
首先把x和y分开
然后考虑对每一个x的微元求一个概率再积分
然后对于x=t,通过他的概率就是2*t左边的面积*t右边的面积/(总面积^2)
对这个积分就行了(并不会)
题解说可以用高斯积分公式
---------------------------------------------------------------------
T3:
首先容斥一下每一个限制是>=l还是>=r+1
然后每个数就有一个下界v[i]
然后相当于t(t<=d)个球放到n个盒子里,每个盒子有一个下界
方案书就是C(t-sum(v[i])+n-1,n-1)
然后题解说"注意到C(a+b,n)=sum(C(a,i)*C(b,n-i),i=0..n),于是我们只要求出C(t,0),...,C(t,n-1)的和,然后通过这个式子可以将这些数整体加一个值,从而求出C(t-sum(v[i])+n-1,n-1)。"
也就是说对于同一个i,C(t,i)的系数是一样的,
不过问题转换为了对每个合法的t分别求C(t,0),...,C(t,n-1)和
这个数位DP就行了
---------------------------------------------------------------------
 
LOL

登录 *


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