携程 算法 9.9笔试

class Solution:
    # 方法1
    def maxRecArea_1(self, grid, k: int) -> int:
        n, m = len(grid), len(grid[0])
        res = float("-inf")
        for i in range(n - k + 1):
            for j in range(m - k + 1):
                nums = [grid[i:i + k][a][j:j + k] for a in range(k)]
                # print(nums)
                res = max(res, sum(sum(nums[i]) for i in range(k)))

        return res

    # 方法2
    def maxRecArea(self, grid: List[List[int]], k: int) -> int:
        n, m = len(grid), len(grid[0])
        res = float("-inf")
        tmp = 0
        for i in range(n - k + 1):
            for j in range(m - k + 1):
                for a in range(k):
                    for b in range(k):
                        tmp += grid[i + a][j + b]
                # print(tmp)
                res = max(res, tmp)
                tmp = 0

        return res


if __name__ == "__main__":
    sl = Solution()
    N, M, K = input().split()
    N, M, K = int(N), int(M), int(K)
    board = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        board.append(tmp)

    # print(board)
    print(sl.maxRecArea(board, K))

import collections

class Solution:
    def operationGoods(self, arr):
        n = len(arr)
        capacity = 0  # 仓库容量
        deadline = 0  # 有效期
        res = []
        cur_nums = 0
        for i in range(n):
            tmp = arr[i]
            if tmp[0] == 1:
                cur_nums = tmp[1]
                capacity += cur_nums
                deadline = tmp[2]
            elif tmp[0] == 2:
                if tmp[1] > capacity:
                    res.append("no")
                else:
                    cur_nums = tmp[1]
                    capacity -= cur_nums
                    res.append("yes")
            elif tmp[0] == 3:
                deadline -= 1
                if deadline == 0:
                    capacity -= cur_nums
            elif tmp[0] == 4:
                res.append(deadline)

        return res


if __name__ == "__main__":
    sl = Solution()
    N = int(input())
    nums = []
    for _ in range(N):
        nums.append(list(map(int, input().split())))
    # print(nums)
    ans = sl.operationGoods(nums)
    for a in ans:
        print(a)

import collections

class Solution:
    def __init__(self):
        self.sum = 0

    def sumSubTreeUniqueness(self, graph, nums):
        n = len(graph)  # 节点个数
        def dfs(node: int, cur):
            if not node:
                return
            if not graph.get(node, None):
                res.append(0)
                return
            for next_node in graph[node]:
                # print(next_node)
                cur ^= nums[next_node - 1]
                # print(next_node)
                if cur:
                    # print("yes")
                    self.sum += 1
                    res.append(self.sum)
                    break
            for next_node in graph[node]:
                dfs(next_node, cur)

        res = []
        for i in range(1, n + 1):
            dfs(i, nums[i - 1])

        return res


if __name__ == "__main__":
    sl = Solution()
    N, index = input().split()
    N, index = int(N), int(index)
    Arrs = list(map(int, input().split()))
    connections = []
    for _ in range(N - 1):
        connections.append(list(map(int, input().split())))
    # print(connections)
    Graphs = collections.defaultdict(list)
    for c in range(N - 1):
        Graphs[connections[c][0]].append(connections[c][1])
        # Graphs[connections[c][1]].append(connections[c][0])
    # print(Graphs)
    ans = sl.sumSubTreeUniqueness(Graphs, Arrs)
    # print(ans)
    for a in ans:
        print(a, end=" ")