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