HDU2050 && CSU2059 折线分割平面问题

2018/08/02 15:57
阅读数 12

HDU2050 折线分割平面 (递推)

Problem Description

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

Input

输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(0<n<=10000),表示折线的数量。

Output

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

Sample Input

2
1
2

Sample Output

2
7

题解

思路

整理下思路,首先入手时候应该考虑直线分割平面的事实。当第i条直线画在平面上时,最多可以和i-1条直线形成交点。由此可得多出的平面数量为(i-1)+1。

对于本题增加到第i条折线时,最多有2*2(i-1)个新增交点,由此可得多出的平面数量为2*2(n-1)+1,所以可以推出递推公式:

f(n)=f(n-1)+4(n-1)+1 n>=3*

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
int T =0;
const int MAXN=1e5+10;
const int MAX =1e8+10;
int ans[MAXN];
int a=0;

int line(){
	ans[1]=2;
	for(int j=2;j<MAXN+2;j++){
		ans[j]=ans[j-1]+4*(j-1)+1;
	} 
	
	return 1;
}

int main(void){
	line();
	scanf("%d",&T);
	for(int i =0;i<T;i++){
		scanf("%d",&a);
		printf("%d\n",ans[a]);
	}
	return 0;

}

CSU2059 Water Problem(递推)

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

Hint

img

题解

思路

首先考虑这样的问题,每组直线由3条平行线构成,间隔可以任意调整。那么对于n组直线所能形成的最多平面数量为3n*(3n-1)/2+1。现在,将中间的直线改为斜线之后,在之前答案基础上减去2n即可。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

int main(){
	int T = 0;
	scanf("%d",&T);
	for(int i=0;i<T;i++){
		ll h = 0;
		scanf("%lld",&h);
		ll ans = (long long )(4.5*(h+2)*(h-1)-8*(h-1)+2);
		printf("%lld\n",ans);
	}

	return 0;
}

总结

直线分割平面的递推题目的突破点在于考察对于第i条直线时,新加入之后,新形成的交点情况。新形成的交点会产生新的平面。基础情况见下面blog:

https://blog.csdn.net/zhouhong1026/article/details/7854948

展开阅读全文
amp
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部