题解 P5377 【[THUPC2019]鸽鸽的分割】
题目描述
牛牛有一块蛋糕，他想把蛋糕分给小朋友们。蛋糕一开始是圆形的，牛牛会在圆周上选择 n 个不重合的点，将这几个点两两用线段连接。这些线段将会把蛋糕分成若干块。n<=64
现在，牛牛想知道，蛋糕最多会被分成多少块，请你告诉他答案。 （原文题意就挺简洁的，就不简化了）
这题看起来就像是道数学题（找规律题），但我太菜了，找不到规律。
首先我们画几张图（六个点就可以了），就可以发现没有三条边交于同一位置的情况是最好的。
如果三条边交于同一点，稍微调整一下一条边的位置，就可以使三个边两两的交点在不同位置，这三个交点会围处一块，就多出一块。
所以说构造出的这些点应该要满足连出的线没有三条边交于同一位置，容易发现是能构造出来的主要因为我不会构造，接下讲的所有图形都是满足这个条件的。
然而又因为我太菜了，不会直接计算n个点的图形，假设已经构造出了i-1个点在环上构造出的连边，再加入第i个点，并与i-1个点都连边，枚举与原先i-1个点哪一个连边，假设这一条连边有x个交点（包括在圆上的），这一条边上任意两个相邻的交点会把原先的一块变成两块，也就是这一条连边会使圆多出x-1块，求x的方法也很容易，从第i个点沿圆环（任意方向）到连边的那个点，若其中经过了k（不计第i个点和连边的那个点），那从圆环的另一方向走会经过i-2-k个点，从这两种点中任意各取一个点，他们的连边肯定会与现在连的这条边有一个交点，又因为没有三条边交于同一点，所以x就是k(i-2-k)+2，答案增加k(i-2-k)+1，如果按照顺序连边的话，k就是从0到i-2。
注意一开始块数等于1（一整个圆就算一块）。
题目下面的题解我点开后不知道在哪看QaQ,所以我写的可能和其中的相似，也极有可能讲的没其中的好所以我就是想水一下贡献。
这个数据范围<=64不太懂为什么，时间复杂度可以达到O(n^2),可能本来出题人不是想这样做的QaQ。
代码十分简短。
#include <cstdio>
#include <iostream>
using namespace std;
int n,i,j;
long long ans;//其实用int就够了
int main(){
while (scanf("%d",&n)==1){
ans=1;
for (i=2;i<=n;i++){
for (j=0;j<=i-2;j++)
ans+=(i-2-j)*(j)+1;
}
printf("%lld\n",ans);
}
return 0;
}