2.cpp

一次比赛的代码,有五道题,2,4比较基础,3题是模拟,1高精度,5树状dp

#include <iostream.h>
#include <string.h>
#define maxn 101
#define DIGIT	4
#define DEPTH	10000
#define MAX     100
typedef int bignum_t [MAX+1];
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 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;
}


bignum_t a1[maxn],cell[maxn];//a1纪录每小时新产生的细胞，cell纪录该小时细胞数

void precalc()
{
	
    int i;
	a1[2][0]=1;a1[1][1]=1;a1[1][0]=1;a1[3][1]=1;a1[3][0]=1;a1[4][1]=2;a1[4][0]=1;a1[5][0]=1;a1[5][1]=2;
    for (i=6;i<maxn;i++)
    {
	
		memset(a1[i],0,sizeof(a1[i]));
		a1[i][0] = 1;
		add(a1[i],a1[i-2]);
		add(a1[i],a1[i-3]);
		add(a1[i],a1[i-3]);
		add(a1[i],a1[i-4]);
	}
    cell[1][0]=1;cell[1][1]=1;
	cell[2][0]=1;cell[2][1]=1;
	cell[3][0]=1;cell[3][1]=2;
	cell[4][0]=1;cell[4][1]=4;
	for (i=5;i<maxn;i++)
	{
		
		memset(cell[i],0,sizeof(cell[i]));
		cell[i][0] =1;
		add(cell[i],a1[i]);
		add(cell[i],a1[i-1]);
		add(cell[i],a1[i-2]);
		add(cell[i],a1[i-3]);
		add(cell[i],a1[i-4]);
	}
}
int main()
{
    int i;
    precalc();
	cout<<"1~30小时后的细胞数"<<endl;	
	for (i=2;i<=31;i++)
	{
	
		cout<<i<<"小时候的细胞数为:  ";
		write(cell[i],cout);
		cout<<endl;
	}
	cout<<endl;
	cout<<"第100小时的细胞数为: ";
	write(cell[100],cout);
	cout<<endl;

	return 0;
}