洛谷 P2675 题解

放普及段的原因:
image

卢卡斯定理练手好题
水紫一道,顶多蓝

解题思路

该题的难点在于:脑补 \LaTeX
我们先分析下样例,设这四个数分别为 a_1,a_2,a_3,a_4
那么合并过程就可以这样表示:
a_1 \,\,\,\,\,\,\, a_2 \,\,\,\,\,\,\, a_3 \,\,\,\,\,\,\, a_4 \\a_1+a_2 \,\,\, a_2+a_3 \,\,\, a_3+a_4 \\a_1+2a_2+a_3 \, a_2+2a_3+a_4 \\a_1+3a_2+3a_3+a_4
可以发现,结果的各项系数刚好对应杨辉三角,从下往上推很容易证明。
所以只需用组合数求出各项系数。
接下来考虑贪心,由于杨辉三角中间的数最大,考虑将大数放在中间,然后就能过了。
(有无大佬证明一下,反正这个思路是能过的)

AC 代码

你说的对,但是信友队论坛不能放 AC 代码

1 个赞

这么快就降蓝了?

有什么可以证明的?

题解不应该放在经验分享里嘛,问题讨论里理论上都不应该有题解这个标签的