笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

经典题再放送

posted on 2020-05-28 07:54:54 | under 题解 |

似乎 THUPC2019 考过这题?当然这题已经是经典题中的经典题了。这里给出一个不同的解释。

给定一个圆,边界上选 $n$ 个点两两连边,最多能划分出多少个区域。



与正解之间的分割线。



首先不难发现是可以做到不存在三点共线的,并且不共线结果至少不会更劣。那么如果设 $g(i)$ 表示交出的这些区域中 $i $ 边形的个数(只考虑交出来的最小单元),会有$$ \sum _{i=3}^{n} i\times g(i)=n+2\cdot \left(2\cdot \binom{n}{4}+ \binom{n}{2}-n\right) $$ 即每条边会产生两次贡献,这 $n$ 个点最后连出的边可以交出 $\binom{n}{4}$ 个交点,每删掉一个交点可以多出两条线段。同时最后交点删干净之后还剩 $\binom{n}{2}$ 条线段,同时为了单独计算相邻点之间的连边要先减去 $n$ 并且最后再加回来。

同时再考虑内角和的贡献。即$$ \sum_{i=3}^ng(i)\cdot(i-2) \pi=2\pi\cdot \binom{n}{4}+(n-2)\pi $$ 其中右边第一项是每个点周围一圈是 $2\pi$ ,第二项是考虑最大的那个 $n$ 边形的内角和。

考虑上面两个式子作差,可以得到$$ \sum_{i=3}^n g(i)=\binom{n}{4}+\binom{n-1}{2}+n $$ 即为答案。