摘要
Title: 1912. 里程表
Tag: 二分、枚举
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1912. 里程表

• 题意

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

• 思路

  找出位数在这两个数位数之间得所有满足题目要求的数，直接放进数组中，最后二分查找即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-05-16 09:35:56
  FilePath: \ACM\Acwing\1912.py
  LastEditTime: 2022-05-16 10:06:36
  '''
  from bisect import bisect_left, bisect_right
  
  a, b = map(int, input().split())
  
  al = len(str(a))
  bl = len(str(b))
  
  ans = []
  
  for i in range(al, bl + 1):  # 枚举位数
      for j in range(10):  # 枚举串的模板 如 1111
          s = list(str(j) * i) # 构造出串
          for k in range(i):  # 枚举特殊数的放置地方 如 0
              tmp = s[:]
              for q in range(10):  # 枚举特殊数的数值 如 2
                  if q == j:  # 相等时跳过
                      continue
                  tmp[k] = str(q)  # 临时串
                  res = int("".join(tmp))  # 其中一个结果 即为 2111
                  if len(str(res)) == i:
                      ans.append(res)
                  tmp = s[:]
  
  ans = sorted(list(set(ans)))
  
  print(bisect_right(ans, b) - bisect_left(ans, a))