解决通法
找出第i条线增加后会增加几个交点,则增加的面数就是交点数+1,根据递推公式求出通项公式,注意如果第i次增加的线不只一条,要单独考虑每一条线,比如每一次增加一组平行线,要分别算出这两条线可能产生的交点数
例题
HDU-2050 折线分割平面
题目链接
https://vjudge.net/problem/HDU-2050
题面
Description
我们看到过很多直线分割平面的题目,今天的这个题目稍微有些变化,我们要求的是n条折线分割平面的最大数目。比如,一条折线可以将平面分成两部分,两条折线最多可以将平面分成7部分,具体如下所示。
Input
输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(0<n<=10000),表示折线的数量。
Output
对于每个测试实例,请输出平面的最大分割数,每个实例的输出占一行。
Sample Input
2
1
2
Sample Output
2
7
题解
第i条折线增加后,就是增加\(4 \times (i-1)\)个交点,则增加\(4 \times(i-1)+1\)个平面,数据范围较小,直接递推即可
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 10050
using namespace std;
long long f[N];
int main() {
f[1] = 2;
for (int i = 2; i <= 10000; i++) {
f[i] = f[i - 1] + 4 * (i - 1) + 1;
}
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
printf("%lld\n", f[n]);
}
return 0;
}
CSU-2059 Water Problem
题目链接
https://vjudge.net/problem/CSU-2059
题面
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
题解
第i条线增加后,会增加\(9\times (i-1)\)个点,则产生点数加1个面,数据量较大,需算出通项公式,递推公式为
\[f[i]=f[i-1]+9\times(i-1)+1,f[1]=2
\]
则
\[f[n]=9\times(1+2...+n-1)+n+1=\frac{9n(n-1)}{2}+n+1
\]
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 10050
using namespace std;
long long f[N];
int main() {
int t;
scanf("%d", &t);
while (t--) {
long long n;
scanf("%lld", &n);
printf("%lld\n", 9 * n * (n - 1) / 2 + n + 1);
}
return 0;
}