AcWing 1083. Windy数 python
原题链接
中等
作者:
ppz
,
2021-01-11 15:37:22
,
所有人可见
,
阅读 227
Python代码
N = 11 # 数据范围
f = [[0] * N for _ in range(N)] # 表示i位数,最高位为j的合法的Windy数的个数
# DP预处理推f,包含前导零
def init():
global N
# 枚举一位数,除零外,一位数也是Windy数
for i in range(N):
f[1][i] = 1
# DP递推
for i in range(2, N):
for j in range(10):
for k in range(10):
if abs(j - k) >= 2:
f[i][j] += f[i-1][k]
# DP处理1~N内合法的Windy数的个数
def dp(n):
# 边界判断
if n == 0:
return 0
# 拆分数字每一位,从低位到高位
nums = []
while n:
nums.append(n % 10)
n //= 10
res = 0 # 答案
last = -2 # 首位随便选,要能满足Windy数性质,选择与首位都满足大于等于2的要求,last记录的是上一位,初始选择-2
# 长度为len(nums)时
for i in range(len(nums)-1, -1, -1):
x = nums[i]
for j in range(i==len(nums)-1, x):
if abs(j - last) >= 2:
res += f[i+1][j] # 此时有i+1位
if abs(x - last) < 2: # 不满足性质,则退出
break
last = x
if i == 0: # 如果有幸走到最后,说明右分支也满足Windy性质,加1
res += 1
# 因为包含前导零,而题目中是不考虑前导零的
# 也就是说如013在题目中是不满足Windy数性质的,但013=13,13是Windy数
# 因此,当包含前导零时,需要加上长度小于len(nums)的情况
for i in range(1, len(nums)):
for j in range(1, 10):
res += f[i][j]
return res
init()
# 读入数据
a, b = list(map(int, input().split()))
# 输出结果
print(dp(b) - dp(a-1))