GESP-Python七级 题库
动态规划算法通常有递归实现和递推实现。但由于递归调用在运行时会由于层数过多导致程序崩溃,因此有些动态规划算法只能用递推实现。
按照下面的规则生成一棵二叉树:以一个人为根节点,其父亲为左子节点,母亲为右子节点。对其父亲、母亲分别用同样规则生成左子树和右子树。以此类推,记录30代的直系家谱,则这是一棵满二叉树。
城市规划


# tokens里面缓存了输入 tokens = [] # 这个函数将输入的内容放到tokens里面,随后再读取tokens里的第一条内容作为输入 def get_val(): while not tokens: tokens.extend(input().split()) return int(tokens.pop(0)) # 得到城市和边的数量 n = get_val() m = get_val() # 邻接表,每一个节点后面的列表表示这个节点到列表里面的节点有边 e = [[] for _ in range(n + 1)] for _ in range(m): u = get_val() v = get_val() e[u].append(v) e[v].append(u) # 假设当前在遍历节点i,则d[j]表示节点i目前发现的到j的最短距离。如果这个值为n+1则表明我们还没遍历到j,否则表示我们已经遍历到了j d = [0] * (n + 1) # 这个列表其实是队列,用在以i为中心的广度优先搜索中,记录即将被bfs遍历到的节点 q = [0] * (n + 2) # 这个数组缓存了各个城市的建设成本 mx = [0] * (n + 1) def bfs(u): # 初始化d数组,表明所有节点都还没被遍历到 for i in range(1, n + 1): d[i] = n + 1 # 初始节点已经被遍历到了 d[u] = 0 # 将初始节点入队 q[1] = u # 广度优先的队列左右边界,初始化为1,表明还没开始遍历。这个队列的长度是n+2,而一共只有n个节点,所以这个队列肯定不会被装满,一个节点只会入队不超过1次 ql, qr = 1, 1 # 只要队列还不空就继续遍历 while ql <= qr: # 将队首的元素出栈,将队首元素称为x x = q[ql] ql += 1 # 遍历从x出发能够直接到达的节点 for y in e[x]: # 如果当前找到的最短路径不如从初始节点到x再多走一步,那么就将y节点入队 if d[x] + 1 < d[y]: d[y] = d[x] + 1 # 理论上来讲,使用数组一样的数据结构存储队列元素,这里需要取模。但是这道题里面,每一个节点只会入队一次,所以qr最大就到n+1,因此不需要取模 qr += 1 q[qr] = y # 队列中最后一个弹出的元素一定是最后入队的,这个元素一定离初始节点最远,所以他的距离就是建设难度 mx[u] = d[q[qr]] ans = 1 for i in range(1, n + 1): bfs(i) # 判断当前的建设难度是否小于之前找到的最小的,如果是则更新答案 if mx[i] < mx[ans]: ans = i print(ans)
学习小组

3.2.3 输出格式
输出一行,一个整数,表示所有划分方案中,学习小组综合讨论积极度之和的最大值。
3.2.4.1 输入样例 1
3.2.4.2 输出样例 1
3.2.4.3 输入样例 2
3.2.4.4 输出样例 2

getint = lambda: map(int, input().split()) getints = lambda: list(getint()) # 同学数量 n = int(input()) # 按照讨论积极程度从小到大排序,方便后面计算转移方程 c = sorted(getints()) # 不同分组的基础讨论度 a = [0] + getints() # 用来进行动态规划的数组 # f[j][k]表示在当前已经用掉k个学生,且包含了j个人数不为1的组的情况下的最大积极度 # 我们在这里使用了滚动数组优化,所以没有题解中的i维度 f = [[0] * (n + 1) for _ in range(n + 1)] # 考虑人数最少的组不少于i个人的情况 for i in range(n, 0, -1): # j表示分成了多少个组 # 一共就n个人,所以组的数量绝对不大于n//i+1 for j in range(1, n // i + 1): # 如果最后一个小组刚刚好有i个人,因为之前的组都有至少i个人,所以新加入的组应该选择第j大和第j小的元素作为极大极小值 diff = c[n - j] - c[j - 1] if i > 1 else 0 if diff < 0: break # 假设我们考虑用掉了k个学生,只需要考虑k>=i的情况即可 for k in range(i, n + 1): # 判断最后一个小组如果刚刚好有i个人能否比 f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff) print(max(f[i][n] for i in range(n + 1)))
图上移动
题目描述
小 A 有一张包含n 个结点与 m条边的无向图,结点以1,2,...,n 标号。小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点 i(1≤i≤n ),小 A 想知道从结点i 出发恰好移动1,2,...,k步之后,小 A 可能位于哪些结点。由于满足条件的结点可能有很多,你只需要求出这些结点的数量。
输入格式
第一行,三个正整数 n,m,k,分别表示无向图的结点数与边数,最多移动的步数。
接下来m 行,每行两个正整数 ui,vi,表示图中的一条连接结点 ui与vi 的无向边。
输出格式
共n 行,第 i行(1≤i≤n )包含 k个整数,第j 个整数(1≤j≤k )表示从结点 i出发恰好移动j 步之后可能位于的结点数量。
输入样例
输出样例
数据范围
对于20 % 的测试点,保证k=1 。
对于另外20 % 的测试点,保证 1≤n≤50,1≤m≤50 。
对于所有测试点,保证 1≤n≤500,1≤m≤500 ,1≤k≤20 ,1≤ui,vi≤n。
n, m, k = map(int, input().split())
to = [[] for i in range(n + 2)]
for i in range(m):
x, y = map(int, input().split())
to[x].append(y)
to[y].append(x)
f = [[[False] * (n + 2) for _ in range(n + 2)] for __ in range(k + 2)]
for i in range(1, n + 1):
f[0][i][i] = True
for t in range(1, k + 1):
for x in range(1, n + 1):
for y in range(1, n + 1):
if f[t - 1][x][y]:
for z in to[y]:
f[t][x][z] = True
for i in range(1, n + 1):
Ans = []
for t in range(1, k + 1):
ans = 0
for j in range(1, n + 1):
ans += (f[t][i][j] == True)
Ans.append(str(ans))
print(' '.join(Ans))等价消除
题目描述
小 A 有一个仅包含小写英文字母的字符串 S。
对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字符串是可以被等价消除的。
小 A 想知道 S有多少子串是可以被等价消除的。
一个字符串 S'是S 的子串,当且仅当删去 S的某个可以为空的前缀和某个可以为空的后缀之后,可以得到 S'。
输入格式
第一行,一个正整数|S| ,表示字符串S 的长度。
第二行,一个仅包含小写英文字母的字符串 S。
输出格式
一行,一个整数,表示答案。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围
对于20 % 的测试点,保证S 中仅包含 a 和 b 两种字符。
对于另外20 % 的测试点,保证 1≤|S|≤2000。
对于所有测试点,保证 1≤|S|≤2*105 。
n = int(input())
s = input()
state, cnt, ans = 0, {}, 0
cnt[0] = 1
for i in range(n):
c = ord(s[i]) - ord('a')
state ^= (1 << c)
if state not in cnt:
cnt[state] = 0
ans += cnt[state]
cnt[state] += 1
print(ans)