~~第一次用python写算法题，感悟到了常数的奥妙。~~

T3

经典动态规划，但是C比D还难是什么逆天，或者用记忆化搜索，大差不差。（哪天一起和数位dp再看看）

def f(x):
    s = str(x)
    # dp[i][k][l]: 
    # i: 第一个非零数字(0-9)
    # k: 是否已确定小于原数x(0/1)
    # l: 是否已出现过非零数字(0/1)
    dp = [[[0]*2 for _ in range(2)] for _ in range(10)]
    
    # 初始状态：只有前导零的情况
    dp[0][1][0] = 1
    
    # 处理第一位数字
    for i in range(1, int(s[0])):
        dp[i][1][1] = 1  # 比首位小的数字都是合法的
    dp[int(s[0])][0][1] = 1  # 等于首位的情况
    
    # 处理后续位数
    for i in range(1, len(s)):
        dpn = [[[0]*2 for _ in range(2)] for _ in range(10)]
        for j in range(10):            # 当前第一个非零数字
            for k in range(2):         # 是否已确定小于原数
                for l in range(2):     # 是否已有非零数字
                    for nx in range(10):  # 当前要填入的数字
                        # 如果已有非零数字，新数字必须小于第一个非零数字
                        if l and j <= nx:
                            continue
                        # 如果还未确定小于原数，新数字不能超过对应位
                        if not k and nx > int(s[i]):
                            continue
                        # 状态转移
                        kn = 1 if (k or nx < int(s[i])) else 0  # 更新是否确定小于原数
                        ln = 1 if (l or nx > 0) else 0          # 更新是否有非零数字
                        jn = nx if (not l and nx != 0) else j   # 更新第一个非零数字
                        dpn[jn][kn][ln] += dp[j][k][l]
        dp = dpn

    # 统计所有合法状态
    ans = 0
    for i in range(10):s
        for j in range(2):
            ans += dp[i][j][1]  # 只统计有非零数字的情况
    return ans

这道题其实也能模拟做。我们计算1~R的蛇数一共三种情况。为了方便我们设位数是n，首数字是t

位数比r小，这就意味着一共有$t^n-1$个，只需枚举t即可
位数和r相同，但是t小于r的首位，这时同上
位数相同，首位相同，我们就暴力dfs枚举（分为同位数数字相同，和不同两种情况）！

def dfs(u: int, top: int, sz: int, s: str) -> int:
    """
    u: 当前处理的位置
    top: 首位数——蛇头
    sz: 数字长度
    s: 数字字符串
    """
    
    #一位数
    if u >= sz:
        return 0
    # 两位数
    if u == sz - 1:
        return min(int(s[u]) + 1, top)
    
    res = 0
    # 相当于solve中的2，3情况
    rbound = min(top - 1, int(s[u]))
    for i in range(rbound + 1):
        if i == int(s[u]):
            res += dfs(u + 1, top, sz, s)
        else:
            res += top ** (sz - u - 1)
    return res

def solve(x: int) -> int:
    if x < 10:
        return 0
    
    t = str(x)
    sz = len(t)
    res = 0
    
    #1 处理长度小于当前数字长度的情况
    for i in range(2, sz):  # 长度
        for j in range(1, 10):  # 第一位数字
            res += j ** (i - 1)
    
    #2 处理长度等于当前数字长度的情况
    for i in range(1, int(t[0])):  # 第一位数字小于当前数字第一位
        res += i ** (sz - 1)
    
    #3 处理剩余情况
    res += dfs(1, int(t[0]), sz, t)
    return res

def main():
    l, r = map(int, input().split())
    print(solve(r) - solve(l - 1))

if __name__ == "__main__":
    main()

T4

简简单单的bfs竟然也会被卡常。看别人代码为什么这么快，竟然用的pypy不讲武德！沟槽的CPython就是这么的慢。还有不要用Queue要用deque

from collections import deque

dx = [0,0,1,-1]  # 右左下上
dy = [1,-1,0,0]

def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    

    sx, sy, gx, gy = -1, -1, -1, -1
    for i in range(h):
        row = s[i]
        for j in range(w):
            if row[j] == 'S':
                sx, sy = i, j
            elif row[j] == 'G':
                gx, gy = i, j
    
    # visited[i][j]: 使用位掩码表示方向，0为水平，1为垂直
    visited = [0] * (h * w)
    
    q = deque()
    # (x, y, steps, last_direction)
    q.append((sx, sy, 0, -1))
    visited[sx * w + sy] |= 0b11  # 标记水平和垂直方向已访问
    
    while q:
        tx, ty, step, last_dir = q.popleft()
        
        if tx == gx and ty == gy:
            print(step)
            return
            
        for i in range(4):
            nx = tx + dx[i]
            ny = ty + dy[i]
            
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != '#':
                curr_dir = 0 if i < 2 else 1
                
                if last_dir == -1 or curr_dir != last_dir:
                    idx = nx * w + ny
                    if not (visited[idx] & (1 << curr_dir)):
                        visited[idx] |= (1 << curr_dir)
                        q.append((nx, ny, step + 1, curr_dir))
    
    print(-1)

if __name__ == "__main__":
    main()