讨论/算法和数据结构/酒桌游戏思考/
酒桌游戏思考

我们都玩过酒桌游戏,数7。按顺序报数,从1开始,遇到包含7或是7的倍数的数字需要跳过,说错了罚酒。
如果我们定义不包含7且不是7的倍数的数是好数,例如:1,2,3,4,5,6,8,9,10,11,12,13,15,16,18 ...,
那第n个好数是多少呢,有没有快速求解的算法呢?

展开讨论

这题是数位dp的题

需要解决如下几个子问题

  1. 第n个好数是多少呢?

只要解决了1号子问题,加上二分法,就可以得到第n个好数的值

  1. 区间[1,x],有多少个好数?

将x分解成10进制 x=a1a2a3...x=a_{1}a_{2}a_{3}...

我们需要按数位进行统计

举个例子:

区间[1,1234567]的好数有多少个?

我们需要统计下面这几种情况的好数的个数

  • 0xxxxxxx
  • 10xxxxxx
  • 11xxxxxx
  • 120xxxxx
  • 121xxxxx
  • 122xxxxx
  • 1230xxxx
  • 1231xxxx
  • 1232xxxx
  • 1233xxxx
  • 12340xxx
  • 12341xxx
  • 12342xxx
  • 12343xxx
  • 12344xxx
  • 123450xx
    ...
  1. n位数(包括前导0)的好数有多少个?

令dp[i][j]表示i位数除以7的余数为j的个数,则有转移方程

dp[i][j]=k=09dp[i1][(j10+k)%7],k7dp[i][j]=\sum_{k=0}^{9} dp[i-1][(j*10+k)\%7] , k \neq 7

k=06dp[n][k]\sum_{k=0}^{6}dp[n][k]就是结果

3
展开全部 4 讨论