计算机网络网站建设的实训总结,wordpress pin,桂林象鼻山公园,wordpress 网络电台备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一#xff1a;病毒溯源 试题二#xff1a;没有上司的舞会 试题三#xff1a;生命之树 试题一#xff1a;病毒溯源
【题目描述】 病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株#xff0c;而…备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一病毒溯源 试题二没有上司的舞会 试题三生命之树 试题一病毒溯源
【题目描述】 病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株而这些变异的病毒又可能被诱发突变产生第二代变异如此继续不断变化。现给定一些病毒之间的变异关系要求你找出其中最长的一条变异链。在此假设给出的变异都是由突变引起的不考虑复杂的基因重组变异问题 —— 即每一种病毒都是由唯一的一种病毒突变而来并且不存在循环变异的情况。
【输入格式】 输入在第一行中给出一个正整数 N即病毒种类的总数。于是我们将所有病毒从 0 到 N−1 进行编号。 随后 N 行每行按以下格式描述一种病毒的变异情况 k 变异株1 …… 变异株k 其中 k 是该病毒产生的变异毒株的种类数后面跟着每种变异株的编号。第 i 行对应编号为 i 的病毒0≤iN。题目保证病毒源头有且仅有一个。
【输出格式】 首先输出从源头开始最长变异链的长度。 在第二行中输出从源头开始最长的一条变异链编号间以 11 个空格分隔行首尾不得有多余空格。如果最长链不唯一则输出最小序列。 注我们称序列 {a1,…,an} 比序列 {b1,…,bn} “小”如果存在 1≤k≤n 满足 aibi 对所有 ik 成立且 akbk。
【数据范围】 1≤N≤104
【输入样例】
10
3 6 4 8
0
0
0
2 5 9
0
1 7
1 2
0
2 3 1
【输出样例】
4
0 4 9 1
【解题思路】 题意就是输出根节点到叶子节点的最大长度的那条路径如果有多条路径选择字典序最小的那一条。首先找到根节点从根节点搜索最长路径采用DFS.
【Python程序代码】
# import sys
# sys.setrecursionlimit(10000)
n int(input())
h,e,ne,idx [-1]*(n5),[0]*(2*n5),[0]*(2*n5),0
st,mp [0]*(n5),[0]*(n5)
def add(a,b):global idxe[idx] b; ne[idx]h[a]; h[a]idx; idx1
def dfs(u):res 0mp[u]-1i h[u]while i!-1:j e[i]d dfs(j)if resd:res d; mp[u]jelif resd:mp[u] min(mp[u],j)i ne[i]return res1
for i in range(n):s list(map(int,input().split()))if s[0]0:continuefor j in range(1,len(s)):add(i,s[j])st[s[j]]1root 0
while st[root]:root1
print(dfs(root))
print(root,end )
while mp[root]!-1:root mp[root]print(root,end )试题二没有上司的舞会
【题目描述】 Ural 大学有 N 名职员编号为 1∼N。他们的关系就像一棵以校长为根的树父节点就是子节点的直接上司。每个职员有一个快乐指数用整数 Hi 给出其中 1≤i≤N。现在要召开一场周年庆宴会不过没有职员愿意和直接上司一起参会。在满足这个条件的前提下主办方希望邀请一部分职员参会使得所有参会职员的快乐指数总和最大求这个最大值。
【输入格式】 第一行一个整数 N。 接下来 N行第 i行表示 i号职员的快乐指数 Hi。 接下来 N−1 行每行输入一对整数 L,K表示 K 是 L的直接上司。注意一下后一个数是前一个数的父节点不要搞反。
【输出格式】 输出最大的快乐指数。
【数据范围】 1≤N≤6000, −128≤Hi≤127
【输入样例】
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
【输出样例】
5
【解题思路】 令f[u][0]表示不取节点的最大快乐指数、f[u][1]表示取节点u的最大快乐指数。所以f[u][0] max(f[j][0]f[j][1])其中j为u的子节点。f[u][1] f[j][0]。答案为max(f[root])。
【Python程序代码】
n int(input())
h,e,ne,idx [-1]*(n5),[0]*(2*n5),[0]*(2*n5),0
f [[0]*(3) for i in range(n5)]
def add(a,b):global idxe[idx]b; ne[idx]h[a]; h[a]idx; idx1
def dfs(u):f[u][1] w[u]i h[u]while i!-1:j e[i]dfs(j)f[u][0] max(f[j][1],f[j][0])f[u][1] f[j][0]i ne[i]
st,w [0]*(n5), [0]*(n5)
for i in range(1,n1):w[i] int(input())
for i in range(n-1):a,b map(int,input().split())add(b,a)st[a]1
root 1
while st[root]:root1
dfs(root)
print(max(f[root])) 试题三生命之树
【题目描述】 在X森林里上帝创建了生命之树。他给每棵树的每个节点叶子也称为一个节点上都标了一个整数代表这个点的和谐值。上帝要在这棵树内选出一个非空节点集 S使得对于 S 中的任意两个点 a,b都存在一个点列 {a,v1,v2,…,vk,b}使得这个点列中的每个点都是 S 里面的元素且序列中相邻两个点间有一条边相连。在这个前提下上帝要使得 S 中的点所对应的整数的和尽量大。这个最大的和就是上帝给生命之树的评分。经过 atm 的努力他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。
【输入格式】 第一行一个整数 n 表示这棵树有 n 个节点。 第二行 n 个整数依次表示每个节点的评分。 接下来 n−1行每行 2 个整数 u,v表示存在一条 u 到 v 的边。 由于这是一棵树所以是不存在环的。 树的节点编号从 1 到 n。
【输出格式】 输出一行一个数表示上帝给这棵树的分数。
【数据范围】 1≤n≤105, 每个节点的评分的绝对值均不超过 106。
【输入数据】
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
【输出数据】
8
【解题思路】 看起来像求根的直径但是边是带权值的。实际上就是找到一个无向图中的连通块使得它的节点权值的总和最大。同样由于是无向图为了减少搜索次数dfs的时候可以记录一下父节点。
【Python程序代码】
import sys
sys.setrecursionlimit(int(1e9))
n int(input())
h,e,ne,idx [-1]*(n5),[0]*(2*n5),[0]*(2*n5),0
def add(a,b):global idxe[idx]b; ne[idx]h[a]; h[a]idx; idx1
w [0] list(map(int,input().split()))
for i in range(n-1):a,b map(int,input().split())add(a,b); add(b,a)
f [0]*(n5)
def dfs(u,fa):f[u] w[u]i h[u]while i!-1:j e[i]if j!fa:dfs(j,u)f[u] max(0,f[j])i ne[i]
dfs(1,0)
print(max(f[1:n1]))
