您的位置: 首页  >  IT文章  >  2016 Multi-University Training Contest 3

2016 Multi-University Training Contest 3

分类: IT文章 • 2023-03-23 09:30:56

A - Sqrt Bo

签到题啦，直接套一个大数模板搞定。

不过我现在使用的大数模板不支持直接定义并赋值，bignum a = 1 这样是不行的。

　　
　　//查看了下代码发现，模板中bignum的构造函数，只有这一个，也就是定义一个大数，初始化为0(num[0]非0位数)
　　inline bignum()
    {
        memset(num,0,sizeof(bignum_t));
        num[0]=1 ;
        sgn=0 ;
    }

有因为模板中重载了=

    inline bignum&operator=(const int a)
    {
        memset(num,0,sizeof(bignum_t));
        num[0]=1 ;
        sgn=SGN (a);
        add(num,sgn*a);
        return*this ;
    }

所以可以采用：

bignum a;

a = 1233;

这种方法来定义一个静态大数。

//
//  main.cpp
//  multi2016.2.firtst
//
//  Created by New_Life on 16/8/1.
//  Copyright © 2016年 chenhuan001. All rights reserved.
//

#include <iostream>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

#define DIGIT   4      //四位隔开,即万进制
#define DEPTH   10000        //万进制
#define MAX     30    //题目最大位数/4，要不大直接设为最大位数也行
typedef int bignum_t[MAX+1];

/************************************************************************/
/* 读取操作数，对操作数进行处理存储在数组里                             */
/************************************************************************/
int read(bignum_t a,istream&is=cin)
{
    char buf[MAX*DIGIT+1],ch ;
    int i,j ;
    memset((void*)a,0,sizeof(bignum_t));
    if(!(is>>buf))return 0 ;
    for(a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)
        ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ;
    for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j<a[0]*DIGIT;buf[j++]='0');
    for(i=1;i<=a[0];i++)
        for(a[i]=0,j=0;j<DIGIT;j++)
            a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0' ;
    for(;!a[a[0]]&&a[0]>1;a[0]--);
    return 1 ;
}

void write(const bignum_t a,ostream&os=cout)
{
    int i,j ;
    for(os<<a[i=a[0]],i--;i;i--)
        for(j=DEPTH/10;j;j/=10)
            os<<a[i]/j%10 ;
}

int comp(const bignum_t a,const bignum_t b)
{
    int i ;
    if(a[0]!=b[0])
        return a[0]-b[0];
    for(i=a[0];i;i--)
        if(a[i]!=b[i])
            return a[i]-b[i];
    return 0 ;
}

int comp(const bignum_t a,const int b)
{
    int c[12]=
    {
    }
    ;
    for(c[1]=b;c[c[0]]>=DEPTH;c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);
    return comp(a,c);
}

int comp(const bignum_t a,const int c,const int d,const bignum_t b)
{
    int i,t=0,O=-DEPTH*2 ;
    if(b[0]-a[0]<d&&c)
        return 1 ;
    for(i=b[0];i>d;i--)
    {
        t=t*DEPTH+a[i-d]*c-b[i];
        if(t>0)return 1 ;
        if(t<O)return 0 ;
    }
    for(i=d;i;i--)
    {
        t=t*DEPTH-b[i];
        if(t>0)return 1 ;
        if(t<O)return 0 ;
    }
    return t>0 ;
}
/************************************************************************/
/* 大数与大数相加                                                       */
/************************************************************************/
void add(bignum_t a,const bignum_t b)
{
    int i ;
    for(i=1;i<=b[0];i++)
        if((a[i]+=b[i])>=DEPTH)
            a[i]-=DEPTH,a[i+1]++;
    if(b[0]>=a[0])
        a[0]=b[0];
    else
        for(;a[i]>=DEPTH&&i<a[0];a[i]-=DEPTH,i++,a[i]++);
    a[0]+=(a[a[0]+1]>0);
}
/************************************************************************/
/* 大数与小数相加                                                       */
/************************************************************************/
void add(bignum_t a,const int b)
{
    int i=1 ;
    for(a[1]+=b;a[i]>=DEPTH&&i<a[0];a[i+1]+=a[i]/DEPTH,a[i]%=DEPTH,i++);
    for(;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);
}
/************************************************************************/
/* 大数相减(被减数>=减数)                                               */
/************************************************************************/
void sub(bignum_t a,const bignum_t b)
{
    int i ;
    for(i=1;i<=b[0];i++)
        if((a[i]-=b[i])<0)
            a[i+1]--,a[i]+=DEPTH ;
    for(;a[i]<0;a[i]+=DEPTH,i++,a[i]--);
    for(;!a[a[0]]&&a[0]>1;a[0]--);
}
/************************************************************************/
/* 大数减去小数(被减数>=减数)                                           */
/************************************************************************/
void sub(bignum_t a,const int b)
{
    int i=1 ;
    for(a[1]-=b;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);
    for(;!a[a[0]]&&a[0]>1;a[0]--);
}

void sub(bignum_t a,const bignum_t b,const int c,const int d)
{
    int i,O=b[0]+d ;
    for(i=1+d;i<=O;i++)
        if((a[i]-=b[i-d]*c)<0)
            a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH ;
    for(;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);
    for(;!a[a[0]]&&a[0]>1;a[0]--);
}
/************************************************************************/
/* 大数相乘，读入被乘数a，乘数b，结果保存在c[]                          */
/************************************************************************/
void mul(bignum_t c,const bignum_t a,const bignum_t b)
{
    int i,j ;
    memset((void*)c,0,sizeof(bignum_t));
    for(c[0]=a[0]+b[0]-1,i=1;i<=a[0];i++)
        for(j=1;j<=b[0];j++)
            if((c[i+j-1]+=a[i]*b[j])>=DEPTH)
                c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH ;
    for(c[0]+=(c[c[0]+1]>0);!c[c[0]]&&c[0]>1;c[0]--);
}
/************************************************************************/
/* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数                   */
/************************************************************************/
void mul(bignum_t a,const int b)
{
    int i ;
    for(a[1]*=b,i=2;i<=a[0];i++)
    {
        a[i]*=b ;
        if(a[i-1]>=DEPTH)
            a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH ;
    }
    for(;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);
    for(;!a[a[0]]&&a[0]>1;a[0]--);
}

void mul(bignum_t b,const bignum_t a,const int c,const int d)
{
    int i ;
    memset((void*)b,0,sizeof(bignum_t));
    for(b[0]=a[0]+d,i=d+1;i<=b[0];i++)
        if((b[i]+=a[i-d]*c)>=DEPTH)
            b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH ;
    for(;b[b[0]+1];b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH);
    for(;!b[b[0]]&&b[0]>1;b[0]--);
}
/**************************************************************************/
/* 大数相除,读入被除数a，除数b，结果保存在c[]数组                         */
/* 需要comp()函数                                                         */
/**************************************************************************/
void div(bignum_t c,bignum_t a,const bignum_t b)
{
    int h,l,m,i ;
    memset((void*)c,0,sizeof(bignum_t));
    c[0]=(b[0]<a[0]+1)?(a[0]-b[0]+2):1 ;
    for(i=c[0];i;sub(a,b,c[i]=m,i-1),i--)
        for(h=DEPTH-1,l=0,m=(h+l+1)>>1;h>l;m=(h+l+1)>>1)
            if(comp(b,m,i-1,a))h=m-1 ;
            else l=m ;
    for(;!c[c[0]]&&c[0]>1;c[0]--);
    c[0]=c[0]>1?c[0]:1 ;
}

void div(bignum_t a,const int b,int&c)
{
    int i ;
    for(c=0,i=a[0];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);
    for(;!a[a[0]]&&a[0]>1;a[0]--);
}
/************************************************************************/
/* 大数平方根，读入大数a，结果保存在b[]数组里                           */
/* 需要comp()函数                                                       */
/************************************************************************/
void sqrt(bignum_t b,bignum_t a)
{
    int h,l,m,i ;
    memset((void*)b,0,sizeof(bignum_t));
    for(i=b[0]=(a[0]+1)>>1;i;sub(a,b,m,i-1),b[i]+=m,i--)
        for(h=DEPTH-1,l=0,b[i]=m=(h+l+1)>>1;h>l;b[i]=m=(h+l+1)>>1)
            if(comp(b,m,i-1,a))h=m-1 ;
            else l=m ;
    for(;!b[b[0]]&&b[0]>1;b[0]--);
    for(i=1;i<=b[0];b[i++]>>=1);
}
/************************************************************************/
/* 返回大数的长度                                                       */
/************************************************************************/
int length(const bignum_t a)
{
    int t,ret ;
    for(ret=(a[0]-1)*DIGIT,t=a[a[0]];t;t/=10,ret++);
    return ret>0?ret:1 ;
}
/************************************************************************/
/* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数               */
/************************************************************************/
int digit(const bignum_t a,const int b)
{
    int i,ret ;
    for(ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT;i;ret/=10,i--);
    return ret%10 ;
}
/************************************************************************/
/* 返回大数末尾0的个数                                                  */
/************************************************************************/
int zeronum(const bignum_t a)
{
    int ret,t ;
    for(ret=0;!a[ret+1];ret++);
    for(t=a[ret+1],ret*=DIGIT;!(t%10);t/=10,ret++);
    return ret ;
}

void comp(int*a,const int l,const int h,const int d)
{
    int i,j,t ;
    for(i=l;i<=h;i++)
        for(t=i,j=2;t>1;j++)
            while(!(t%j))
                a[j]+=d,t/=j ;
}

void convert(int*a,const int h,bignum_t b)
{
    int i,j,t=1 ;
    memset(b,0,sizeof(bignum_t));
    for(b[0]=b[1]=1,i=2;i<=h;i++)
        if(a[i])
            for(j=a[i];j;t*=i,j--)
                if(t*i>DEPTH)
                    mul(b,t),t=1 ;
    mul(b,t);
}
/************************************************************************/
/* 组合数                                                               */
/************************************************************************/
void combination(bignum_t a,int m,int n)
{
    int*t=new int[m+1];
    memset((void*)t,0,sizeof(int)*(m+1));
    comp(t,n+1,m,1);
    comp(t,2,m-n,-1);
    convert(t,m,a);
    delete[]t ;
}
/************************************************************************/
/* 排列数                                                               */
/************************************************************************/
void permutation(bignum_t a,int m,int n)
{
    int i,t=1 ;
    memset(a,0,sizeof(bignum_t));
    a[0]=a[1]=1 ;
    for(i=m-n+1;i<=m;t*=i++)
        if(t*i>DEPTH)
            mul(a,t),t=1 ;
    mul(a,t);
}

#define SGN(x) ((x)>0?1:((x)<0?-1:0))
#define ABS(x) ((x)>0?(x):-(x))

int read(bignum_t a,int&sgn,istream&is=cin)
{
    char str[MAX*DIGIT+2],ch,*buf ;
    int i,j ;
    memset((void*)a,0,sizeof(bignum_t));
    if(!(is>>str))return 0 ;
    buf=str,sgn=1 ;
    if(*buf=='-')sgn=-1,buf++;
    for(a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)
        ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ;
    for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j<a[0]*DIGIT;buf[j++]='0');
    for(i=1;i<=a[0];i++)
        for(a[i]=0,j=0;j<DIGIT;j++)
            a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0' ;
    for(;!a[a[0]]&&a[0]>1;a[0]--);
    if(a[0]==1&&!a[1])sgn=0 ;
    return 1 ;
}
struct bignum
{
    bignum_t num ;
    int sgn ;
    public :
    inline bignum()
    {
        printf("!!!
");
        memset(num,0,sizeof(bignum_t));
        num[0]=1 ;
        sgn=0 ;
    }
    inline int operator!()
    {
        return num[0]==1&&!num[1];
    }
    inline bignum&operator=(const bignum&a)
    {
        memcpy(num,a.num,sizeof(bignum_t));
        sgn=a.sgn ;
        return*this ;
    }
    inline bignum&operator=(const int a)
    {
        memset(num,0,sizeof(bignum_t));
        num[0]=1 ;
        sgn=SGN (a);
        add(num,sgn*a);
        return*this ;
    }
    ;
    inline bignum&operator+=(const bignum&a)
    {
        if(sgn==a.sgn)add(num,a.num);
        else if
            (sgn&&a.sgn)
        {
            int ret=comp(num,a.num);
            if(ret>0)sub(num,a.num);
            else if(ret<0)
            {
                bignum_t t ;
                memcpy(t,num,sizeof(bignum_t));
                memcpy(num,a.num,sizeof(bignum_t));
                sub (num,t);
                sgn=a.sgn ;
            }
            else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;
        }
        else if(!sgn)
            memcpy(num,a.num,sizeof(bignum_t)),sgn=a.sgn ;
        return*this ;
    }
    inline bignum&operator+=(const int a)
    {
        if(sgn*a>0)add(num,ABS(a));
        else if(sgn&&a)
        {
            int  ret=comp(num,ABS(a));
            if(ret>0)sub(num,ABS(a));
            else if(ret<0)
            {
                bignum_t t ;
                memcpy(t,num,sizeof(bignum_t));
                memset(num,0,sizeof(bignum_t));
                num[0]=1 ;
                add(num,ABS (a));
                sgn=-sgn ;
                sub(num,t);
            }
            else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;
        }
        else if
            (!sgn)sgn=SGN(a),add(num,ABS(a));
        return*this ;
    }
    inline bignum operator+(const bignum&a)
    {
        bignum ret ;
        memcpy(ret.num,num,sizeof (bignum_t));
        ret.sgn=sgn ;
        ret+=a ;
        return ret ;
    }
    inline bignum operator+(const int a)
    {
        bignum ret ;
        memcpy(ret.num,num,sizeof (bignum_t));
        ret.sgn=sgn ;
        ret+=a ;
        return ret ;
    }
    inline bignum&operator-=(const bignum&a)
    {
        if(sgn*a.sgn<0)add(num,a.num);
        else if
            (sgn&&a.sgn)
        {
            int ret=comp(num,a.num);
            if(ret>0)sub(num,a.num);
            else if(ret<0)
            {
                bignum_t t ;
                memcpy(t,num,sizeof(bignum_t));
                memcpy(num,a.num,sizeof(bignum_t));
                sub(num,t);
                sgn=-sgn ;
            }
            else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;
        }
        else if(!sgn)add (num,a.num),sgn=-a.sgn ;
        return*this ;
    }
    inline bignum&operator-=(const int a)
    {
        if(sgn*a<0)add(num,ABS(a));
        else if(sgn&&a)
        {
            int  ret=comp(num,ABS(a));
            if(ret>0)sub(num,ABS(a));
            else if(ret<0)
            {
                bignum_t t ;
                memcpy(t,num,sizeof(bignum_t));
                memset(num,0,sizeof(bignum_t));
                num[0]=1 ;
                add(num,ABS(a));
                sub(num,t);
                sgn=-sgn ;
            }
            else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;
        }
        else if
            (!sgn)sgn=-SGN(a),add(num,ABS(a));
        return*this ;
    }
    inline bignum operator-(const bignum&a)
    {
        bignum ret ;
        memcpy(ret.num,num,sizeof(bignum_t));
        ret.sgn=sgn ;
        ret-=a ;
        return ret ;
    }
    inline bignum operator-(const int a)
    {
        bignum ret ;
        memcpy(ret.num,num,sizeof(bignum_t));
        ret.sgn=sgn ;
        ret-=a ;
        return ret ;
    }
    inline bignum&operator*=(const bignum&a)
    {
        bignum_t t ;
        mul(t,num,a.num);
        memcpy(num,t,sizeof(bignum_t));
        sgn*=a.sgn ;
        return*this ;
    }
    inline bignum&operator*=(const int a)
    {
        mul(num,ABS(a));
        sgn*=SGN(a);
        return*this ;
    }
    inline bignum operator*(const bignum&a)
    {
        bignum ret ;
        mul(ret.num,num,a.num);
        ret.sgn=sgn*a.sgn ;
        return ret ;
    }
    inline bignum operator*(const int a)
    {
        bignum ret ;
        memcpy(ret.num,num,sizeof (bignum_t));
        mul(ret.num,ABS(a));
        ret.sgn=sgn*SGN(a);
        return ret ;
    }
    inline bignum&operator/=(const bignum&a)
    {
        bignum_t t ;
        div(t,num,a.num);
        memcpy (num,t,sizeof(bignum_t));
        sgn=(num[0]==1&&!num[1])?0:sgn*a.sgn ;
        return*this ;
    }
    inline bignum&operator/=(const int a)
    {
        int t ;
        div(num,ABS(a),t);
        sgn=(num[0]==1&&!num [1])?0:sgn*SGN(a);
        return*this ;
    }
    inline bignum operator/(const bignum&a)
    {
        bignum ret ;
        bignum_t t ;
        memcpy(t,num,sizeof(bignum_t));
        div(ret.num,t,a.num);
        ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*a.sgn ;
        return ret ;
    }
    inline bignum operator/(const int a)
    {
        bignum ret ;
        int t ;
        memcpy(ret.num,num,sizeof(bignum_t));
        div(ret.num,ABS(a),t);
        ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*SGN(a);
        return ret ;
    }
    inline bignum&operator%=(const bignum&a)
    {
        bignum_t t ;
        div(t,num,a.num);
        if(num[0]==1&&!num[1])sgn=0 ;
        return*this ;
    }
    inline int operator%=(const int a)
    {
        int t ;
        div(num,ABS(a),t);
        memset(num,0,sizeof (bignum_t));
        num[0]=1 ;
        add(num,t);
        return t ;
    }
    inline bignum operator%(const bignum&a)
    {
        bignum ret ;
        bignum_t t ;
        memcpy(ret.num,num,sizeof(bignum_t));
        div(t,ret.num,a.num);
        ret.sgn=(ret.num[0]==1&&!ret.num [1])?0:sgn ;
        return ret ;
    }
    inline int operator%(const int a)
    {
        bignum ret ;
        int t ;
        memcpy(ret.num,num,sizeof(bignum_t));
        div(ret.num,ABS(a),t);
        memset(ret.num,0,sizeof(bignum_t));
        ret.num[0]=1 ;
        add(ret.num,t);
        return t ;
    }
    inline bignum&operator++()
    {
        *this+=1 ;
        return*this ;
    }
    inline bignum&operator--()
    {
        *this-=1 ;
        return*this ;
    }
    ;
    inline int operator>(const bignum&a)
    {
        return sgn>0?(a.sgn>0?comp(num,a.num)>0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<0:0):a.sgn<0);
    }
    inline int operator>(const int a)
    {
        return sgn>0?(a>0?comp(num,a)>0:1):(sgn<0?(a<0?comp(num,-a)<0:0):a<0);
    }
    inline int operator>=(const bignum&a)
    {
        return sgn>0?(a.sgn>0?comp(num,a.num)>=0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<=0:0):a.sgn<=0);
    }
    inline int operator>=(const int a)
    {
        return sgn>0?(a>0?comp(num,a)>=0:1):(sgn<0?(a<0?comp(num,-a)<=0:0):a<=0);
    }
    inline int operator<(const bignum&a)
    {
        return sgn<0?(a.sgn<0?comp(num,a.num)>0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<0:0):a.sgn>0);
    }
    inline int operator<(const int a)
    {
        return sgn<0?(a<0?comp(num,-a)>0:1):(sgn>0?(a>0?comp(num,a)<0:0):a>0);
    }
    inline int operator<=(const bignum&a)
    {
        return sgn<0?(a.sgn<0?comp(num,a.num)>=0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<=0:0):a.sgn>=0);
    }
    inline int operator<=(const int a)
    {
        return sgn<0?(a<0?comp(num,-a)>=0:1):
        (sgn>0?(a>0?comp(num,a)<=0:0):a>=0);
    }
    inline int operator==(const bignum&a)
    {
        return(sgn==a.sgn)?!comp(num,a.num):0 ;
    }
    inline int operator==(const int a)
    {
        return(sgn*a>=0)?!comp(num,ABS(a)):0 ;
    }
    inline int operator!=(const bignum&a)
    {
        return(sgn==a.sgn)?comp(num,a.num):1 ;
    }
    inline int operator!=(const int a)
    {
        return(sgn*a>=0)?comp(num,ABS(a)):1 ;
    }
    inline int operator[](const int a)
    {
        return digit(num,a);
    }
    friend inline istream&operator>>(istream&is,bignum&a)
    {
        read(a.num,a.sgn,is);
        return  is ;
    }
    friend inline ostream&operator<<(ostream&os,const bignum&a)
    {
        if(a.sgn<0)
            os<<'-' ;
        write(a.num,os);
        return os ;
    }
    friend inline bignum sqrt(const bignum&a)
    {
        bignum ret ;
        bignum_t t ;
        memcpy(t,a.num,sizeof(bignum_t));
        sqrt(ret.num,t);
        ret.sgn=ret.num[0]!=1||ret.num[1];
        return ret ;
    }
    friend inline bignum sqrt(const bignum&a,bignum&b)
    {
        bignum ret ;
        memcpy(b.num,a.num,sizeof(bignum_t));
        sqrt(ret.num,b.num);
        ret.sgn=ret.num[0]!=1||ret.num[1];
        b.sgn=b.num[0]!=1||ret.num[1];
        return ret ;
    }
    inline int length()
    {
        return :: length(num);
    }
    inline int zeronum()
    {
        return :: zeronum(num);
    }
    inline bignum C(const int m,const int n)
    {
        combination(num,m,n);
        sgn=1 ;
        return*this ;
    }
    inline bignum P(const int m,const int n)
    {
        permutation(num,m,n);
        sgn=1 ;
        return*this ;
    }
};

/*
 int main()
 {
 bignum a,b,c;
 cin>>a>>b;
 cout<<"加法:"<<a+b<<endl;
 cout<<"减法:"<<a-b<<endl;
 cout<<"乘法:"<<a*b<<endl;
 cout<<"除法:"<<a/b<<endl;
 c=sqrt(a);
 cout<<"平方根:"<<c<<endl;
 cout<<"a的长度:"<<a.length()<<endl;
 cout<<"a的末尾0个数:"<<a.zeronum()<<endl<<endl;
 cout<<"组合: 从10个不同元素取3个元素组合的所有可能性为"<<c.C(10,3)<<endl;
 cout<<"排列: 从10个不同元素取3个元素排列的所有可能性为"<<c.P(10,3)<<endl;
 return 0 ;
 }
 */

int main(int argc, const char * argv[]) {
    bignum a;
    while(cin>>a)
    {
        int cnt=0;
        int flag=0;
        bignum b;
        b = 1;
        //cout<<b<<endl;
        //b += 1;
        while(a != b)
        {
            a = sqrt(a);
            //cout<<a<<endl;
            cnt++;
            if(cnt>5)
            {
                flag = 1;
                break;
                
            }
        }
        if(flag == 0) printf("%d
",cnt);
        else printf("TAT
");
    }
    return 0;
}
View Code

B - Permutation Bo

这题主要根据期望的可加性，将总的期望转变为求每一个位置的期望和。

然后推下公式就可以发现在最左边和最右边概率为(1/2)

在其他位置的为(1/3). 还得注意n＝＝1 的特殊情况。

//
//  main.cpp
//  multi2016.3.B
//
//  Created by New_Life on 16/8/1.
//  Copyright © 2016年 chenhuan001. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    while(cin>>n)
    {
        double ans = 0;
        for(int i=1;i<=n;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            if(i==1 || i==n) ans += (0.5)*tmp;
            else ans += (1.0/3.0)*tmp;
        }
        if(n==1)
        {
            ans *= 2;
        }
        printf("%.6lf
",ans);
    }
    return 0;
}
View Code

C - Life Winner Bo

不得不说这题就是个代码量稍微大一点的模拟题。

但是看了大家的题解后发现，怪不得大家做出来的这么多，原来直接用几种经典的博弈可以直接算出来，仔细一想确实把三种经典博弈全部都用上了。

我用的dp的方法，对于king 和 knight 直接dp搞就行了。

对于车和皇后，则则需要用额外的数组纪录下。

//
//  main.cpp
//  multi2016.3.J
//
//  Created by New_Life on 16/8/1.
//  Copyright © 2016年 chenhuan001. All rights reserved.
//

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int mark[1002][1002][4];
int save[1002][1002][3];//三个方向

//处理king和kinght
int dfs(int x,int y,int type)
{
    if(mark[x][y][type] != -1) return mark[x][y][type];
    int flag = 0;
    int flag2 = 0;
    
    if(type == 0)
    {
        if(x+1<=1000 && dfs(x+1,y,type)==0) flag=1;
        
        if(y+1<=1000 && dfs(x,y+1,type)==0) flag=1;
        
        if(x+1<=1000 && y+1<=1000 && dfs(x+1,y+1,type)==0) flag=1;
        
        return mark[x][y][type]=flag;
    }
    else //只有这里会存在。。。平局
    {
        flag = -1;
        if(x+2<=1000 && y+1<=1000)
        {
            if(dfs(x+2,y+1,type) == 0)
            {
                flag = 1;
            }
            else if(dfs(x+2,y+1,type) == 2) flag2= 1;
            else flag = 0;
            
        }
        if(y+2<=1000 && x+1<=1000)
        {
            if(dfs(x+1,y+2,type)==0) flag = 1;
            else if(dfs(x+1,y+2,type)==2) flag2 =1;
            else flag = 0;
        }
        if(flag == 1) return mark[x][y][type] = 1;//能必胜
        else if(flag2 == 1 || flag == -1) return mark[x][y][type] = 2;
        else
        {
            return mark[x][y][type] = 0;
        }
    }
}

int main() {
    memset(mark,-1,sizeof(mark));
    for(int i=0;i<4;i++)
        mark[1000][1000][i] = 0;
    for(int i=1;i<=1000;i++)
        for(int j=1;j<=1000;j++)
            for(int k=0;k<2;k++)
            {
                dfs(i,j,k);
            }
    //然后来搞车
    int x[1002],y[1002];
    memset(x, 0, sizeof(x));
    memset(y, 0, sizeof(y));
    for(int i=1000;i>=1;i--)
        for(int j=1000;j>=1;j--)
        {
            int flag = 0;
            if( x[i]==1 || y[j]==1 ) flag = 1;
            
            mark[i][j][2] = flag;
            if(flag == 0)
            {
                x[i] = 1;
                y[j] = 1;
            }
        }
    
    //这里还是错了
    for(int i=1000;i>=1;i--)
        for(int j=1000;j>=1;j--)
        {
            int flag=0;
            if(i+1<=1000 && save[i+1][j][0]==1) flag = 1;
            if(j+1<=1000 && save[i][j+1][1]==1) flag = 1;
            if(i+1<=1000 && j+1<=1000 && save[i+1][j+1][2]==1) flag = 1;
            
            mark[i][j][3] = flag;
            
            if(flag == 0)
            {
                save[i][j][0] = 1;
                save[i][j][1] = 1;
                save[i][j][2] = 1;
            }
            else
            {
                save[i][j][0] = save[i+1][j][0];
                save[i][j][1] = save[i][j+1][1];
                save[i][j][2] = save[i+1][j+1][2];
            }
        }
    int T;
    cin>>T;
    while(T--)
    {
        int type,n,m;
        cin>>type>>n>>m;
        if(type == 1) type = 0;
        if(type == 2) type = 2;
        if(type == 3) type = 1;
        if(type == 4) type = 3;
        int flag = mark[1000-n+1][1000-m+1][type];
        
        if(flag == 0) printf("G");
        else if(flag == 1) printf("B");
        else printf("D");
        
        printf("
");
    }
    return 0;
}

/*
 10
 1 5 5
 2 5 5
 3 5 5
 4 5 5
 3 2 2
 3 2 3
 3 3 5
 
 ans:
 G
 G
 D
 B
 D
 B
 D
*/
View Code

D - Gambler Bo

用构造，二分图，dp什么的鬼想法想了一下午。 后面看题解发现是高斯消元裸题，简直要撞墙。。。 md taicaile

如果用高斯消元的方法就很好想了。

不过这题还是个线性同余方程组。

具体参见。

 G - Explorer Bo

首先这题确定的最小的移动次数。

稍作分析可以发现，当叶节点个数为偶数时，移动次数必为 (叶节点总数/2)

当叶节点个数为奇数时，移动次数比为（叶节点总数+1）/2

对于偶数的情况，很好分析。 对于每一条树边，如果两侧的叶节点个数都为偶数，那么这条树边必会走两次，否则只需要走一次。这样一趟 dfs 就可以搞定

对于奇数的情况，则需要唯一确定一条不用两端都为叶节点的路径。用树形dp和线段树都可以解决。 我用的线段树.

//
//  main.cpp
//  hdu5758
//
//  Created by New_Life on 16/8/3.
//  Copyright &#169; 2016年 chenhuan001. All rights reserved.
//

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 100100

int n;
struct node{
    int to,next;
}edge[2*N];

int cnt,pre[N];
int leafid;
int savel[N],saver[N];
int ans;

void add_edge(int u,int v)
{
    edge[cnt].to = v;
    edge[cnt].next = pre[u];
    pre[u] = cnt++;
}

void dfs(int s,int fa,int first)
{
    int flag = 0;//是否是叶子结点
    int saveid = leafid;
    for(int p = pre[s];p!=-1;p=edge[p].next)
    {
        int v = edge[p].to;
        if(v == fa) continue;
        flag ++;
        dfs(v,s,0);
    }
    
    if(first == 1)
    {
        if(flag == 1)//is leaf
        {
            leafid++;
        }
    }
    else
    if(flag == 0)
    {
        leafid++;
    }
    savel[s] = saveid+1;
    saver[s] = leafid;
}

void dfs1(int s,int fa)
{
    for(int p=pre[s];p!=-1;p=edge[p].next)
    {
        int v = edge[p].to;
        if(v == fa) continue;
        int x1 = saver[v]-savel[v]+1;
        //int x2 = leafid - x1;
        ans += (2-x1%2);
        dfs1(v,s);
    }
}

#define max(a,b) (a>b)?a:b
#define min(a,b) (a>b)?b:a
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

#define LL long long

const int maxn = N;
LL lazy[maxn<<2];
LL sum[maxn<<2];

void putup(int rt)
{
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void putdown(int rt,int m)
{
    if (lazy[rt])
    {
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        sum[rt<<1] += lazy[rt] * (m - (m >> 1));
        sum[rt<<1|1] += lazy[rt] * (m >> 1);
        lazy[rt] = 0;
    }
}
void build(int l,int r,int rt) {
    lazy[rt] = 0;
    if (l == r)
    {
        sum[rt] = 0;
        //scanf("%I64d",&sum[rt]);
        return ;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    putup(rt);
}
void update(int L,int R,int c,int l,int r,int rt)
{
    if (L <= l && r <= R)
    {
        lazy[rt] += c;
        sum[rt] += (LL)c * (r - l + 1);
        return ;
    }
    putdown(rt , r - l + 1);
    int m = (l + r) >> 1;
    if (L <= m) update(L , R , c , lson);
    if (m < R) update(L , R , c , rson);
    putup(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
    if (L <= l && r <= R)
    {
        return sum[rt];
    }
    putdown(rt , r - l + 1);
    int m = (l + r) >> 1;
    LL ret = 0;
    if (L <= m) ret += query(L , R , lson);
    if (m < R) ret += query(L , R , rson);
    return ret;
}
/*
 int main()
 {
 int n , m;int a , b , c;
 char str[5];
 scanf("%d%d",&n,&m);
 build(1 , n , 1);
 while (m--)
 {
 scanf("%s",str);
 if (str[0] == 'Q')
 {
 scanf("%d%d",&a,&b);
 printf("%I64d
",query(a , b , 1 , n , 1));
 }
 else if(str[0]=='C')
 {
 scanf("%d%d%d",&a,&b,&c);
 update(a , b , c , 1 , n , 1);
 }
 }
 return 0;
 }
 */

void dfs2(int s,int fa)
{
    for(int p=pre[s];p!=-1;p=edge[p].next)
    {
        int v = edge[p].to;
        if(v == fa) continue;
        int x1 = saver[v]-savel[v]+1;
        int x2 = leafid - x1;
        int tmp1=0,tmp2=0;
        
        x1--;
        if(x1!=0) tmp1 = (2-x1%2);
        else tmp1 = 1;
        x1 ++;
        
        x2--;
        if(x2!=0) tmp2 = (2-x2%2);
        else tmp2 = 1;
        x2++;
        
        update(1,leafid,tmp2,1,leafid,1);
        update(savel[v],saver[v],tmp1-tmp2,1,leafid,1);
        dfs2(v,s);
    }
}

int main(int argc, const char * argv[]) {
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        cnt = 0;
        memset(pre,-1,sizeof(pre));
        for(int i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add_edge(x,y);
            add_edge(y,x);
        }
        if(n == 1)
        {
            printf("0
");
            continue;
        }
        leafid = 0;
        dfs(1, -1, 1);//第一遍建立线段区间，且得出有多少叶节点.
        
        ans = 0;
        if(leafid%2 == 0)//叶节点为偶数
        {
            //一趟dfs搞定
            dfs1(1, -1);
        }
        else
        {
            build(1, leafid, 1);
            dfs2(1,-1);
            ans = 1000000000;
            for(int i=1;i<=leafid;i++)
            {
                ans = min(ans,(int)query(i, i, 1, leafid, 1));
            }
        }
        printf("%d
",ans);
    }
    return 0;
}
/*
 10
 4
 1 2
 2 3
 3 4
 5
 1 5
 5 2
 2 3
 2 4
 9
 1 2
 2 3
 2 4
 3 5
 3 6
 4 7
 7 8
 7 9
 
 */
View Code

J - Rower Bo

应该是高中的物理竞赛会考的东西。

这种巧妙的公式，没做过的人好难。 听说很多人都是直接猜的公式，这场比赛3题都可以找规律。 orz

2016 Multi-University Training Contest 3

K - Teacher Bo

因为n*m的图的曼哈顿距离最多有2*(n+m)种，所以当n>500 时必有相同点，n<500直接暴力。

//
//  main.cpp
//  multi2016.3.B
//
//  Created by New_Life on 16/8/1.
//  Copyright © 2016年 chenhuan001. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;

struct point
{
    int x,y;
}g[100100];

int mark[200200];

//仅适合纯数字输入
int Scan()     //输入外挂
{
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
void Out(int a)    //输出外挂
{
    if(a>9)
        Out(a/10);
    putchar(a%10+'0');
}

int main(int argc, const char * argv[]) {
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        
        for(int i=0;i<n;i++)
        {
            g[i].x = Scan();
            g[i].y = Scan();
        }
        if(n>500) printf("YES
");
        else
        {
            memset(mark,0,sizeof(mark));
            //for(int i=0;i<2*m;i++)
            int flag=0;
            for(int i=0;i<n;i++)
            {
                if(flag) break;
                for(int j=i+1;j<n;j++)
                {
                    int tmp = abs(g[i].x-g[j].x)+abs(g[i].y-g[j].y);
                    mark[ tmp ]++;
                    if(mark[tmp] >= 2)
                    {
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag) printf("YES
");
            else printf("NO
");
            
        }
    }
    return 0;
}
View Code

相关推荐