首页 > 腾讯8月22日笔试 个人题解与Python代码
头像
牛客699525022号
发布于 2021-08-23 20:54
+ 关注

腾讯8月22日笔试 个人题解与Python代码

1. 开锁

题目描述

有 n 把钥匙,m 个锁,每把锁只能由一把特定的钥匙打开,其他钥匙都无法打开。一把钥匙可能可以打开多把锁,钥匙也可以重复使用。
对于任意一把锁来说,打开它的钥匙是哪一把是等概率的。但你无法事先知道是哪一把钥匙,只能进行尝试。
已知每次尝试用第i把钥匙打开第j把锁会消耗的时间aij 秒。
问最优策略下打开所有锁的总期望时间是多少秒。

输入描述

第一行两个以空格分隔的正整数n,m。
接下来m行每行m个空格分隔的正整数aij
1<=n,m,aij <=500

输出描述

输出一个小数代表答案,你的答案会被认为是正确的当且仅当你的答案与正确答案的绝对误差或相对误差不超过10-6。

个人题解

排序 + 前缀和
假设一把锁对应解锁时间从小到大排序后为 a, b, c,则解锁时间期望值为

为典型的前缀和。

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 步三种状态的概率了。由此可以知道行情什么时候大涨大跌,从而发家致富,赢取白富美,走向人生巅峰。比如我们想知道第1步之后“行情大跌”的概率,那么由全概率公式和马尔科夫链的性质(第t步的概率只和第t-1步有关):

可以通过该模型,计算出第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,每行有三个浮点数

输出描述

如果第t步的“行情大涨”概率大于0.5那么输出1,否则输出0

个人题解

标准的矩阵幂运算,可采用快速幂的技巧

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。

输出描述

一个正整数,第t秒满负荷工作的水站数量。

个人题解

这个只会模拟暴力解,然后算完之后记录下第 i 个水站满负载的时间 full_time[i] 进行打表然后使用二分法进行搜索。应该还有更正确的方法进行计算
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 个整数,该矩形代表标记完轰炸区域后的结果呈现。

由于勾勒的随机性,有可能不能形成封闭区域,此时,只需要输出原矩形即可。

个人题解

图的遍历。我这里使用 BFS,并把地图扩大了一圈,并默认标记为 2,遍历之后的点标为 0。

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]))


全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐