题目 Codeforces Subsequences
题目链接 :Codeforces Subsequences
题目大意:
每次让l+1
,直到加到r
,问转换中每个位上的数总共变化了几次
思路:构造
如果暴力求l
到r
的话一定会超时,所以有没有什么性质可以挖掘。我们先来看从
1
到x
的变化个位:每次加1就变化一次,所以个位要变化
x
次十位:每次加10就变化一次,所以十位要变化
x / 10
次。其余同理。。
我们用
f(x)
表是从1到x变化的总位数,那么从l
到r
的变化次数就等于f(r)-f(l)
.我做题的时候刚开始没往
f(r)-f(l)
这里想,直接算从l
到r
中每个位都变了几次,发现怎么求都不对,因为不仅要看加了多少次,还要看l
中的每一位和r
中的每一位是啥,非常不好求,然后就想到了分别处理的思想,用总的减去部分的就是剩下的。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get(int r)
{
ll ans = 0;
ll k = 1;
while (r >= k)
{
ans += r / k;
k = k * 10;
}
return ans;
}
void solve()
{
int l, r;
cin >> l >> r;
cout << get(r) - get(l) << endl;
}
signed main()
{
#ifdef Xin
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
中间断了,继续补上