AtCoder Beginner Contest 161

[Wizmann]

Contest Code

D. Lunlun Number

题意

如果一个数的所有相邻位的差的绝对值不大于1，那么称它是一个合法的Lunlun数。

求第k大的lunlun数。

解法

数位DP思想。按位枚举即可。

E. Yutori

题意

一个人要在N天里随意选K天进行工作。现在已知有一些天他不能工作。又已知他在工作一天后，需要休息C天。

问在哪些天，这个人一定在工作。

解法

首先我们进行DP，dp[i]意味着在第i天，这个最多能工作几天。 我们把这个DP正向反向进行两次，获得dp1和dp2。如果dp1[i - 1] + dp2[i + 1] == k - 1，那么意味着在第i天，他一定在工作。否则不能满足工作K天的条件。

F. Division or Subtraction

题意

给你一个数N。让你随意选定一个数K。

然后规定以下操作：

def getlast(N, K):
    while N % K == 0:
        N /= K
    return N % K

问有多少个K可以满足getlast(N, K) == 1

解法

分三种情况讨论：

1. n = k ^ a
2. n = a * k + 1
3. n = t * k and t % k^a == 1

2和3好像重了。。。