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

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

题目链接

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

题目分析

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

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

代码

#include 
#include 
#include 

using namespace std;

typedef long long LL;

int main()
{
    LL x,y;
    cin >> x >> y;
    int cnt=0;
    for (int i = 3; i