A - 规律题

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

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

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

Sample Input

Sample Output

2

7

找规律，一条线，区域为2，两条线，区域是2+2，为4，但是因为是折线，相交处没有延申，总数要-2，得2。三条线区域2+3，四条线区域5+4，同样实际数目也要-2，结果为7；
以此类推，设n为当前折线数目，得出公式f(n)=f(n-1)+2n+2n-1-2=f(n-1)+4*n-3；
可以将f(0)=1看作首项，则到第n个时，f(n)=1+4+8+…+4n-3n=2*n*n-n+1。

f(n)=2*n*n -n + 1
直线
n s(n)
1 2  1+1
2 4  1+1+2
3 7  1+1+2+3
n n*(n+1)/2+1
折线
n s2(n) d=s-s2    s
1  2    2         4
2  7    4         11
3  16   6         22
n  　　　2n       s

 1 #include <stdio.h>

 2 int main()

 3 {

 4     int t;

 5     scanf("%d",&t);

 6     while(t--)

 7     {

 8         int x;

 9         scanf("%d",&x);

10         printf("%lld\n",x*x*2-x+1);

11     }

12 }

巴特西

A - 规律题

最新文章

热门文章