AcWing 338. 计数问题
原题链接
中等
作者:
我要出去乱说
,
2021-01-29 19:56:37
,
所有人可见
,
阅读 244
#include <iostream>
#include <algorithm>
using namespace std;
int get(vector<int> num, int l, int r)
{
int res = 0;
for (int i = l; i >= r; i -- )
res = res * 10 + num[i];
return res;
}
int power10(int x)
{
int res = 1;
while (x -- ) res *= 10;
return res;
}
int count(int n, int x) //数字1~n中出现了多少次x
{
if (!n) return 0;
vector<int> num;
while (n) //把n拆散,从最小位放入vector
{
num.push_back(n % 10);
n /= 10;
}
n = num.size(); //n等于n的长度
int res = 0;
for (int i = n - 1 - !x; i >= 0; i -- ) //当x == 0时从n-2开始循环
{
if (i != n - 1) //当i不是最高位时,第一种情况
{
res += get(num, n - 1, i + 1) * power10(i);
if (!x) res -= power10(i); //当x == 0 是,去除abc中000这个前缀
}
//情况2.1为0,不需要列出
if (num[i] == x) res += get(num, i - 1, 0) + 1; //情况2.2 : efg从000到efg共efg + 1次
else if (num[i] > x) res += power10(i); //情况2.3 : efg从000到999共一千次
}
return res;
}
int main()
{
int a, b;
while (cin >> a >> b, a || b) //判断两个值都为0是停止输入
{
if (a > b) swap(a, b); //小数在前大数在后
for (int i = 0; i < 10; i ++ ) //i表示出现的数字
cout << count(b, i) - count(a - 1, i) << ' '; //前缀和算法,b中出现i的次数减去a-1中出现i的次数
cout << endl;
}
return 0;
}