链接:https://www.nowcoder.com/acm/contest/180/A
来源:牛客网
题目描述
小a的平面上有n个X型不明物体,但是他不确定他们的位置。现在请你来确定他们的位置,使得划分形成的平面尽量多
输入描述:
一个整数n,如题所示
输出描述:
一个整数,表示最多把平面分成多少份
示例1
输入
2
输出
11
说明
备注:
n ≤ 109
【题解】
定理:n条直线最多能把空间划分为n(n-1)/2+1份。
我们可以把X型看做两条不相交的直线,因此答案为2n(2n-1)/2+1。
证明:
对于第n条直线,如果使得区域增加k个,当且仅当它与k-1条直线相交。
而我们之前已经构造好了n-1条两两相交的直线,且三三不相交的直线,因此第n条直线一定可以找到一种方法使得与n-1条直线相交。
因此ans=1+1+2+3+...+n,直接上等差数列求和公式。
【递推】
1条直线分割平面数最多为2;a1=2
2条直线分割平面数最多为4;为1条直线时分割数目+2,即a2=a1+2
3条直线分割平面数最多为7;为2条直线时分割数目+3,即a3=a2+3=a1+2+3
4条直线分割平面数最多为11;为3条直线时分割数目+4,即a4=a3+4=a1+2+3+4
5条直线分割平面数最多为16;为4条直线时分割数目+5,即a5=a4+5=a1+2+3+4+5
6条直线分割平面数最多为22;为5条直线时分割数目+6,即a6=a5+6=a1+2+3+4+5+6
因此an=a1+2+3+...+n。
可以看到分割的平面数的差值按照等差数列递增;
因此第N条直线分割的最多平面数为:n(n-1)/2+1。
#include<cstdio> using namespace std; int main(){ long long a; scanf("%lld",&a); printf("%lld ",(a*((a<<1)+1)+1)); return 0; }
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int MAXN = 2001 * 2, INF = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int main() { long long n = read(); long long ans = n * (2 * n + 1) + 1; printf("%lld ", ans); return 0; }