BZOJ NOI十连测 TheLastTest
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
---------------------------------------------------------------------
看到题就懵逼了..
---------------------------------------------------------------------
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就行了
---------------------------------------------------------------------
评论 (0)
