HDU-2050变式拓展

原始题目

2059: Water Problem

• Time Limit: 1 Sec
  
• Memory Limit: 128 Mb
  
• Submitted: 576
  
• Solved: 199
  ### 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

Source

Author

csutsz

题目大意

如题

解题思路

• 先推导递推式，由于数据量大，再推导通项公式最后直接输出。
• 分析：第i条z形线比第i-1条z形线新分成的最多区域数为新增最多交点个数+1
  • 第i条线最多与前i-1条z形线交 \(4\*(i-1)\) 个点。 \[ dp[i]=dp[i-1]+4\*(i-1)+! , dp[1]=2 \]
  • 所以得到通项公式 \[ dp[i]=\frac{9\*(i-1)\*(i)}{2}+i+1 \]

解题代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
const int maxn=1e8+2;
typedef long long ll;

using namespace std;
int main(){
	int t;
	cin>>t;
	for(ll i=0;i<t;i++){
		ll a;
		cin>>a;
		if(a==1) cout<<2<<endl;
		else cout<<9*(a-1)*(a)/2+a+1<<endl;
	}
}

收获与反思

• 折线，z形线，类似的都转化到与新增交点数的关系。