前言

这是第四届大学生算法挑战赛的练习赛系列 1，这个比赛是国家一级协会的。

这章是进阶训练1的F-J题，感觉还是蛮基础的。

---

题解

第四届大学生算法挑战赛的练习赛系列 1
尝试用Deepseek写了下，感觉人类在AI面前真的很渺小。

---

F. A*B problem

题目：A * B

考点: 高精度

a = int(input())
b = int(input())

print (a * b)

突然想起了一句话: “甚至没让python大人出点汗”

---

G. 字符串正反连接

题意: 所给字符串正序和反序连接，形成新串并输出。

s = input()
print (s + s[::-1])

---

H. 造一造

思路: 数学题

和卡特兰数有关

$$front=C(2m-k-1,m-k)-C(2m-k-1,m-k-1)$$

$$back=C(2(n-m)+k,n-m)-C(2(n-m)+k,n-m-1)$$

$$结果为front\ast back$$

import sys
MOD = 10**9 + 7

def solve():
    n, m, k = map(int, sys.stdin.readline().split())
    
    if k > m or k < 0:
        print(0)
        return
    
    max_n = 2 * n + k  # 最大可能用到的阶乘
    
    # 预计算阶乘、逆阶乘和逆元数组
    fact = [1] * (max_n + 1)
    inv_fact = [1] * (max_n + 1)
    
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
    
    inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD)
    for i in range(max_n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    
    def comb(a, b):
        if a < 0 or b < 0 or a < b:
            return 0
        return fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD
    
    # 前m-1个操作的合法序列数
    a = 2 * (m - 1) - (k - 1)
    b = (m - 1) - (k - 1)
    front = (comb(a, b) - comb(a, b - 1)) % MOD
    
    # 后n - m个操作的合法序列数
    c = 2 * (n - m) + k
    d = n - m
    back = (comb(c, d) - comb(c, d - 1)) % MOD
    
    total = front * back % MOD
    print(total)


t = int(input())
for _ in range(t):
    solve()

这是deepseek给出的解，说实在，完败

---

I. 村村通

思路: 求连通分量数

这个思路蛮多的， bfs, dfs, 并查集都可以

import sys
from sys import stdin

def main():
    sys.setrecursionlimit(1 << 25)
    while True:
        line = stdin.readline()
        if not line or line == "0":
            break
        n, m = map(int, line.strip().split())
        
        parent = [i for i in range(n + 1)]
        
        def find(u):
            while parent[u] != u:
                parent[u] = parent[parent[u]]
                u = parent[u]
            return u
        
        def union(u, v):
            u_root = find(u)
            v_root = find(v)
            if u_root != v_root:
                parent[v_root] = u_root
        
        for _ in range(m):
            u, v = map(int, stdin.readline().strip().split())
            union(u, v)
        
        roots = set()
        for i in range(1, n + 1):
            roots.add(find(i))
        
        print(len(roots) - 1)

if __name__ == "__main__":
    main()

J. maze

思路: 迷宫寻路题

Dijkstra板子题，但是赛氪出题非常的不严谨

上面输出说是YES/NO, 样例输出确实最短路/无解(-1)

import sys
import heapq

def main():
    n, m, q = list(map(int, input().split()))

    maze = []
    S = None
    T = None
    for i in range(n):
        row = input()
        maze.append(row)
        if 'S' in row:
            S = (i, row.index('S'))
        if 'T' in row:
            T = (i, row.index('T'))

    teleports = {}
    for _ in range(q):
        x1, y1, x2, y2 = list(map(int, input().split()))
        if maze[x1][y1] != '#' and maze[x2][y2] != '#':
            if (x1, y1) not in teleports:
                teleports[(x1, y1)] = []
            teleports[(x1, y1)].append((x2, y2))

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    heap = []
    heapq.heappush(heap, (0, S[0], S[1]))
    visited = {}
    visited[(S[0], S[1])] = 0

    found = False
    while heap:
        time, x, y = heapq.heappop(heap)
        if (x, y) == T:
            found = True
            print(time)
            break
        if time > visited.get((x, y), float('inf')):
            continue

        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != '#':
                new_time = time + 1
                if (nx, ny) not in visited or new_time < visited[(nx, ny)]:
                    visited[(nx, ny)] = new_time
                    heapq.heappush(heap, (new_time, nx, ny))

        if (x, y) in teleports:
            for (tx, ty) in teleports[(x, y)]:
                if maze[tx][ty] != '#':
                    new_time = time + 3
                    if (tx, ty) not in visited or new_time < visited[(tx, ty)]:
                        visited[(tx, ty)] = new_time
                        heapq.heappush(heap, (new_time, tx, ty))

    if not found:
        print("-1")

if __name__ == "__main__":
    main()

---

写在最后