首页 > 代码库 > HDU 5047 Sawtooth(数学 公式 大数)

HDU 5047 Sawtooth(数学 公式 大数)

2024-07-24 18:02:24   228人阅读

题目链接：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
2
1
2
 

Sample Output
Case #1: 2
Case #2: 19
 

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]='\0';
    }
    else
    {
        for (i=0; i<=max; i++)
            c[i]=s[i];
        c[i]='\0';
    }
    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]=='\0')
        {
            c[0]='0';
            c[1]='\0';
        }
        else
        {
            for (j=0; a[i]!='\0'; i++,j++)
                c[j]=a[i];
            c[j]='\0';
        }
    }
    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]!='\0'; i++,j++)
            c[i]=b[j];
        c[i]='\0';
    }
}

/* 大数乘法*/
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]='\0';
    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]='\0';
    for (i=0; s[i]=='0'&&s[i]!='\0'; i++);
    if (s[i]=='\0')
    {
        c[0]='0';
        c[1]='\0';
    }
    else
    {
        for (j=0; s[i]!='\0'; i++,j++)
            c[j]=s[i];
        c[j]='\0';
    }
    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] = '\0';
    b[0] = '7';
    b[1] = '\0';
    c[0] = '1';
    c[1] = '\0';
    int t;
    int cas = 0;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        memset(ans,'\0',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\n",++cas,ans);
    }
    return 0;
}

//8*n^2 - 7*n + 1


HDU 5047 Sawtooth(数学 公式 大数)


联系
我们