Day51力扣打卡

打卡记录

Plus and Multiply（模拟）

链接
要满足 $a^x+b\ast y=n$ 的关系，可以枚举满足 $b\ast y=n-a^x$ 的可余条件。

t = int(input())
for _ in range(t):
    n, a, b = map(int, input().split())
    if n == 1 or b == 1 or n % b == 1:
        print('YES')
    elif a == 1:
        if n % b == 1:
            print('YES')
        else:
            print('NO')
    else:
        mul = 1
        while mul <= n:
            if (n - mul) % b == 0:
                print('YES')
                break
            mul *= a
        else:
            print('NO')

到达首都的最少油耗（dfs）

链接
从每条路要被走过的车的次数来进行考虑。

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1
        g = [[] for _ in range(n)]
        g[0] = [-1]
        for x, y in roads:
            g[y].append(x)
            g[x].append(y)
        ans = 0
        def dfs(x, fa):
            res = 0
            for y in g[x]:
                if y == fa:
                    continue
                nonlocal ans
                tmp = dfs(y, x) + 1
                ans += (tmp - 1) // seats + 1
                res += tmp
            return res
        dfs(0, -1)
        return ans