每天一道 CodeForces 构造思维题 （day7）

题目 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;
}

中间断了，继续补上