前言
题解
测试考场【算法编程赛道】2025第四届大学生算法挑战赛
继续用Deepseek进行求解，还是非常丝滑。
A. 追债之旅
思路: 图论 + bfs题
利用deepseek，直接给出答案
感觉deepseek在输入输出上，显得有些啰嗦。
# coding=utf-8
import heapqdef solve():import sysinput = sys.stdin.readdata = input().split()idx = 0n = int(data[idx])idx += 1m = int(data[idx])idx += 1k = int(data[idx])idx += 1adj = [[] for _ in range(n + 1)]for _ in range(m):u = int(data[idx])idx += 1v = int(data[idx])idx += 1w = int(data[idx])idx += 1adj[u].append((v, w))adj[v].append((u, w))a = list(map(int, data[idx:idx + k]))idx += kINF = float('inf')dp = [[INF] * (n + 1) for _ in range(k + 1)]dp[0][1] = 0heap = []heapq.heappush(heap, (0, 0, 1)) # (total_cost, day, city)found = Falsemin_total = INFwhile heap:total_cost, day, u = heapq.heappop(heap)if u == n:min_total = min(min_total, total_cost)found = Truecontinueif day == k:continueif total_cost > dp[day][u]:continuefor (v, w) in adj[u]:new_day = day + 1if new_day > k:continuenew_total = total_cost + w + a[day]if new_total < dp[new_day][v]:dp[new_day][v] = new_totalheapq.heappush(heap, (new_total, new_day, v))if found:print(min_total)else:print(-1)solve()
B. 单词分类
思路: 对每个单词的字母频率进行统计，构建一个feature key
# coding=utf-8n = int(input())from collections import Counterst = set()
for _ in range(n):s = input()cnt = Counter(s)z = list(cnt.items())z.sort(key=lambda x: (x[0], x[1]))k = ""for (i, j) in z:k += str(i) + ":" + str(j) + ","st.add(k)print (len(st))C. 梯形面积
S = ( u + d ) ∗ h / 2 S = (u + d) * h / 2 S=(u+d)∗h/2
u, d, h = list(map(int, input().split()))print ("%.3f" % ((u + d)/ 2.0 * h))
D. 好串
等价变化：堆栈模拟, a等价push，b等价于pop
保证栈不存在pop空的操作，同时最后栈为空
s = input()def solve(s):r = 0for c in s:if c == 'a': r+=1else:r-=1if r < 0: return Falsereturn r == 0print ("Good" if solve(s) else "Bad")E. 展览
省流题意: 给你一个数组，任意取几个元素，使得其异或值最大
线性基的板子题
想到了线性基，但代码还是借助deepseek来提供。
# coding=utf-8def insert(x, basis):for i in range(63, -1, -1):if (x >> i) & 1:if basis[i] == 0:basis[i] = xbreakx ^= basis[i]return basisn = int(input())
arr = list(map(int, input().split()))
basis = [0] * 64for v in arr:insert(v, basis)def get_max_xor(basis):res = 0for i in range(63, -1, -1):if (res ^ basis[i]) > res:res ^= basis[i]return resprint (get_max_xor(basis))写在最后
