noip2011提高组day2题解.docx

《noip2011提高组day2题解.docx》由会员分享，可在线阅读，更多相关《noip2011提高组day2题解.docx（2页珍藏版）》请在第一文库网上搜索。

1、noip2011提高组day2题解第一题数值计算考察二项式定理(a*x+b*y)Ak 展开后 x八n*yAm(n+m=k)项系数为 aAn*bAm*C(k,n)C为组合数求解组合数用杨辉三角即 C(a, b) = C(a-1, b-l) + C(a-1, b)时间复杂度0(02)第二题二分取的w值越大 可以选择的零件就越少所以按要求计算出的数值s就越小所以二分找到两个距离给定的值k最近的两个s即可每次求解s时用部分和的方法即先用0(n)的时间算出从最开始到中间某一处总的可以取的零件数和其v值之和之后对于每一个区间可以用0(1)的时间算出该范围内可以取的零件数和其v值之和不需要高精度因为当w取最

2、大时s为0此时abs(k-s)=s优于所有s爆精度的情况所以计算时若s超过64位整型的范围时令其等于一个特别大的值即可时间复杂度 二分O(logMaxW) *二分时每次的求解O(n)即 O(nlogMaxW)第三题贪心这道题使用贪心的方法每次选择一条能获得最大收益的路修改直到不能修改为止具体做法和解释如下每个人在车上的时间等于车到达目的站的时间减去这个人到达起始站的时间由于人到达起始站的时间题目给出不会变化所以求解一个最优的车到达目的站的时间即可假设到达第i+1站的时间是timei从前往后逐个求解到站时间可以得出 timei = maxtimei-l, lasti + di其中lasti为从第

3、i站上车的旅客中最后到达的一个到达的时间可以用O(n+m)的时间预处理得出di为从i走到i+1所用的时间很明显的我们可以利用这个递推关系式用0(n)的时间求解timei当我们令di减少1时timef 1 .i-1 不会变化会减少1考虑 timei+l由前面的式子得出 timeli+1 = maxtimeli, lasti+l + di+l若我们令di减少之前 存在timeilasti+l则timei+l会减少1否则mei+l就会不变若timei+l减少了 1我们可以用同样的方法判断timei+2直到最后是否变化若limei+H不变 则timei+2及之后的time值都不会变化*所以当我们令某个

4、di减少1时 从timei开始会有一段区间的time值均减少1这个区间的左端为i我们令右端为rangei对于 j 属于从 i+1 到 rangei均存在 lastfj且对于 rangei+l 不存在lastj说到这里 大家应该发现求解ranged的方法了若rangei+l = t则对于从i+2到t前不等式均成立且对于t+1不成立所以我们求解range。只需判断对于i+1前不等式是否成立即可若成立则 rangei= rangei+l不成立则 rangei = i若我们修改每个值所减少的时间为reduceij则reducei = vij + vi+l + . + vrangeivi表示到达第i+1个车站的人的数量很明显的 reducei = vi + reducei+l或 vi现在 我们可以用0(n)的时间求解reduce 了然后每次选择一个令reducei最大的i令di减少即可注意每次修改di之后要重新计算新的timefil时间复杂度O(kn)第三题补充若di=。时则不能再减少 但计算reduce和range时还要考虑它 这一点要注意