第一题

第一题代码没存下来，凭感觉打一下。Python处理这样的格式很舒服。读完数据之后直接BFS即可。

import json
from collections import deque

g=json.loads(input())

q=deque([0])
visited=[False]*n
visited[0]=True
while q:
    cnt=q.popleft()
    for nxt in g[cnt]:
        if not visited[nxt]:
            visited[nxt]=True
            q.append(nxt)
print('true' if all(visited) else 'false')

第二题

赛场上有点bug，过了80%。结束之后改了一下，和暴力代码对拍了一下，应该没啥问题。

经典数位DP，主要是考虑2个点，假设数字长度为n：

1. 让你构造一个1~(n-1)长度的数字，你如何构造出包含25的合法情况
2. 根据给定数字遍历前缀，看是否符合要求。

算是裸数位dp，参考题：https://blog.csdn.net/Cassie_zkq/article/details/88577827

from functools import lru_cache


# 前置数为pre的时候，再构造n位数字的合理方案数
# first代表是不是首位，如果是的话无法用0
@lru_cache(None)
def f(n, pre, first=True):
    if n == 0: return 0
    ans = 0

    if pre == 2:
        ans += pow(10, n - 1)

    for i in range(10):
        if first and i == 0: continue
        if pre == 2 and i == 5: continue
        ans += f(n - 1, i, False)

    return ans


def solve():
    s = input()
    n = int(s)
    ms = list(map(int, list(s)))

    l = len(s)

    ans = 0
    for i in range(2, l):
        ans += f(i, -1, True)

    # 遍历到第i位，前置数字为pre的时候的合理方案数
    def g(i, pre):
        if i == l: return 0

        start = 1 if i == 0 else 1

        ans = 0

        # 构造了一个比当前数字小的数字，后面随意选
        for nxt in range(start, ms[i]):
            if pre == 2 and nxt == 5:
                ans += pow(10, l - i - 1)
            else:
                ans += f(l - i - 1, nxt, False)

        if pre == 2 and ms[i] == 5:
            # 如果遇到了25，后面不用遍历了，直接构造就可以
            p = 0
            for j in range(i + 1, l):
                p = p * 10 + ms[j]
            ans += p + 1
        else:
            ans += g(i + 1, ms[i])
        return ans

    ans += g(0, -1)
    return ans

print(solve())

第三题

100%，分治，考虑 和 之间的关系。

首先考虑一个C1，它的构成是：

23
14

然后考虑n2，根据题意，上面2个不动。下面一个逆时针一个顺时针，构成：

23 23
14 14

43 21
12 34

可看出来C2由4个C1组成。以此类推，C3也由4个C2组成。你知道每一块具有的数字数量，按照顺序把该块之前有多少数字加上去即可。

也就是，上面最左下角的块不变，左上角的块每个数字+4，右上角块每个数字+8，右下角每个数字加12。

有了上述推论，你反过来考虑即可。我拥有一个 ，它由4个 块构成。我知道每一块的边上—— ，还有每一块的数字数量 。给定一个x和y，我计算这个(x,y)在哪一块，进行一定的坐标变换，递归处理即可。

class Solution:
    def solution(self, n: int, x1: int, y1: int, x2: int, y2: int) -> int:
        # 得到序号
        def find(n, x, y):
            if n == 1:
                if x == 1 and y == 1: return 1
                if x == 1 and y == 2: return 2
                if x == 2 and y == 2: return 3
                if x == 2 and y == 1: return 4
                raise Exception(n, x, y)
            mid = pow(2, n - 1)
            points = mid * mid
            if x <= mid and y <= mid:
                return find(n - 1, y, x)
            if x <= mid and y > mid:
                y -= mid
                return points + find(n - 1, x, y)
            if x > mid and y > mid:
                x -= mid
                y -= mid
                return 2 * points + find(n - 1, x, y)
            if x > mid and y <= mid:
                x -= mid
                return 3 * points + find(n - 1, mid - y + 1, mid - x + 1)

        return abs(find(n, x1, y1) - find(n, x2, y2))