每天一道 CodeForces 构造思维题 (day7)

简介: 每天一道 CodeForces 构造思维题 (day7)

题目 Codeforces Subsequences

题目链接 :Codeforces Subsequences

题目大意:

image-20220721222048563

每次让 l+1,直到加到 r,问转换中每个位上的数总共变化了几次

思路:构造

如果暴力求 lr的话一定会超时,所以有没有什么性质可以挖掘。

我们先来看从1x的变化

个位:每次加1就变化一次,所以个位要变化x

十位:每次加10就变化一次,所以十位要变化x / 10 次。

其余同理。。

我们用f(x)表是从1到x变化的总位数,那么从lr的变化次数就等于f(r)-f(l).

我做题的时候刚开始没往f(r)-f(l)这里想,直接算从lr中每个位都变了几次,发现怎么求都不对,因为不仅要看加了多少次,还要看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;
}
中间断了,继续补上
相关文章
|
Java 编译器 C++
c++终极螺旋丸:₍˄·͈༝·͈˄*₎◞ ̑̑“类与对象的结束“是结束也是开始
c++终极螺旋丸:₍˄·͈༝·͈˄*₎◞ ̑̑“类与对象的结束“是结束也是开始
200 0
|
机器学习/深度学习 人工智能 算法
一个10年符号主义学者的深度讨论:如何理性看待ChatGPT?(2)
一个10年符号主义学者的深度讨论:如何理性看待ChatGPT?
|
机器学习/深度学习 人工智能 自然语言处理
一个10年符号主义学者的深度讨论:如何理性看待ChatGPT?(1)
一个10年符号主义学者的深度讨论:如何理性看待ChatGPT?
147 0
|
人工智能
每天两道 CodeForces 构造/思维题 (day5)
每天两道 CodeForces 构造/思维题 (day5)
每天两道 CodeForces 构造/思维题 (day5)
codeforces1013——D. Chemical table(思维+转化+并查集)
codeforces1013——D. Chemical table(思维+转化+并查集)
88 0
|
人工智能 算法
每天一道 CodeForces 构造/思维题 (day1)
每天一道 CodeForces 构造/思维题 (day1)
每天一道 CodeForces 构造/思维题 (day2)
每天一道 CodeForces 构造/思维题 (day2)
|
开发工具
每天一道 CodeForces 构造/思维题 难度1500 (day3)
每天一道 CodeForces 构造/思维题 难度1500 (day3)