puzzle（006.1）平面划分问题HDU 1249 三角形

puzzle（006.1）平面划分问题HDU 1249 三角形

目录

​​一，连续空间划分问题​​

​​1，1维——线段 or 直线​​

​​2，2维——圆形 or 整个平面​​

​​3，3维——球形 or 整个空间​​

​​4，k维——整个k维空间​​

​​二，OJ实战​​

​​HDU 1249 三角形​​

​​HDU 2050 折线分割平面​​

​​51Nod 1104 直线分割圆​​

​​CSU 1284 Cutting Cake​​

​​CSU 2059 Water Problem（Z字形分隔平面）​​

​​三，对称之美​​

​​练习模式​​

​​比赛模式​​

​​策略​​

一，连续空间划分问题

1，1维——线段 or 直线

n个点可以把线段或者直线分成多少段？

答案是 n+1

2，2维——圆形 or 整个平面

（1）n个直线把圆或者平面分成多少块？

答案是（1+2+3+......+n）+1 = n(n+1)/2+1

（2）圆上的n个点，两两连接成的n(n-1)/2条弦最多可以把圆分成多少块？

思路：单点发出的n-1条弦被其他弦分割形成的分割点的个数是1*(n-3)+2*(n-4)+...+(n-4)*2+(n-3)*1=(n-1)(n-2)(n-3)/6

所以答案是

即n(n-1)(n-2)(n-3)/24+n(n-1)/2+1

3，3维——球形 or 整个空间

（1）n个平面把球形或者空间分成多少块？

答案是

（2）在matrix67的博客中还有这么一个问题，n刀可以把甜甜圈切成多少块？

通过拓扑变换，可以推导出，n刀可以把甜甜圈切成多少块其实就是n+1刀可以把球形分成多少块。所以答案是

4，k维——整个k维空间

通用问题，n个k-1维的刀，可以把一个k维的无穷空间切成多少块？

递推式是

例如，

即，n刀可以把一个无限的三维空间切成

块。

二，OJ实战

HDU 1249 三角形

题目： Description

用N个三角形最多可以把平面分成几个区域?  Input

输入数据的第一行是一个正整数T(1<=T<=10000),表示测试数据的数量.然后是T组测试数据,每组测试数据只包含一个正整数N(1<=N<=10000). Output

对于每组测试数据,请输出题目中要求的结果.  Sample Input

2 1 2 Sample Output

2 8

解释一下网上到处飞的递推式f(n)=f(n-1)+(n-1)*6是怎么来的。

这个问题其实和n条直线可以把平面分成多少个部分是差不多一样的。

对于直线的问题，递推式是f(n)=f(n-1)+n

也就是说，从n-1条直线，变成n条直线，多了n块。

为什么就刚好是n呢？因为，一条直线可以被n-1条直线分成n段，而每一段，都恰好对应着从n-1条直线变成n条直线时会有1块变成2块，于是整体增加了n块。

对于三角形的问题，道理是一样的。

一个三角形（注意，这里指的是三条边构成的曲线）可以被n-1个三角形分成(n-1)*6段，于是便得到了递推式。

所以f(n)=3 * n*(n - 1) + 2

代码：

#includeusing namespace std;int main(){ int k, n; cin >> k; while (k--) { cin >> n; cout << 3 * n*(n - 1) + 2 << endl; } return 0;}

HDU 2050 折线分割平面

题目：

我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。

Input 输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0

Output 对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。

Sample Input 2 1 2 Sample Output 2 7

这个问题的本质，和直线分割平面问题是一样的。

每增加1个折线，增加的平面区域的数目等于增加的交点的数目加1

每2个折线都可以有4个交点，如此便得到公式

代码：

#includeusing namespace std; int main(){ int a; cin >> a; while (cin >> a)cout << a*a * 2 - a + 1 << endl; return 0;}

51Nod 1104 直线分割圆

圆上有N个点，每个点和其他所有点之间都有直线相连。并且任意3线不共点。计算这些直线把圆分割所得的区域的数量K。

例如：N = 2，K = 2，N = 3，K = 4。由于结果可能会很大，输出K Mod (10^9 + 7)的结果。

Input

输入：1个数N。(2 <= N <= 10^9)

Output

输出数量 Mod 10^9 + 7

Sample Input

2

Sample Output

2

#includeusing namespace std;int main(){ long long n,p=1000000007; cin>>n; long long x=n*(n-1)/2%p,y=(n-2)*(n-3)/2%p; long long z=x*y%p*(p+1)/6%p+x+1; cout<

CSU 1284 Cutting Cake

题目：

Description

一个蛋糕切N刀，最多能得到多少块？切的过程中不能改变任意一块蛋糕的位置。

Input

输入数据的第一行包含一个整数T (1 <= T <= 100)，表示接下来一共有T组测试数据。

每组测试数据占一行，包含一个整数N (1 <= N <= 100)，含义同上。

Output

用一行输出一个整数，表示上述问题的答案。

Sample Input

3 2 3 4

Sample Output

4 8 15

代码：

#includeusing namespace std; int main(){ int t, n; cin >> t; while (t--) { cin >> n; cout << (n*n - 1)*n / 6 + n + 1 << endl; } return 0;}

CSU 2059 Water Problem（Z字形分隔平面）

题目：

Description

一条‘Z’形线可以将平面分为两个区域，那么由N条Z形线所定义的区域的最大个数是多少呢？每条Z形线由两条平行的无限半直线和一条直线段组成

Input

首先输入一个数字T（T<100），代表有T次询问 每次询问输入一个数字N（N<1e8），代表有N条Z形线

Output

对于每次询问，在一行输出N条‘Z’形线所能划分的区域的最大个数为多少

Sample Input

2 1 2

Sample Output

2 12

思路：

首先考虑一个类似的问题：

有N组直线，每组都由3条平行的直线构成，3条直线的间距可以调整。

那么N组直线最多划分出多少个区域？

这个问题就很容易求出来，3n（3n-1）/2+1

本题的答案，就是把每组3条平行直线变成Z，也就是在3n（3n-1）/2+1的基础上再减2n即可

代码：

#includeusing namespace std; int main(){ long long a; cin >> a; while (cin >> a)cout << (a * 9 - 7)*a / 2 + 1 << endl; return 0;}

三，对称之美

​​最强大脑​​同款项目。

练习模式

（3）

（8）

比赛模式

简单

普通

困难

前面很多地方是随便试的，最后这块有个白格子没覆盖，不好解决。

策略

初始条件：先把对称点在边上的或在交叉点上的，对应的2个或4个格子标注出来，颜色不用特别在意，随时可以换，如果不在意速度的话。

局部性原理：整个局面如何划分，并不是特别随意，每个格子属能于哪个块的情况数并不多。

推理顺序：推理顺序主要是2种，一种是先从对称点比较密集的地方开始推理，另一种是从边角往里推，因为这些地方的情况数比较少。

示例：

先标初始条件

再从边角推理：（粉色的4处）

PS：我用黑线把颜色标注出来了，标注的颜色表示是这一轮新推理出来的。

继续推理能确定的：（蓝绿紫三色的8处）

继续推理：（红色和粉色的5处）

然而，再继续往下推就会发现错误，于是我干脆随意试一下，看大概有多少格子标不出颜色

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。