[洛谷P5377][THUPC2019]鸽鸽的分割

题目大意：有一个圆，圆上有$n$个点，将这几个点两两连接，问最多分成几部分

题解：发现这相当于一个平面图，由欧拉公式得（$F$为平面分割块数，$E$为平面图边数，$V$为平面图点数）：
$$
F=E-V+2
$$
可知最优解不存在三线共点。

$V=n+\binom n4$，即圆上原来的$n$个点，和任意四个点会产生一个交点

$E=n+\binom n2+2\binom n4$，即原来的$n$条弧，任意两个点产生一条线段，以及每个点增加两条线段

且圆外空间不算一部分。故答案为$1+\binom n2+\binom n4$

卡点：无

C++ Code：

#include <cstdio>

#include <iostream>

long long n;

int main() {

	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

	while (std::cin.good() && std::cin >> n) {

		std::cout << 1 + n * (n - 1) / 2 + n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4 << '\n';

	}

	return 0;

}

巴特西

[洛谷P5377][THUPC2019]鸽鸽的分割

最新文章

热门文章