CF1538F Interesting Function

题目传送门

题意

给定两个正整数 \(l, r\)（\(l < r\)），将 \(l\) 不断加 \(1\) 直到 \(l = r\)，求出这一过程中 \(l\) 发生变化的位数总数。

位数变化指：

\(l=909\)，将 \(l+1\) 后有 \(2\) 位数字发生变化。
\(l=9\)，将 \(l+1\) 后也有 \(2\) 位数字发生变化。
\(l=489999\)，将 \(l+1\) 后有 \(5\) 位数字发生变化。

而总数指：

\(l=10\)，\(r=20\)，个位变化了 \(10\) 次，十位变化了 \(1\) 次，所以总数为 \(11\)。

思路

很明显，当在十位进位时，会比个位多变化一个数位，百位则比十位多变化一个，依此类推。

所以最后我们只需要求出来这个数在相加的过程中每一个数位分别做了多少次仅为操作就行

如果有一个数\(k\)，从\(1\)开始进行题目所述操作，那么他在位权是\(10^i\)时（即第\(i-1\)位），就会有\(\frac{k}{10^i}\)

可以用这个方法求出\(l\)和\(r\)，再作差即可

最后，将他们进位总数相加即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[15],l,r,ans;
int p(int x)
{
    int re=1;
    while(x) x--,re*=10;
    return re;
}
void run()
{
    cin>>l>>r;ans=0;
    memset(f,0,sizeof(f));
    for(int i=0;i<=9;i++) f[i]=r/p(i);
    for(int i=0;i<=9;i++) f[i]-=l/p(i);
    for(int i=0;i<=9;i++) ans+=f[i];
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) run();
    system("echo. & pause");
    return 0;
}