GESP-Python六级 题库
深度优先搜索(DFS,Depth First Search的简写)属于图算法,其过程是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。( )
二叉搜索树可以是空树(没有任何节点)或者单节点树(只有一个节点),或者多节点。如果是多节点,则左节点的值小于父节点的值,右节点的值大于父节点的值,由此推理,右节点树的值都大于根节点的值,左节点树的值都小于根节点的值。( )
完全二叉树
n = int(input()) # l[i]:i的左孩子;r[i]:i的右孩子,0为空 l = [0] * (n + 1) r = [0] * (n + 1) # mn[u]:u子树中,叶子节点的最小深度 mn = [0] * (n + 1) # mx[u]:u子树中,叶子节点的最大深度 mx = [0] * (n + 1) # chk[u]:布尔标记,1代表以u为根的子树是完全二叉树,0不是 chk = [0] * (n + 1) ans = 0 for i in range(1, n + 1): li, ri = map(int, input().split()) l[i] = li r[i] = ri def dfs(u): global ans chk[u] = 1 if u == 0: return # 后序:先递归左右子树 dfs(l[u]) dfs(r[u]) # 条件1:左右子树本身都必须是完全二叉树 chk[u] &= chk[l[u]] & chk[r[u]] # mn[u]:当前子树叶子最小深度 mn[u] = 1 + min(mn[l[u]], mn[r[u]]) # mx[u]:当前子树叶子最大深度 mx[u] = 1 + max(mx[l[u]], mx[r[u]]) # 条件2:左子树叶子最小深度 >= 右子树叶子最大深度 chk[u] &= mn[l[u]] >= mx[r[u]] # 条件3:整棵子树叶子最小深度 >= 最大深度 - 1 chk[u] &= mn[u] >= mx[u] - 1 # 如果u是完全二叉树,答案+1 ans += chk[u] dfs(1) print(ans)
路径覆盖
时间限制:3.0 s
内存限制:512.0 MB
题目描述
给定一棵有 n 个结点的有根树 T ,结点依次以 1 , 2, . , n 编号 ,根结点编号为 1 。方便起见 ,编号为 i 的结点称为结点 i。
初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结
点。将结点 i 染为黑色需要代价 c,你需要在满足以上条件的情况下,最小化染色代价之和。
叶子是指 T 中没有子结点的结点。
输入格式
第一行,一个正整数 n,表示结点数量。

输出格式
一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围

getint = lambda: map(int, input().split()) getints = lambda: list(getint()) # 获取节点数 n = int(input()) # 各个节点的根节点 f = [0, 0] + getints() # 各个节点涂黑的成本 c = [0] + getints() # cnt[i]表示节点i有多少子节点 cnt = [0] * (n + 1) # ans[i]表示以节点i为根节点的子树,需要多少成本才能让所有叶子结点到根节点都有涂黑的节点 ans = [0] * (n + 1) # 统计一个节点有多少子节点 for i in range(2, n + 1): cnt[f[i]] += 1 # 遍历每一个节点,因为一个节点的父节点编号肯定这个节点,所以大编号的一定更深 for i in range(n, 0, -1): # 如果一个节点没有子节点,那么显然ans[i]=c[i]就是把自己涂黑 if cnt[i] == 0: ans[i] = c[i] # 一个节点当前已经找到的答案等于 ans[i] = min(ans[i], c[i]) ans[f[i]] += ans[i] print(ans[1])
树上漫步
题目描述
小 A 有一棵 n个结点的树,这些结点依次以 1,2,...,n标号。
小 A 想在这棵树上漫步。具体来说,小 A 会从树上的某个结点出发,每一步可以移动到与当前结点相邻的结点,并且小 A 只会在偶数步(可以是零步)后结束漫步。
现在小 A 想知道,对于树上的每个结点,从这个结点出发开始漫步,经过偶数步能结束漫步的结点有多少个(可以经过重复的节点)。
输入格式
第一行,一个正整数n 。
接下来n-1 行,每行两个整数ui,vi ,表示树上有一条连接结点ui 和结点vi 的边。
输出格式
一行, n个整数,第 i个整数表示从结点i 出发开始漫步,能结束漫步的结点数量。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围
对于40 % 的测试点,保证1≤n≤103 。
对于所有测试点,保证1≤n≤2*105 。
n = int(input())
to = [[] for i in range(n + 2)]
for i in range(n - 1):
x, y = map(int, input().split())
to[x].append(y)
to[y].append(x)
cnt = [0, 0]
color = [0 for i in range(n + 2)]
def dfs(x, c, f):
color[x] = c
cnt[c] += 1
for y in to[x]:
if y != f:
dfs(y, c ^ 1, x)
dfs(1, 0, 0)
ans = []
for i in range(1, n + 1):
ans.append(str(cnt[color[i]]))
print(' '.join(ans))树上游走
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含无穷节点的二叉树(即每个节点都有左儿子节点和右儿子节点;除根节点外,每个节点都有父节点),其中根节点的编号为 1 ,对于节点 i ,其左儿子的编号为 2×i,右儿子的编号为 2×i+1。
小杨会从节点 s 开始在二叉树上移动,每次移动为以下三种移动方式的任意一种:
第1种移动方式: 如果当前节点存在父亲节点,向上移动到当前节点的父亲节点,否则不移动;
第2种移动方式: 移动到当前节点的左儿子;
第3种移动方式: 移动到当前节点的右儿子。
小杨想知道移动 n 次后自己所处的节点编号。数据保证最后的所处的节点编号不超过1012。
输入格式
第一行包含一个正整数 n,s,代表移动次数和初始节点编号。
第二行包含一个长度为 n 且仅包含大写字母 U,L,R 的字符串,代表每次移动的方式,其中U 代表第1种移动方式,L 代表第2种移动方式,R 代表第3种移动方式。
输出格式
输出一个正整数,代表最后所处的节点编号。
输入样例
输出样例
样例解释
小杨的移动路线为 2-1-3-7。

对于全部数据,保证有1≤n≤106,1≤s≤1012。
INF = 1e12
n, s = map(int, input().split())
c = input()
st = []
for i in range(n):
if c[i] == 'U':
if s == 1:
continue
if st:
st.pop()
continue
s >>= 1
elif c[i] == 'L':
if (s << 1) > INF:
st.append('L')
continue
s = s << 1
else:
if (s << 1 | 1) > INF:
st.append('R')
continue
s = s << 1 | 1
print(int(s))