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