| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
take too much time#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator