这次笔试好难，蹭网笔试到一半电脑没电关机了，难上加难。

第一题 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个操作：

1. x = x * 2
2. x = x * 3
3. x = x +1
4. 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')