10.16 腾讯笔试题-技术研究

五道题，感觉都是中等难度。单独做都有思路，放在一起时间挺紧的，差点没写完。

先占坑，放AC代码。解法慢慢写

第一题：加一数字游戏

给两个数字 x，y。每次操作，可以令其中一个数加1。问 k 次操作之后，x 和 y 的最大公约数是多少

这是一道比较偏数学的题。我刚看到的时候没思路先跳过了，后面写完才回来写这个。

首先，无论如何，最终的x和y加起来的和为 x+y+k，是固定的，我们把它记为 t（代码中的变量total）。有一点很重要：x 和 y 的最大公约数，一定也是 t 的约数。

因此，先编写一个函数 fact(n)，用于将 total 的所有约数找出来。然后用贪心的方法，从大到小看每个约数是否能达到要求。

对于一个约数 d 和初始值 x，什么条件下可以让 x 加 k 次以内，变为 d 的倍数呢？这个问题不难，可以发现条件是：

k ≥ d - x % d

其实，一旦 x 能达成该条件，剩下的次数加在 y 上，最终 y 一定也是 d 的整数倍（因为他们最终加起来是 t），所以代码 14 行的第二个判断是多余的。

从大到小遍历约数。判断成功后，直接输出这个约数即可；否则找下一个。

import math
def fact(n):
    ans = set()
    for i in range(1, math.floor(math.sqrt(n) + 1)):
        if n % i == 0:
            ans |= {i, n//i}
    return sorted(list(ans))
def foo(x, y, k):
    total = x + y + k
    if x > y:
        x, y = y, x
    for d in fact(total)[1:]:
        ans = total // d
        if x % ans + k >= ans or y % ans + k >= ans:
            return ans
for _ in range(int(input())):
    x, y, k = [int(x) for x in input().split()]
    print(foo(x, y, k))

第二题：神经网络

本题难度主要在读懂题。大致题意如下：

给定一个向量 v，把它经过两个不同的线性变换，生成两个不同的向量。如果这两个向量的距离大于 t，输出1；否则输出0

输入：

第一行是向量的维度 n，线性变换矩阵的行数 m，距离 t

第二行是 n 个整数，代表这个向量。

之后 m 行是第一个线性变换矩阵，再之后 m 行是第二个线性变换矩阵

先试着在代码中写一行 import numpy，结果报错。因此需要自己实现矩阵乘法和向量距离。分别是 mul(A, B) 和 dist(A, B)，不再多说。

接下来就是读输入。注意 v 是一个 n 行 1 列的向量，两个线性变换分别用矩阵 A 和 B 表示（矩阵是 m 行 n 列）。

最后看 A*v 和 B*v 的距离是否大于 t 即可。

def mul(A, B):
    m, n, p = len(A), len(A[0]), len(B[0])
    ans = [[0] * p for _ in range(m)]
    for i in range(m):
        for j in range(p):
            tmp = 0
            for k in range(n):
                tmp += A[i][k] * B[k][j]
            ans[i][j] = tmp
    return ans
def dist(A, B):
    total = 0
    for i in range(len(A)):
        total += A[i][0] ** 2
    return total ** .5
for _ in range(int(input())):
    n, m, t = [eval(x) for x in input().split()]
    v = [[float(x)] for x in input().split()]
    A, B = [], []
    for _ in range(m):
        A.append([float(x) for x in input().split()])
    for _ in range(m):
        B.append([float(x) for x in input().split()])
    Av = mul(A, v)
    Bv = mul(B, v)
    print(1 if dist(Av, Bv) > t else 0)

第三题：国王城堡

国王有 n 个城堡，横纵坐标均为整数。现在需要找一个横线 y=a 和一个竖线 x=b，将平面分层四部分。要求每部分城堡数均相等，且没有城堡在直线上

输入：第一行 n ，然后 n 行表示城堡横纵坐标

输出：如果有可行方案，输出任意一个可行的 a, b；否则输出 -1

如果 n 不是 4 的倍数，一定是不行的。

既然 4 块都相等，那么 x=b 左右两侧的城堡数量一定也相等，据此我们先来确定 x=b 的位置。先将城堡按照横坐标排序，然后取出中间两个横坐标 b1，b2。有可行的 b 值的条件是 b2 > b1+1。任取一个作为 b 。

然后我们也将所有城堡 p 分层两半区 pl 和 pr。接下来需要确定有没有可行的 a 值。

利用相同的方法，先将 pl，pr 按照纵坐标排序，分别找到位于中间的两个纵坐标。记左半区的中间两个坐标为 al1, al2；右半区的中间两个坐标为 ar1, ar2。如果最终有可行的 y=a 直线，那么它需要同时将左右两个半区等分。因此有可行的 a 的条件是 (al1, al2) 和 (ar1, ar2) 两个开区间的交集中有整数。从中任取一个作为 a。

如果没有可行的 a 或 b，直接输出 -1。（文字读起来不是很形象，但画个图其实很好理解）

def solve():
    n = int(input())
    p = []
    if n % 4 != 0:
        return -1
    for _ in range(n):
        x, y = [int(x) for x in input().split()]
        p.append((x, y))
    p.sort()
    b1, b2 = p[n // 2 - 1][0], p[n // 2][0]
    if b2 <= b1 + 1:
        return -1
    pl, pr = p[:n // 2], p[n // 2:]
    pl = sorted(pl, key=lambda c:c[1])
    pr = sorted(pr, key=lambda c:c[1])
    al1, al2 = pl[n // 4 - 1][1], pl[n // 4][1]
    ar1, ar2 = pr[n // 4 - 1][1], pr[n // 4][1]
    a1, a2 = max(al1, ar1), min(al2, ar2)
    if a2 > a1 + 1:
        return a1 + 1, b1 + 1
    else:
        return -1

ans = solve()
if type(ans) == int:
    print(ans)
else:
    a, b = ans
    print(a, b)

第四题：小飞机

有 n 个小飞机在数轴上做匀速直线运动，给定它们的初始位置 x 和速度 v。现在可以将它们的初始位置任意调换，但速度不能交换。输出一种方案，使得没有小飞机会相撞。

输出时，每个小飞机的速度应该与输入的顺序相同。如果有多个可行解，输出一个即可。

往左速度越大的飞机，初始位置越靠左；往右速度越大的飞机，初始位置越靠右即可。

具体实现方式：先将速度 v 和输入的顺序 id 绑定。然后分别对 x 和 v 的数组进行排序。对应位置的 x 先找到一个对应的速度v，然后将 x 放在速度为 v 的飞机的位置即可。

n = int(input())
v_id = []
lv = []
lx = []
for i in range(n):
    x, v = [int(x) for x in input().split()]
    v_id.append((v, i))
    lv.append(v)
    lx.append(x)
v_id.sort()
lx.sort()
ans = [0] * n
for i in range(n):
    ans[v_id[i][1]] = lx[i]
for i in range(n):
    print(ans[i], lv[i])

第五题：修公路

有 n 个城市，城市 i 权重为 w_i。有 n-1 条公路，将这些城市连起来。现在需要找到两个城市 i 和 j，使得 w_i + w_j + dist(i,j) 最大。其中 dist(i,j) 是从 i 到 j 的公路长度之和。

输入：

第一行是 n

第二行是 n 个整数，表示每个城市的权重

之后 n-1 行是公路，a, b, c 代表公路两端为城市 a 和 b，长度为 c

输出：最大的 w_i + w_j + dist(i,j)

树的直径问题的变种。在原来的树中，每个节点 i 处加一个长度为 w_i 的边，连向一个新节点 i'，然后求新的树的直径即可。

dfs(node_id) 函数的作用：给定一个树，找到离 node_id 这个节点最远的节点。返回最远的距离和这个点。

然后，从任意一点开始dfs，找到最远的点。然后再从这个点开始dfs，找到最远距离记为所求。

from collections import defaultdict
n = int(input())
w = [int(x) for x in input().split()]
e = defaultdict(list)
def dfs(node_id):
    dis = [0] * n
    vis = {node_id}
    s = [node_id]
    while s:
        node = s.pop()
        for nxt, d in e[node]:
            if nxt not in vis:
                s.append(nxt)
                dis[nxt] = d + dis[node]
                vis.add(nxt)
    max_dist = max_node = 0
    for i in range(n):
        if dis[i] + w[i] > max_dist:
            max_dist = dis[i] + w[i]
            max_node = i
    return max_dist, max_node
for _ in range(n-1):
    a, b, c = [int(x) for x in input().split()]
    a -= 1; b -= 1
    e[a].append((b, c))
    e[b].append((a, c))
node = dfs(0)[1]
print(dfs(node)[0] + w[node])