经典题再放送

皎月半洒花

2020-05-28 07:54:54

Solution

似乎 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 $$ 即为答案。