HDU 5047 Sawtooth(数学 公式 大数)
来源：程序员人生 发布时间：2014-10-09 03:04:26 阅读次数：3025次
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5047
Problem Description
Think about a plane:
● One straight line can divide a plane into two regions.
● Two lines can divide a plane into at most four regions.
● Three lines can divide a plane into at most seven regions.
● And so on...
Now we have some figure constructed with two parallel rays in the same direction, joined by two straight segments. It looks like a character “M”. You are given N such “M”s. What is the maximum number of regions that these “M”s can divide a plane ?
Input
The first line of the input is T (1 ≤ T ≤ 100000), which stands for the number of test cases you need to solve.
Each case contains one single non-negative integer, indicating number of “M”s. (0 ≤ N ≤ 1012)
Output
For each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning. Then an integer that is the maximum number of regions N the “M” figures can divide.
Sample Input
Sample Output
Source
2014 ACM/ICPC Asia Regional Shanghai Online
PS:
推出公式：8*n^2 - 7*n + 1 ，套一下模板就好了！ 不过很多大数模板这题是会T的，不过这个模板：http://blog.csdn.net/u012860063/article/details/39612037 多亏了队友的神模板2333333！
代码如下：
#include <cstdio>
#include <cstring>
#include <malloc.h>
/*大数加法*/
void add(char* a,char* b,char* c)
{
int i,j,k,max,min,n,temp;
char *s,*pmax,*pmin;
max=strlen(a);
min=strlen(b);
if (max<min)
{
temp=max;
max=min;
min=temp;
pmax=b;
pmin=a;
}
else
{
pmax=a;
pmin=b;
}
s=(char*)malloc(sizeof(char)*(max+1));
s[0]='0';
for (i=min-1,j=max-1,k=max; i>=0; i--,j--,k--)
s[k]=pmin[i]-'0'+pmax[j];
for (; j>=0; j--,k--)
s[k]=pmax[j];
for (i=max; i>=0; i--)
if (s[i]>'9')
{
s[i]-=10;
s[i-1]++;
}
if (s[0]=='0')
{
for (i=0; i<=max; i++)
c[i-1]=s[i];
c[i-1]=' ';
}
else
{
for (i=0; i<=max; i++)
c[i]=s[i];
c[i]=' ';
}
free(s);
}
/*大数减法*/
void subtract(char* a,char* b,char* c)
{
int i,j,ca,cb;
ca=strlen(a);
cb=strlen(b);
if (ca>cb||(ca==cb&&strcmp(a,b)>=0))
{
for (i=ca-1,j=cb-1; j>=0; i--,j--)
a[i]-=(b[j]-'0');
for (i=ca-1; i>=0; i--)
if (a[i]<'0')
{
a[i]+=10;
a[i-1]--;
}
i=0;
while (a[i]=='0')
i++;
if (a[i]==' ')
{
c[0]='0';
c[1]=' ';
}
else
{
for (j=0; a[i]!=' '; i++,j++)
c[j]=a[i];
c[j]=' ';
}
}
else
{
for (i=ca-1,j=cb-1; i>=0; i--,j--)
b[j]-=(a[i]-'0');
for (j=cb-1; j>=0; j--)
if (b[j]<'0')
{
b[j]+=10;
b[j-1]--;
}
j=0;
while (b[j]=='0')
j++;
i=1;
c[0]='-';
for (; b[j]!=' '; i++,j++)
c[i]=b[j];
c[i]=' ';
}
}
/* 大数乘法*/
void multiply(char* a,char* b,char* c)
{
int i,j,ca,cb,* s;
ca=strlen(a);
cb=strlen(b);
s=(int*)malloc(sizeof(int)*(ca+cb));
for (i=0; i<ca+cb; i++)
s[i]=0;
for (i=0; i<ca; i++)
for (j=0; j<cb; j++)
s[i+j+1]+=(a[i]-'0')*(b[j]-'0');
for (i=ca+cb-1; i>=0; i--)
if (s[i]>=10)
{
s[i-1]+=s[i]/10;
s[i]%=10;
}
i=0;
while (s[i]==0)
i++;
for (j=0; i<ca+cb; i++,j++)
c[j]=s[i]+'0';
c[j]=' ';
free(s);
}
/*大数除法,返回余数*/
int dividor(char* a,int b,char* c)
{
int i,j,temp=0,n;
char* s;
n=strlen(a);
s=(char*)malloc(sizeof(char)*(n+1));
for (i=0; a[i]!=0; i++)
{
temp=temp*10+a[i]-'0';
s[i]=temp/b+'0';
temp%=b;
}
s[i]=' ';
for (i=0; s[i]=='0'&&s[i]!=' '; i++);
if (s[i]==' ')
{
c[0]='0';
c[1]=' ';
}
else
{
for (j=0; s[i]!=' '; i++,j++)
c[j]=s[i];
c[j]=' ';
}
free(s);
return temp;
}
const int maxn = 1017;
char s[maxn], t1[maxn], t2[maxn], t3[maxn];
char a[17], b[17], c[17];
char ans[maxn];
int main()
{
a[0] = '8';
a[1] = ' ';
b[0] = '7';
b[1] = ' ';
c[0] = '1';
c[1] = ' ';
int t;
int cas = 0;
scanf("%d",&t);
getchar();
while(t--)
{
memset(ans,' ',sizeof(ans));
gets(s);
multiply(s,s,t1);//n^2
multiply(t1,a,t2);//8*n^2
multiply(b,s,t3);//7*n
subtract(t2,t3,ans);//8*n^2 - 7*n
add(ans,c,ans);//8*n^2 - 7*n + 1
printf("Case #%d: %s
",++cas,ans);
}
return 0;
}
//8*n^2 - 7*n + 1
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
