cms开源建站系统,国外网站设计模板,灵山县建设局网站,宁波seo怎么推广备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一#xff1a;奶牛选美 试题二#xff1a;树的重心 试题三#xff1a;大臣的差旅费 试题四#xff1a;扫雷 试题一#xff1a;奶牛选美
【题目描述】 听说最近两斑点的奶牛最受欢迎#xff0c;…备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一奶牛选美 试题二树的重心 试题三大臣的差旅费 试题四扫雷 试题一奶牛选美
【题目描述】 听说最近两斑点的奶牛最受欢迎约翰立即购进了一批两斑点牛。不幸的是时尚潮流往往变化很快当前最受欢迎的牛变成了一斑点牛。约翰希望通过给每头奶牛涂色使得它们身上的两个斑点能够合为一个斑点让它们能够更加时尚。牛皮可用一个 N×M的字符矩阵来表示如下所示
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX.... 其中X表示斑点部分。如果两个 X在垂直或水平方向上相邻对角相邻不算在内则它们属于同一个斑点由此看出上图中恰好有两个斑点。约翰牛群里所有的牛都有两个斑点。约翰希望通过使用油漆给奶牛尽可能少的区域内涂色将两个斑点合为一个。在上面的例子中他只需要给三个 .. 区域内涂色即可新涂色区域用 ∗ 表示
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX.... 请帮助约翰确定为了使两个斑点合为一个他需要涂色区域的最少数量。
【输入格式】 第一行包含两个整数 N和 M。 接下来 N 行每行包含一个长度为 M 的由 X 和 .. 构成的字符串用来表示描述牛皮图案的字符矩阵。
【输出格式】 输出需要涂色区域的最少数量。
【数据范围】 1≤N,M≤50
【输入样例】
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
【输出样例】
3
【解题思路】 用2次BFS第一次用来找出两个斑点第二次用来找最短的连接线。
【Python程序代码】
from collections import *
n,m map(int,input().split())
a []
for i in range(n):a.append(list(input()))
st [[0]*(m5) for _ in range(n5) ]
t,f 1,0
for i in range(n):for j in range(m):if a[i][j]X and st[i][j]0:qdeque()q.append([i,j])st[i][j]twhile q:tx,ty q.popleft()for zx,zy in [(-1,0),(1,0),(0,-1),(0,1)]:nx,ny txzx,tyzyif nx0 or nxn or ny0 or nym:continueif a[nx][ny]. or st[nx][ny]:continuest[nx][ny]tq.append([nx,ny])t 1def bfs(i_,j_):q deque()q.append([i_,j_,0])vis [[0]*(m5) for _ in range(n5) ]vis[i_][j_]1while q:tx,ty,z q.popleft()if st[tx][ty]2:return zfor zx,zy in [(-1,0),(1,0),(0,1),(0,-1)]:nx,ny txzx,tyzyif nx 0 or nx n or ny 0 or ny m: continueif vis[nx][ny]: continuevis[nx][ny]1q.append([nx,ny,z1])return 0res n*m
for i in range(n):for j in range(m):if st[i][j]1:tep bfs(i,j)res min(res,tep)
print(res-1) 试题二树的重心
【题目描述】 给定一颗树树中包含 n个结点编号 1∼n和 n−1 条无向边。请你找到树的重心并输出将重心删除后剩余各个连通块中点数的最大值。重心定义重心是指树中的一个结点如果将这个点删除后剩余各个连通块中点数的最大值最小那么这个节点被称为树的重心。
【输入格式】 第一行包含整数 n表示树的结点数。 接下来 n−1行每行包含两个整数 a 和 b表示点 a 和点 b 之间存在一条边。
【输出格式】 输出一个整数 m表示将重心删除后剩余各个连通块中点数的最大值。
【数据范围】 1≤n≤100000
【输入样例】
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6 【输出样例】
4
【解题思路】 本体上就是一个树的遍历问题遍历去掉每一个点找出答案。
【Python程序代码】
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
for i in range(n-1):a,b map(int,input().split())add(a,b); add(b,a)
ans,st n,[False]*(n5)
def dfs(u):global ansst[u]Trueres,sumv 0,1i h[u]while i!-1:j e[i]if not st[j]:s dfs(j)res max(res,s)sumv si ne[i]res max(res,n-sumv)ans min(ans,res)return sumv
dfs(1)
print(ans)试题三 大臣的旅费
【题目描述】 很久以前T王国空前繁荣。为了更好地管理国家王国修建了大量的快速路用于连接首都和王国内的各大城市。为节省经费T 国的大臣们经过思考制定了一套优秀的修建方案使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时如果不重复经过大城市从首都到达每个大城市的方案都是唯一的。J 是 T 国重要大臣他巡查于各大城市之间体察民情。所以从一个城市马不停蹄地到另一个城市成了 J最常做的事情。他有一个钱袋用于存放往来城市间的路费。聪明的 J发现如果不在某个城市停下来修整在连续行进过程中他所花的路费与他已走过的距离有关。具体来说一段连续的旅途里第 1千米的花费为 11第 2 千米的花费为 12第 3 千米的花费为 13…第 x 千米的花费为 x10。也就是说如果一段旅途的总长度为 1 千米则刚好需要花费 11如果一段旅途的总长度为 2 千米则第 1千米花费 11第 2 千米花费 12一共需要花费 111223。J 大臣想知道他从某一个城市出发中间不休息到达另一个城市所有可能花费的路费中最多是多少呢
【输入样例】 【输出格式】 输出一个整数表示大臣 J 最多花费的路费是多少。
【数据范围】 【输入样例】
5
1 2 2
1 3 1
2 4 5
2 5 4
【输出样例】
135
【解题思路】 可以发现本题就是求树的直径的问题经典做法就是先遍历找出距离点d最远的点x然后找到距离x点最优的y点其中x到y的距离就是树的直径。
【Python程序代码】
n int(input())
mp [[]for i in range(n1)]
for i in range(n-1):a,b,c map(int,input().split())mp[a].append([b,c])mp[b].append([a,c])
dist [0]*(n1)
def dfs(st,father,distance):dist[st] distancefor b,c in mp[st]:if b!father:dfs(b,st,distancec)
dfs(1,-1,0)
u 1
for i in range(1,n1):if dist[i]dist[u]:ui
dfs(u,-1,0)
for i in range(1,n1):if dist[i]dist[u]:ui
s dist[u]
print( s*10 s*(1s)//2 ) 试题四扫雷
【题目描述】 小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下在一个二维平面上放置着 n 个炸雷第 i个炸雷 (xi,yi,ri)表示在坐标 (xi,yi)(处存在一个炸雷它的爆炸范围是以半径为 ri 的一个圆。为了顺利通过这片土地需要玩家进行排雷。玩家可以发射 m 个排雷火箭小明已经规划好了每个排雷火箭的发射方向第 j 个排雷火箭 (xj,yj,rj)表示这个排雷火箭将会在 (xj,yj)处爆炸它的爆炸范围是以半径为 rj 的一个圆在其爆炸范围内的炸雷会被引爆。同时当炸雷被引爆时在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
【输入格式】 输入的第一行包含两个整数 n、m。 接下来的 n 行每行三个整数 xi,yi,ri表示一个炸雷的信息。 再接下来的 m 行每行三个整数 xj,yj,rj表示一个排雷火箭的信息。
【输出格式】 输出一个整数表示答案。
【数据范围】
【输入样例】
2 1
2 2 4
4 4 2
0 0 5
【输出样例】
2 【解题思路】 首先对在同一点的炸雷和排雷火箭进行去重处理然后枚举每一个排雷火箭遍历排雷范围如果能扫到雷则该炸雷也存放到排雷火箭队列。最后用排雷火箭队列模拟排雷。
【Python程序代码】
import sys
from collections import *
input sys.stdin.readline
n, m map(int, input().split())
num Counter()
find dict()
for _ in range(n):x, y, r map(int, input().split())if (x, y) not in find:find[(x, y)] 0num[(x, y)] 1find[(x, y)] max(find[(x, y)], r)
pq deque()
f dict()
for _ in range(m):x, y, r map(int, input().split())if (x, y) not in f:f[(x, y)] 0f[(x, y)] max(f[(x, y)], r)
for (x, y), r in f.items():for i in range(x - r, x r 1):for j in range(y - r, y r 1):if (i - x) ** 2 (j - y) ** 2 r ** 2:if (i, j) in find:pq.append((i, j, find[(i, j)]))del find[(i, j)]
res 0
while pq:x, y, r pq.popleft()res num[(x, y)]for i in range(x - r, x r 1, 1):for j in range(y - r, y r 1, 1):if (i - x) ** 2 (j - y) ** 2 r ** 2:if (i, j) in find:pq.append((i, j, find[(i, j)]))del find[(i, j)]
print(res)
