20220914携程笔试题解
T1
游游拿到了一个边长为n的正方形披萨,她准备切k刀(每刀只能横着或竖着切开),最终会形成若干个小矩形披萨。游游希望每个小披萨的面积相等,且矩形的长和宽的差的绝对值尽可能小。你能帮游游求出每个小矩形的面积吗? 输入描述: 两个正整数n和k,用空格隔开。 1<n,k<100 输出描述: 一个浮点数,代表每个小矩形的面积,小数点后保留2位。 input: 2 1 output: 2.00
因为要尽量小,一边切n/2刀,一边切n-n/2刀。要求切出来的矩形面积都相等,均匀切就可以了。
n, k = map(int, input().split()) if k == 1: print('%.2f' % (n * n / 2)) else: m = k // 2 a = n / (m + 1) b = n / (k - m + 1) print('%.2f' % (a * b))
T2
游游拿到了一个2行2列的01矩阵a,她每次操作可以交换a的相邻两个元素(同一行或者同一列均为相邻)。游游想知道至少要多少次操作可以使得矩阵a变成矩阵b? 共有t组询问。 输入描述: 第一行输入一个正整数t<100,代表询问的次数。 每组询问共有4行,每行两个正整数。前两行用来表示矩阵a,后两行用来表示矩阵b。 输出描述: 输出t行,每行输出一行答案。 如果无论如何都不能使得矩阵a变成矩阵b,则输出-1。 否则输出一个整数,代表操作的最小次数。 input: 2 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 output: 2 -1
经典bfs。
from collections import deque def trans(m): return m[0][0] * 1000 + m[0][1] * 100 + m[1][0] * 10 + m[1][1] for _ in range(int(input())): a = [list(map(int, input().split())), list(map(int, input().split()))] b = [list(map(int, input().split())), list(map(int, input().split()))] target = trans(b) ans = -1 q = deque() q.append((0, a)) seen = set([trans(a)]) while q: price, m = q.popleft() if trans(m) == target: ans = price break nxts = [ [ [m[0][1], m[0][0]], m[1] ], [ m[0], [m[1][1], m[1][0]] ], [ [m[1][0], m[0][1]], [m[0][0], m[1][1]] ], [ [m[0][0], m[1][1]], [m[1][0], m[0][1]] ] ] for nxt in nxts: v = trans(nxt) if v not in seen: q.append((price + 1, nxt)) seen.add(v) print(ans)
T3
游游拿到的一个数组,其中一些数被染成红色,另一些数被染成蓝色。 游游每次操作,可以使得所有红色的数加1,或者可以使得所有蓝色的数减1。一共可以操作任意次。 游游希望最终数组的最大值减去最小值的差尽可能小,你能帮她求出这个差吗? 输入描述: 输入包含多组测试用例,第一行一个正整数t,表示测试用例组数。 每组测试用例的第一行输入一个正整数n,代表数组的长度。 第二行输入n个正整数ai,代表游游拿到的数组。 第三行输入一个长度为n的、仅由'R'和'B'两种字符组成字符串,第i个字符为'R'代表第i个数染成红色,为‘B'代表染成蓝色。 1<n<2e3 1 < ai < 1e9 保证所有测试用例的n的总和不超过2e5 input: 1 5 1 2 3 4 5 RRBRB output: 3 说明:对红色的数和蓝色的数各操作一次,数组变成[2,3,2, 5,4],此时数组的最大值减最小值等于3。可以证明这个差无法小于3。
贪心。因为红色值只能向上,蓝色值只能向下,只需要维护红色最大值最小值和蓝色最大值最小值。比如红色最大值更大的时候说明没有必要对红色进行操作,蓝色最小值最小的时候就没有必要对蓝色操作。否则要看将红色对齐到蓝色的代价和将蓝色对齐到红色的代价。
for _ in range(int(input())): n = int(input()) *a, = map(int, input().split()) c=input() red = [a[i] for i in range(n) if c[i] == 'R'] blue = [a[i] for i in range(n) if c[i] == 'B'] if not red: print(max(blue) - min(blue)) continue if not blue: print(max(red) - min(red)) continue rmax, rmin = max(red), min(red) bmax, bmin = max(blue), min(blue) if rmax >= bmax: if bmin <= rmin: print(abs(rmax - bmin)) else: print(abs(rmax - rmin)) else: # 动红 ans = abs(bmax - min(bmin, rmin + bmax - rmax)) # 动蓝 ans = min(ans, rmax - min(bmin - bmax + rmax,rmin)) print(ans)
T4
游游定义一个矩阵权值为:每一对相邻元素之和的总和。 例如,对于矩阵: 12 34 它的权值是(1+2)+(1+3)+(2+4)+(3+4)=3+4+6+7=20。 游游希望你构造一个n*n的矩阵,矩阵中的元素为1到n*n且每个数恰好出现一次。她希望最终矩阵的权值尽可能大。你能帮帮她吗?由于矩阵可能过大,你不需要输出最终的矩阵,只需要输出这个最大权值即可。答案对1e9+7取模。 输入描述: 一个正整数n。 2 <n <1e9 俞出描述: 矩阵的最大权值,对1e9+7取模。 input: 2 output: 20 input: 3 output: 134
贪心,显然将n*n以内的数排序之后,最中心的区域每个元素有4个相邻,边上每个元素有3个相邻,角落每个元素有2个相邻。依次放下可以了。由于n是1e9级别,没法模拟运算,但是知道某一块区域放的元素都是连续的,可以使用等差数列求和。
其他语言注意处理中间取余,因为数据范围可能超long long
n = int(input()) arr = list(range(1, n * n + 1)) mod = int(1e9) + 7 central = (n - 2) * (n - 2) edge = (n - 2) * 4 point = 4 def get(l, r): return ((r + l) * (r - l + 1) // 2) % mod ans = 2 * get(1, 4) v = 5 ans = (ans + get(v, v + edge - 1) * 3) % mod v += edge ans = (ans + get(v, v + central - 1) * 4) % mod print(ans)#题解##携程##笔试#