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

take too much time

Posted by 11115122 at 2017-03-04 15:34:08 on Problem 2282
#include<iostream>
#include<vector>
using namespace std;
int ten[10] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 };
//返回该数的位数
int get(int N)
{
	int i = 0;
	while (N != 0)
	{
		i++;
		N = N / 10;
	}
	return i;

}
//该函数实现计算从 1到 N各个数字出现的次数
void fun(int N,int ans[])
{
	
	{
		//单独获取0出现的次数(特殊处理)
		int temp = N;
		for (int i = 0; i < get(N) - 1; i++)
		{
			ans[0] += ten[i] * (temp / ten[i + 1] - 1);
			if (temp / ten[i] % 10 == 0)
			{
				ans[0]+=  temp%ten[i] + 1;
			}
			if (temp / ten[i] % 10 > 0)
			{
				ans[0] += ten[i];
			}
		}
	
	}
	//获取其它1到9数字出现的次数
	for (int j = 1; j <= 9; j++)
	{
		int temp = N;
		int i;
		for ( i = 0; i < get(N) - 1; i++)
		{
			ans[j] += ten[i] * (temp / ten[i + 1]);
			if (temp/ten[i] % 10 == j)
			{
				ans[j] += temp%ten[i] + 1;
			}
			if (temp / ten[i] % 10 > j)
			{
				ans[j] += ten[i];
			}
		}
		//判断最高位与j数字的大小关系
		if (temp / ten[i] > j)
		{
			ans[j] +=ten[i];
		}
		if (temp / ten[i] == j)
		{
			ans[j] += temp%ten[i]+1;
		}
	}
	



}
//要计算a,b之间的0到9出现次数,只要计算出 1到b  1到a 而后相减即可,但需要加上a中个数字出现的次数(a中出现的数字被减去)

void BETab(int a, int b)
{
	int *theMin = new int[10];
	int *theMax = new int[10];
	for (int i = 0; i < 10; i++)
	{
		theMax[i] = 0;
		theMin[i] = 0;
	}
	
	if (a < b)
	{
		fun(a, theMin);
		fun(b, theMax);
		//注意加回 a中各个数字出现的次数
		while (a != 0)
		{
			theMax[a % 10]++;
			a /= 10;
		}
		
		for (int i = 0; i < 10; i++)
			cout << theMax[i] - theMin[i] << " ";
		cout << endl;
	}
	else
	{
		fun(b, theMin);
		fun(a, theMax);
		while ( b!= 0)
		{
			theMax[b % 10]++;
			b /= 10;
		}
		for (int i = 0; i < 10; i++)
			cout << theMax[i] - theMin[i] << " ";
		cout << endl;

	}
	delete[]theMax;
	delete[]theMin;
}

int main()
{

	vector<int> theA;
	vector<int> theB;
	int a, b;
	while (cin >> a >> b)
	{
		if (a == 0 && b == 0)
			break;
		theA.push_back(a);
		theB.push_back(b);
	}
	for (int i = 0; i < theA.size(); i++)
	{
		BETab(theA[i], theB[i]);
	}
 
	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