8.23 小马智行笔试题
这次笔试好难，蹭网笔试到一半电脑没电关机了，难上加难。
第一题 0%
题目大意是给定车辆左上和右下顶点坐标，车辆沿着y轴行进，同时给定一些水，通过顶点坐标定义。求车轮接触水的时候，累计行驶里程。
这题停电前正在看，有一个思路是，可以通过水的顶点两两画线段，计算车辆x轴与线段的交点，取大于车头的y里面最小的那个。不确定可否通过。
下面这个代码是断电前写的，没有写完
if __name__ == '__main__':
T = int(input())
for t in range(T):
x1, y1, x2, y2 = map(int, input().split())
n = int(input())
ret = []
for _ in range(n):
pos = list(map(int, input().split()))
nodes = []
for i in range(1, len(pos), 2):
nodes.append([pos[i], pos[i + 1]])
n = pos[0]
cur_min = float('inf')
for i in range(n - 1):
for j in range(i, n):
# x1 y1 x2 y2
n1, n2 = nodes[i], nodes[j]
# x1 - x0 / x1 -x2 = y1 - y0/ y1 - y2
# (y1- y0)(x1 - x2) = (y1- y2) (x1 - x0)
# y1(x1 - x2) - y0(x1- x2) = y1(x1 - x0) - y2(x1 -x0)
# y1 = (y0(x1 - x2) - y2(x1 - x0)) / (x1 - x2) - x1 - x0
y_1 = (n1[1] * (x1 - n2[0]) - n2[1] * (x1 - n1[0])) / (n1[0] - n2[0])
if min(n1[1], n2[1]) <= y_1 <= max(n1[1], n2[1]):
cur_min = min(cur_min, y1)
y_1 = (n1[1] * (x2 - n2[0]) - n2[1] * (x2 - n1[0])) / (n1[0] - n2[0])
if min(n1[1], n2[1]) <= y_1 <= max(n1[1], n2[1]):
cur_min = min(cur_min, y1)
第二题 100%
给定4个操作：
- x = x * 2
- x = x * 3
- x = x +1
- x = x - 1
给定每个操作的代价，和一个数字n，计算从0到n的最小代价。
动态规划优化一下就可以：
假设dp(n)是到达n的最小代价。
from functools import lru_cache
def solve(n, costs):
@lru_cache(None)
def dp(n):
if n == 0:
return 0
if n == 1:
return costs[3]
l2 = n // 2
l3 = n // 3
ret = min(dp(l2) + (n - l2 * 2) * costs[3] + min(l2 * costs[3], costs[1]),
dp(l3) + (n - l3 * 3) * costs[3] + min(2 * l3 * costs[3], costs[0]))
if n % 2:
l2 = (n + 1) // 2
ret = min(ret, costs[2] + costs[1] + dp(l2))
if n % 3:
cnt = 3 - n % 3
l3 = (n + cnt) // 3
ret = min(ret, costs[2] * cnt + costs[0] + dp(l3))
return ret
ret = dp(n)
print(ret)
if __name__ == '__main__':
c = int(input())
for _ in range(c):
n, v1, v2, v3, v4 = map(int, input().split())
solve(n, (v1, v2, v3, v4))
第三题 80%
输入一些表达式， 包含=, !=, <, > 四个操作， 输出是关系否是正确的。
比如a = b, a > b显然是矛盾的。
思路是先处理等于的，构成几个集合，然后处理不等于的，最后处理大于的，注意小于和大于是一个情况a < b 等价于b > a
只通过了80%
from collections import defaultdict, deque
eq, larger, neq, smaller = 0, 1, 2, 3
class DSU:
def __init__(self, n):
self.parents = list(range(n + 2))
n = len(self.parents)
self.small = [set() for _ in range(n)]
self.large = [set() for _ in range(n)]
def find(self, x):
if self.parents[x] != x:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def un(self, x, y):
rx = self.find(x)
ry = self.find(y)
if rx == ry:
return
else:
self.parents[rx] = ry
def solve(graph, nodes):
mapping = {}
cnt = 0
dsu = DSU(len(nodes) + 1)
for node in nodes:
cnt += 1
mapping[node] = cnt
inverse_mapping = {}
for k, v in mapping.items():
inverse_mapping[v] = k
for [a, b] in graph[eq]:
dsu.un(mapping[a], mapping[b])
for [a, b] in graph[neq]:
if dsu.find(mapping[a]) == dsu.find(mapping[b]):
return False
for [a, b] in graph[larger]:
ra = dsu.find(mapping[a])
rb = dsu.find(mapping[b])
if ra == rb:
return False
snodes = set()
que = deque([rb])
while que:
node = que.popleft()
snodes.add(node)
sms = dsu.small[node]
for _n in sms:
if _n not in snodes:
snodes.add(_n)
que.append(_n)
lnodes = set()
que = deque([ra])
while que:
node = que.popleft()
lnodes.add(node)
sms = dsu.large[node]
for _n in sms:
if _n not in lnodes:
lnodes.add(_n)
que.append(_n)
u = lnodes.intersection(snodes)
if len(u):
return False
# for lnode in lnodes:
# dsu.small[lnode] = dsu.small[lnode].union(snodes)
# for snode in snodes:
# dsu.large[snodes] = dsu.large[snode].union(lnodes)
dsu.small[ra].add(rb)
dsu.small[rb].add(ra)
return True
if __name__ == '__main__':
N = int(input())
for _ in range(N):
M = int(input())
graph = defaultdict(list)
nodes = set()
for k in range(M):
equation = input()
if '!=' in equation:
[a, b] = equation.split('!=')
graph[neq].append([a, b])
elif '>' in equation:
[a, b] = equation.split('>')
graph[larger].append([a, b])
elif '<' in equation:
[a, b] = equation.split('<')
graph[larger].append([b, a])
else:
[a, b] = equation.split('=')
graph[eq].append([a, b])
nodes.add(a)
nodes.add(b)
ret = solve(graph, nodes)
print('True' if ret else 'False')
#笔试题目#
