NOIP集训-10.24总结

第一题简直是出题人给我们的惊喜(然而我并没有拿满,数组开小了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最小的那个元素)
--------------------------------------------------------------------------