NOIP 2016 day2

T1

[NOIP2016 提高组] 组合数问题

组合数学

solution

前置知识:组合数

40 pts

暴力套公式就好了,不但TLE,还会爆 long long,考虑优化

70 pts

组合数的递推式

\[C^m_n = C_{n - 1}^{m - 1} + C_{n - 1}^{m} \]

根据公式预处理出 \(C\) 组,然后就优化到了 \(n*m*T\)

90 pts(O2:95 pts)

最后是求 \(k\) 的倍数,所以每步计算都 % k,优化了空间,继续优化时间

100 pts

发现答案是对一个矩形求和,直接二维前缀和就好了

code

T2

[NOIP2016 提高组] 蚯蚓

solution

90 pts 暴力??

因为每次取的都是最大的,所以用优先队列维护每只蚯蚓;

至于每次切完之后都增加 \(q\) ,可以用 \(tmp\) 累计,每次弹出的时候加上这个值就是蚯蚓的长度;

还有个问题,那些切了的蚯蚓这回合不增长,那就把它减掉 \(q\) ,然后放到队列里就好了

100 pts

为ycc改错 逃

考虑单调性;

把原来的蚯蚓排个序 \(a_1 > a_2 … >a_n\)

现在取出 \(a_1\) ,切成了 \(p*a_1\) 和 \((1 - p)*a_1\)

此时 \(a_2\) 成为 \(a_2 + q\) 切开之后成了 \(p(a_2 + q)\) 和 \((1 - p) * (a_2 + q)\)

此时 \(a_3\) 成为 \(a_3 + 2q\) 切开之后成为 \(p(a_2 + 2q)\) 和 \((1 - p) * (a_2 + 2q)\)

此时 \(p * a_1\) 长成了 \(p * a_1 + 2q\) ,\((1 - p)*a_1\) 长成了 \((1 - p)*a_1 + 2q\)

\(p(a_2 + q)\) 长成了 \(p(a_2 + q) + q\) ,\((1 - p) * (a_2 + q)\) 长成了 \((1 - p) * (a_2 + q) + q\)

很显然 \(p * a_1 + 2q > p(a_2 + q) + q > p(a_2 + 2q)\)

​ \((1 - p)*a_1 + 2q > (1 - p) * (a_2 + q) + q > (1 - p) * (a_2 + 2q)\)

依次类推,切开的蚯蚓满足单调性,所以用三个队列维护原蚯蚓和切开的蚯蚓,每次从三个队首取出最大的一个就好了

code

T3

[NOIP2016 提高组] 愤怒的小鸟

搜索,状压

solution

50 pts

暴力, \(f[S]\) 表示加入的点的集合,转移枚举两个点,计算抛物线,然后枚举有多少个点符合这个抛物线

时间复杂度:\(O(n^3 * T * (1<<n))\)

85 pts

预处理

把两点确定的抛物线所经过的点的集合进行预处理

时间复杂度: \(O(T∗n^2*(1<<n))\)

code

100 pts

不再枚举两个点,如果最后一位没有选先处理最后一位,然后再枚举另一个点就好了

code

上一篇:android开发学习——day2


下一篇:DOS DAY2(2)