1.cpp

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

#include <iostream>
#include <string>
using namespace std;
#define DIGIT	4
#define DEPTH	10000
#define MAX     100
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;
}
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 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]--);
}
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]--);
}
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]--);
}
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;
}
int test(const bignum_t x,const bignum_t s)//测试p^3+p^p+3*p与n;
{
	bignum_t p1,p2;
	memset(p1,0,sizeof(p1));
	memset(p2,0,sizeof(p2));
	mul(p1,x,x);
	mul(p2,p1,x);
	return comp(s,p2);
}
int f(int l)
{
	int temp=1;
	while (l--) temp*=10;
	return temp;
}
int main()
{   int m ;
	cin>>m;
	freopen("number1_input.txt","r",stdin);
	freopen("number1_out.txt","w",stdout);
	bignum_t a,begin,end,mid,n;
	int c;
	a[0]=1;a[1]=4;
	read(n,cin);
	memset(end,0,sizeof(end));
	memset(begin,0,sizeof(begin));
	begin[0]=1;begin[1]=0;
	add(end,n);
	while(comp(begin,end)<0)
	{
		memset(mid,0,sizeof(mid));
		add(mid,begin);
		add(mid,end);
		div(mid,2,c);
		if (test(mid,n)<0) {
			memset(end,0,sizeof(end));
			add(end,mid);
			add(end,-1);
		}
		else
		{
			memset(begin,0,sizeof(begin));
			add
				(begin,mid);
			add(begin,1);	
		}
	}
	int num;
	num = length(begin);
	if(num < m)
	{
		cout<<0;

	}
	else
	{
		if (m == num) 
		{
			begin[num/4+1]-=f(num%4-1);
			add(begin,1);
		    write(begin,cout);
			add(begin,-1);
			begin[num/4+1]+=f(num%4-1);
		}
		else 
		{
			cout<<9;
			while (--m) cout<<0;
			cout<<endl;
		}
	}
	cout<<"P的最大值=";
	write(end,cout);
	cout<<endl;
	return 1;
}