NOIP集训-10.24总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
第一题简直是出题人给我们的惊喜（然而我并没有拿满，数组开小了T_T）
--------------------------------------------------------------------------
序列：SuperOjP953
让暴力最慢的输入是斐波那契数列，而斐波那契数列在50项的时候就超过long long的范围了...
所以暴力的时间复杂度不会超过50^3,安心写暴力就好
--------------------------------------------------------------------------
登山:SuperOjP954
题目就是不经过y=x+1这条线走到终点的方法数
首先知道走到一个点(x,y)，没有任何限制的走法为C(x+y,x)
然后假设某点为w,w关于y=x+1的对称点为w'
发现任意一个经过了y=x+1的走法,一定可以关于其与y=x+1的某个交点对称，变成没有限制走到w'的走法
因此总的答案就是 没有限制走到w的走法-没有限制走到w'的走法，设其为f(w)
假如没有坑，我们要求的就是f(终点)
我们把坑和终点都叫做关键点
假设g(p)表示不经过任何其他关键点走到关键点p的方法数
显然有:g(p) = f(p) - ∑(s在p的左下方) g(s)
这样就可以求出g(终点)，也就是答案
--------------------------------------------------------------------------
Melancholy:SuperOjP955
题目给我们了n个二元组(d,v),并有m个询问
询问是有序的，可以通过最后乘以k!来将其变成无序的
首先把所有二元组按d排序，然后两次二分查找可以找到一个要询问的区间，假设为[l,r]
然后可以用线段树询问出来这个区间中v最小的二元组的v,假设为vp
首先可以预处理出一个前缀和S(i,k):前i个，选k个的答案
有:S(i,1) = ∑(i=1,k) v(i)
S(i,k) = v(i)*S(i-1,k-1) + S(i-1,k)
然后假设f(l,r,k)表示[l,r]这个区间内选k个的答案，显然有：
f(l,r,k) = S(r,k)-S(l-1,k)-∑(i=1,k-1)f(l,r,i)*S(l-1,k-i)
(其实至于为什么是这样，还是需要想一下的...)
假设g(l,r,p,k)为l,r内，选k个，且不选p这个点的答案(设vp为p的v值)
显然有:
g(l,r,p,k) = f(l,r,k) - vp*g(l,r,p,k-1)
然后g(l,r,p,k)*(k!)就是这一次询问的答案（p是v最小的那个元素）
--------------------------------------------------------------------------
评论 (0)
