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 derness at 2007-07-24 16:23:06 on Problem 3286
#include<iostream>
#include<cstring>
using namespace std;
int count_0(int *a){
	int len =32;
	int fg=0;
	int count=0;
	for(int m=len-1;m>=0;m--){
		if(a[m] !=0){
			fg = m;
			break;
		}
	}
	if(fg ==0){
		if(a[0]==0)
			count =1;
		return count;
	}
	for(int k=fg;k>=0;k--)
	{
		if(a[k] ==0)
			count++;
	}
	return count;
}
int main(void)
{
	char m[32],n[32];
	int len_m,len_n,i,j;
	unsigned int p,q,flag;
	unsigned c[100]={0};
	unsigned d[2]={0};
	int pair=0;
	int fgl;
	while(cin>>m>>n)
	{
		int a[32]={0},b[32]={0};
        p=atoi(m);
		q=atoi(n);
		if(p == -1){
			break;
		}else{
			len_m=strlen(m);
			len_n=strlen(n);
			for(i=0;i<len_m;i++)
				a[i]=m[len_m-1-i]-48;
			for(j=0;j<len_n;j++)
				b[j]=n[len_n-1-j]-48;
			flag = q-p;
			if(flag==0){
				c[pair]=count_0(a);
				pair++;
				break;
			}
			if(flag !=0){
				d[0]=count_0(a);
				c[pair]=d[0];
				for(unsigned index=1;index<= flag;index++){
					int increment=0;
					if(a[0]==0){
						a[0]++;
						increment = -1;
						d[1]=d[0]+increment;
						c[pair] += d[1];
						d[0]=d[1];						
						continue;
					}
					a[0]++;
					for(int m=31;m>=0;m--){
						if(a[m] !=0){
							fgl = m;
							break;
						}
					}
					for(i=0;i<=fgl;i++){
						if(a[i]>=10){
							a[i+1]++;
							if(a[i+1] == 1 && i!=fgl)
								increment--;
							a[i]=a[i]%10;
							if(a[i]==0)
								increment++;
						}
						else 
							break;
					}
					d[1]=d[0]+increment;
					c[pair] += d[1];
					d[0]=d[1];
				}
			}
		}
		pair++;
	}   
	for(j=0;j<pair;j++)
		cout<<c[j]<<endl;
	system("pause");
	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