腾讯8月22日笔试 个人题解与Python代码
1. 开锁
题目描述
有 n 把钥匙，m 个锁，每把锁只能由一把特定的钥匙打开，其他钥匙都无法打开。一把钥匙可能可以打开多把锁，钥匙也可以重复使用。
对于任意一把锁来说，打开它的钥匙是哪一把是等概率的。但你无法事先知道是哪一把钥匙，只能进行尝试。
已知每次尝试用第i把钥匙打开第j把锁会消耗的时间aij 秒。
问最优策略下打开所有锁的总期望时间是多少秒。
输入描述
第一行两个以空格分隔的正整数n,m。
接下来m行每行m个空格分隔的正整数aij。
1<=n,m,aij <=500
输出描述
输出一个小数代表答案，你的答案会被认为是正确的当且仅当你的答案与正确答案的绝对误差或相对误差不超过10-6。
个人题解
from itertools import * n, m = map(int, input().split()) a = [] for i in range(n): a.append(list(map(int, input().split()))) print(sum(sum(accumulate(sorted(a[i][j] / n for i in range(n)))) for j in range(m)))
2. 勇闯币圈
题目描述
最近以比特币为代表的数字货币市场非常动荡，聪明的小明打算用马尔科夫链来建模股市。如图所示，该模型有三种状态：“行情稳定”，“行情大跌”以及“行情大涨”。每一个状态都以一定的概率转化到下一个状态。比如，“行情稳定”以0.4的概率转化到“行情大跌”的状态。
不妨设“行情稳定”，“行情大跌”以及“行情大涨”分别为状态0，状态1和状态2。我们可以定义概率转移矩阵P，其中P(i,j)的数值表示的是状态j转移到状态i的概率。如图所示的概率转移矩阵为：
有了概率转移矩阵P，我们只要知道一个初始状态 
可以通过该模型，计算出第t步的“行情大涨”的概率吗？如果这个概率大于0.5那么输出1，否则输出0。
输入描述
第1行输入为测试数据组数T(1<=T<1000)，接下来T组每5行的数据格式为
T组第1行是步长1<=t<=10。
T组第2行是一个3维的初始状态
T组第3行到第5行是3*3的概率转移矩阵P，每行有三个浮点数
输出描述
个人题解
def matmul(a, b): assert len(a[0]) == len(b) row, col = len(a), len(b[0]) mid = len(a[0]) res = [[0] * col for _ in range(row)] for i in range(row): for j in range(col): for k in range(mid): res[i][j] += a[i][k] * b[k][j] return res def qpow(mat, n): res = [[1,0,0],[0,1,0],[0,0,1]] while n: if n & 1: res = matmul(res, mat) mat = matmul(mat, mat) n >>= 1 return res T = int(input()) for _ in range(T): t = int(input()) init = list(map(float, input().split())) p = [] for _ in range(3): p.append(list(map(float, input().split()))) res = qpow(p, t) ans = 0 for i in range(3): ans += init[i] * res[2][i] print(1 if ans > 0.5 else 0)
3. 迎宾车队
题目描述
今天正在进行赛车车队选拔，每一辆赛车都有一个不可以改变的速度。现在需要选取速度差距在10以内的车队（车队中速度的最大值减去最小值不大于10），用于迎宾。车队的选拔按照的是人越多越好的原则，给出n辆车的速度，你能选出满足条件的最多车辆的车队吗。
输入描述
第一行一个数字n(1<=n<=100000)。
接下来一行n个整数，speed[i] 表示第i辆车的速度为speedi。
输出描述
个人题解
n = int(input()) s = sorted(map(int, input().split())) l = 0 ans = 1 for r in range(n): if s[r] - s[l] <= 10: ans = max(ans, r - l + 1) else: while s[r] - s[l] > 10: l += 1 print(ans)
4. 水站的水流量
题目描述
有一个水站网络共有n层，第i层有i个水站节点，如图所示连接，水流单向流动。
每个水站在达到MAX个水流量时，称该水站满负荷工作，后续流进该水站的水流量，将会分为两等份流向它后面所连接的两个水站。若每秒都有流入第一个水站MAX个水流量，请问第T秒有多少个水站是满负荷工作的？
输入描述
一行两个正整数，n和t。
输出描述
个人题解
from bisect import * n, t = map(int, input().split()) hub = [[0] * i for i in range(1, n + 1)] full = set() def fill(x, y, w): if x == n&nbs***bsp;w == 0: return hub[x][y] += w if hub[x][y] >= 1: fill(x + 1, y, (hub[x][y] - 1) / 2) fill(x + 1, y + 1, (hub[x][y] - 1) / 2) hub[x][y] = 1 full.add((x, y)) for _ in range(t): fill(0, 0, 1) print(len(full)) # full_time = [1, 3, 3, 5, 7, 7, 9, 9, 11, 14, 14, 15, 15, 16, 16, 19, 22, 22, 22, 22, 24, 24, 28, 31, 31, 31, 31, 32, 32, 34, 34, 37, 37, 41, 41, 46, 46, 63, 63, 63, 63, 69, 69, 105, 105, 127, 127, 182, 182, 255, 255, 511, 511] # i = bisect_right(full_time, t) # print(min(i, n * (1 + n) // 2))
5. 定点轰炸
题目描述
牛牛是军团的指挥官，这一天，高层来到团中检查，牛牛为了演示军团的实战能力，决定表演定点轰炸。
在事先既定的 n*n大小的矩形中，随机勾勒上几笔，轰炸位置即为被这几笔所包围的区域。
你作为自动化定点轰炸的创始人，需要为此书写一个程序，来完成这个任务。首先，你将整个 n*n的矩形看成一个全 0矩形，勾勒的笔画所经过的位置用 1表示，现在，你需要将被轰炸区域改成数字 2，用于标记，指引轰炸方位。
一个被 1包围的区域定义为：区域内部的点不能通过上下左右的移动，在不经过 1的前提下到达区域外的 0点或者矩形外部。
输入描述
第一行输入一个正整数n(1<=n<1000) ，代表矩形边长。
接下去 n 行，每行 n个整数，整数仅有可能为 0或 1，含义如题所述。
输出描述
输出一个 n*n的矩形，一共 n行，每行 n 个整数，该矩形代表标记完轰炸区域后的结果呈现。
个人题解
from collections import deque
n = int(input())
m = [['2'] * (n + 2) for _ in range(n + 2)]
for i in range(n):
ls = input().split()
for j in range(n):
if ls[j] == '1':
m[i + 1][j + 1] = ls[j]
q = deque([(0, 0)])
m[0][0] = '0'
while q:
x, y = q.popleft()
for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nx, ny = x + dx, y + dy
if 0 <= nx < n + 2 and 0 <= ny < n + 2 and m[nx][ny] == '2':
q.append((nx, ny))
m[nx][ny] = '0'
for i in range(n):
print(' '.join(m[i + 1][1: -1])) 
查看18道真题和解析
投递上海莱迪思半导体等公司10个岗位 >
