前言

笔试一共三道编程题,分数依次为100、200、300,需要按顺序依次完成,只有做完这一道题,才能进入下一道题,无法跳题,使用的是牛客网,允许跳出界面使用自己的IDE。

题目一:字符串分割

给定一系列的字符串,字符串的个数为N,每个字符串的长度不超过100。长度小于8的字符串用零补足,长度大于等于8的字符串,按8位位一组的形式不断分割,最后剩余部分用零补足。

输入:

第一行包括一个整数N和N个原始字符串。

输出:

第一行包括分割后的字符串按字典序从小到大排列。

输入示例:

2 abc 123456789

输出示例:

12345678 90000000 abc00000

思路:

这一题比较简单,只需要按照题目的描述做即可。

inp = input().split()
n = int(inp[0])
ls = []
for i in range(1, n+1):
    string = inp[i]
    while len(string) > 8:
        ls.append(string[:8])
        string = string[8:]
    ls.append(string + "0"*(8-len(string)))
ls.sort()
print(" ".join(ls))

题目二:蜜蜂采蜜

平原上,一群蜜蜂离开蜂巢采蜜,要连续采集5片花丛后归巢。
已知5片花丛相对蜂巢的坐标,请你帮它们规划一下到访花丛的顺序,以使飞行总距离最短。

输入:

以蜂巢为平面坐标原点的5片花丛A、B、C、D、E的坐标,坐标值为整数。

输出:

从出发到返回蜂巢最短路径的长度取整值,取整办法为舍弃小数点后面的值。

输入示例:

200 0 200 10 200 50 200 30 200 25

输出示例:

456

说明:

样例中的10个数,相邻两个分别为一组,表示一个花丛相对蜂巢的坐标:A(x1, y1)、B(x2, y2)、C(x3, y3)、D(x4, y4)、E(x5, y5),分表代表x1,y1,x2,y2,x3,y3,x4,y4,x5,y5。

说明:

本题实际上是一道旅行商问题(TSP),经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。从图论的角度来看,该问题实质是在一个带权完全无向图中,找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。

常见的解法有暴力破解、深度优先遍历,动态规划等。

高级的解法有模拟退火算法,遗传算法,粒子群算法、神经网络等

思路一:

暴力破解,求出五片花丛所有可能的到访顺序(全排列),取飞行总距离最短的路径即可。

from math import sqrt, floor
from xmlrpc.client import MAXINT
inp = list(map(int, input().split()))
mincost = MAXINT
ls = [(inp[i*2], inp[i*2+1]) for i in range(5)]
matrix = [[0 for i in range(5)] for j in range(5)]
for i in range(5):
    for j in range(5):
        matrix[i][j] = sqrt((ls[i][0]-ls[j][0])**2 + (ls[i][1]-ls[j][1])**2)

def Perm(nums, begin, end):
    global mincost, ls, matrix, path
    if begin >= end:
        cost = 0
        for i in range(4):
            cost += matrix[nums[i]][nums[i+1]]
        cost = cost + sqrt((ls[nums[0]][0]**2) + (ls[nums[0]][1]**2)) + sqrt((ls[nums[-1]][0]**2) + (ls[nums[-1]][1]**2))
        if cost < mincost:
            path = nums
            mincost = cost
        return
    else:
        for num in range(begin, end):
            nums[begin], nums[num] = nums[num], nums[begin]
            Perm(nums, begin+1, end)
            nums[begin], nums[num] = nums[num], nums[begin]

nums = [i for i in range(5)]
Perm(nums, 0, len(nums))
print(floor(mincost))

思路二:

采用深度优先遍历来寻找最短路径,并在遍历过程中通过不断剪枝来简化求解过程,广义上来讲也是全排列的一种。

from math import sqrt, floor
from xmlrpc.client import MAXINT

def DFS(u, cnt, cost):
    global mincost, matrix, visited
    if cost > mincost:
        return
    if cnt == 6:
        cost = cost + sqrt((ls[u][0]**2) + (ls[u][1]**2)) + sqrt((ls[0][0]**2) + (ls[0][1]**2))
        if cost < mincost:
            mincost = cost
    visited[u] = 1
    for v in range(6):
        if not visited[v]:
            DFS(v, cnt+1, cost + matrix[u][v])
    visited[u] = 0

inp = list(map(int, input().split()))
mincost = MAXINT
visited = [0 for i in range(6)]
ls = [(inp[i*2], inp[i*2+1]) for i in range(5)]
ls.insert(0, (0, 0))
matrix = [[0 for i in range(6)] for j in range(6)]
for i in range(6):
    for j in range(6):
        matrix[i][j] = sqrt((ls[i][0]-ls[j][0])**2 + (ls[i][1]-ls[j][1])**2)

DFS(0, 1, 0)
print(floor(mincost))

惨痛经历

因为邮件上写着系统开放时间为18:00-21:00(不同于美团写着笔试时间为16:00-18:00),所以我习惯性得以为笔试时间为三个小时,当我悠哉游哉地把第二题做完返回系统时,笔试已经结束了,因此只提交了第一题,直接人麻了。。。所以,各位小伙伴无论是在比赛还是在测试,一定先看好时间!!!当然,对于秒AK的大佬来说,时间根本不是事,那就当我没说。

凉梦空间

欢迎你进入我的个人博客网站参观交流:https://www.liangmeng.xyz

来源:MAC、凉梦

物联沃分享整理
物联沃-IOTWORD物联网 » 荣耀笔试题_20220412

发表评论