​​点击阅读更多查看文章内容

AcWing 1912. 里程表（逆向思维）

题目链接

约翰的奶牛正在公路上旅行。
他们汽车上的里程表显示的是整数里程值。
旅途开始时里程表显示的里程值为 X，旅途结束时里程表显示的里程值为 Y。
每当里程表显示“有趣的”数字（包括开始和结束时显示的数字）时，奶牛们就会发出愉快的叫声。
如果一个数除去前导零以外的所有数字中，除了一个数字不同以外，其他所有数字都是相同的，那么这个数就是“有趣的”。
例如，33323 和 110 是有趣的，而 9779 和 55555 不是有趣的。
请帮助约翰计算奶牛们在旅途中发出叫声的次数。
输入格式
共一行，包含两个整数 X 和 Y。
输出格式
输出奶牛们在旅途中发出叫声的次数。
数据范围
100≤X≤Y≤10^16^

题目分析

“有趣的数”：除了一个数字不同以外，其他所有数字都是相同的，可以分析出有趣的数中一共只有两个不同的数

观察本题的数据范围为10^16^显然不能通过遍历来实现
我们可以计算一下在10^16^以内的有趣的数的个数约为：17（数字位数，10^16^共有17位）*10（第一个数一共有0~9十种取值）*9（第二个数与第一个数不能相同故有9种取值）*17（第二个数的出现位置）=26010
经过上述计算得出10^16^以内有趣的数共有26010个于是我们可以通过逆向思维枚举这26010个数然后从中找出在X和Y之间的数即可

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
    LL x,y;
    cin >> x >> y;
    int cnt=0;
    for (int i = 3; i <= 17; i ++ )
        for (int j = 0; j < 10; j ++ )
            for (int k = 0; k < 10; k ++ )
                if(j!=k)
                    for (int t = 0; t < i; t ++ )
                    {
                        string s(i,'0'+j);
                        s[t]='0'+k;
                        if(s[0]=='0')
                            continue;
                        LL ans=stoll(s);
                        if(ans>=x&&ans<=y)
                                cnt++;
                    }

    cout << cnt;
    return 0;
}