Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于在第二十二次AC啦

Posted by cgxinyan at 2009-02-22 03:59:20
虽然我ac的代码也是很不优化的,但始终是被ac啦不是吗,算不上牛但至少也不再是
╭︿︿︿╮ 
{/ o  o /}  猪啦撒。
 ( (oo) )   
  ︶ ︶︶猪

废话少说,还是来介绍我的1.0版本撒。这里说是1.0,今后还会写出更优的2.0,3.0……跟大家交流。
1、标记小数点位置,采用大整数模拟高精度浮点数;
2、采用大整数的乘法计算大整数的乘方运算;
3、采用数组模拟大整数的乘法;
4、具体的运算方法是模拟的一般在草纸上的乘法计算方法;
5、令原始的大整数为r;
6、用数组中的每一个元素去乘r,将值保存在一个二维数组中,并按照乘方的规则对齐;
7、将上述的二维数组的各列元素分别相加,并记录到目标数组(一维)中相应的列。
注意:
1、注意检查是否有前导或者后续的零或者不需要显示的小数点;
2、对R的一次方是否满足。
3、用了64位的整形__int64。

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	__int64 temp,r=0;
	int temparr[500][500],arr1[500],arr2[500],arr[500];
	int lenth=0,lenth1=0,lenth2=0,i=0,j=0,k=0,m=0,col=0,maxcol=0,z=0;
	int n;
	long double R,x;
	char lastarr[500];
	while(scanf("%lf %d",&R,&n)==2)
{
		for(i=0;i<500;i++)
		{
			arr[i]=0;
			arr1[i]=0;
			arr2[i]=0;
			for(j=0;j<500;j++)
			{
				temparr[i][j]=0;
			}
		}
		n=n-1;
		z=(int)(floor(R));
		x=R-z;
		i=0;
		while(z)
		{
			arr1[i]=z%10;
			z=z/10;
			i++;
		}
		lenth1=i;i=0;
		while(fabs(x-0)>pow((long double)(10),-6))
		{
			arr2[i]=floor(x*10);
			x=x*10-arr2[i];
			i++;
			if(i>4)
				break;
		}
		if(arr2[4]>7)arr2[3]+=1;
		lenth2=i-1;
		if(arr2[4]<5)lenth2=i;
		i=0;

		for(i=0;i<lenth2;i++)
		{
			arr[i]=arr2[lenth2-i-1];
		}
		for(i=0;i<lenth1;i++)
		{
			arr[i+lenth2]=arr1[i];
		}
		lenth=lenth1+lenth2;
		for(i=3;i>=0;i--)
		{
			if(arr2[i]==0)
				continue;
			lenth2=i+1;
			break;
		}
		lenth2*=n+1;
		for(i=0;i<lenth;i++)
		{
			r+=pow((long double)(10),lenth-1-i)*arr[lenth-1-i];
		}
	if(n==0)goto yes;
		do{
			for(i=0;i<lenth;i++)
			{
				temp=r*arr[i];//
				j=0;
				while(temp)
				{
					temparr[i][i+j]=temp%10;
					temp=temp/10;
					j++;
				}
				for(m=0;m<i;m++)
				{
					temparr[i][m]=0;
				}
				m=0;
				if(maxcol<i+j)
					maxcol=i+j;
			}
			n--;	

			for(i=0;i<500;i++)arr[i]=0;
			col=0;
			for(i=0;i<maxcol;i++)
			{
				for(k=0;k<lenth;k++)
				{
					arr[col]+=temparr[k][i];
				}
				col++;
			}
			for(k=0;k<col+2;k++)
			{
				if(arr[k]>9)
				{
					z=arr[k];
					z=z/10;
					if(arr[k]>99)
						arr[k]=arr[k]%100;
					else
						arr[k]=arr[k]%10;
					arr[k+1]+=z;
				}
				for(i=col+10;;i--)
				{
					if(arr[i]!=0)
					{
						lenth=i+1;
						break;
					}
				}
			}
			for(i=0;i<500;i++)
			{
				for(j=0;j<500;j++)
				{
					temparr[i][j]=0;
				}
			}
		}while(n);
yes:
	if(lenth<lenth2)
	{	lastarr[0]='.';
		for(i=0;i<lenth;i++)
		{
			lastarr[lenth2-i]=arr[i]+'0';
		}
		for(i=lenth;i<lenth2/*-lenth*/;i++)
		{
			lastarr[lenth2-i]='0';
		}
		for(i=0;i<lenth2+1;i++)
			cout<<lastarr[i];
	}
	else if(lenth==lenth2)
	{
		lastarr[0]='.';
		for(i=1;i<lenth+1;i++)
			lastarr[i]=arr[lenth2-i];
		for(i=0;i<lenth+1;i++)
			cout<<lastarr[i];
	}
	else
	{
		if(lenth2!=0){
			j=lenth-lenth2;lastarr[j]='.';
			for(i=0;i<lenth;i++)
			{
				if(i<lenth2)
				{
					lastarr[lenth-i]=arr[i]+'0';
					continue;
				}
				lastarr[lenth-i-1]=arr[i]+'0';
			}
			i=lenth;
			while(1)
			{
				if(lastarr[i]=='0')
				{
					i--;
					continue;
				}
				break;
			}
			lenth=i;
			for(i=0;i<lenth+1;i++)
			{cout<<lastarr[i];}
		}
		else
			for(i=0;i<lenth;i++)
				cout<<arr[lenth-i-1];
	}
	cout<<endl;
	lenth=0;lenth1=0;lenth2=0;i=0;j=0;k=0;m=0;col=0;maxcol=0;z=0;r=0;
}
	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator