备战2024年蓝桥杯 — 每日一题
Python大学A组
试题一:奶牛选美
试题二:树的重心
试题三:大臣的差旅费
试题四:扫雷
试题一:奶牛选美
【题目描述】
听说最近两斑点的奶牛最受欢迎,约翰立即购进了一批两斑点牛。不幸的是,时尚潮流往往变化很快,当前最受欢迎的牛变成了一斑点牛。约翰希望通过给每头奶牛涂色,使得它们身上的两个斑点能够合为一个斑点,让它们能够更加时尚。牛皮可用一个NM的字符矩阵来表示,如下所示:
................
..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]*(m+5) for _ in range(n+5) ]
t,f = 1,0
for i in range(n):
for j in range(m):
if a[i][j]=='X' and st[i][j]==0:
q=deque()
q.append([i,j])
st[i][j]=t
while q:
tx,ty = q.popleft()
for zx,zy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx,ny = tx+zx,ty+zy
if nx=n or ny=m:continue
if a[nx][ny]=='.' or st[nx][ny]:continue
st[nx][ny]=t
q.append([nx,ny])
t += 1
def bfs(i_,j_):
q = deque()
q.append([i_,j_,0])
vis = [[0]*(m+5) for _ in range(n+5) ]
vis[i_][j_]=1
while q:
tx,ty,z = q.popleft()
if st[tx][ty]==2:
return z
for zx,zy in [(-1,0),(1,0),(0,1),(0,-1)]:
nx,ny = tx+zx,ty+zy
if nx = n or ny = m: continue
if vis[nx][ny]: continue
vis[nx][ny]=1
q.append([nx,ny,z+1])
return 0
res = 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]*(n+5),[0]*(2*n+5),[0]*(2*n+5),0
def add(a,b):
global idx
e[idx]=b; ne[idx]=h[a]; h[a]=idx; idx+=1
for i in range(n-1):
a,b = map(int,input().split())
add(a,b); add(b,a)
ans,st = n,[False]*(n+5)
def dfs(u):
global ans
st[u]=True
res,sumv = 0,1
i = h[u]
while i!=-1:
j = e[i]
if not st[j]:
s = dfs(j)
res = max(res,s)
sumv += s
i = 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 千米的花费为x+10。也就是说,如果一段旅途的总长度为1 千米,则刚好需要花费11,如果一段旅途的总长度为2 千米,则第1千米花费11,第2千米花费12,一共需要花费11+12=23。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(n+1)]
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]*(n+1)
def dfs(st,father,distance):
dist[st] = distance
for b,c in mp[st]:
if b!=father:
dfs(b,st,distance+c)
dfs(1,-1,0)
u = 1
for i in range(1,n+1):
if dist[i]>dist[u]:u=i
dfs(u,-1,0)
for i in range(1,n+1):
if dist[i]>dist[u]:u=i
s = dist[u]
print( s*10 + s*(1+s)//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)] = 0
num[(x, y)] += 1
find[(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)] = 0
f[(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
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
☕️各位观众老爷好,路过点个免费的赞再走呗!❤️❤️(*•ᴗ•*) 前言 随着2024年的到来,人工智能领域正迎来前所未有的变革和发展。随着计算能力的增强、大数据的积累以及机器学习算法的进步, AI的定义和本质 人工智能(Artificial Intellig…