分类目录归档：刷题

一文解决逆序数

345 views

计算逆序数有两种思路，一种是统计归并排序过程中交换的次数，另一种是根据rank逐个修改位置计数，当前rank的逆序数等于[rank + 1, n]的区间和
leetcode有一个弱模板题

class Solution:
    def reversePairs(self, record: List[int]) -> int:
        a = record
        if a == []:
            return 0
        global ans
        ans = 0
        def change(nums1, nums2):

Read more

线段树模板

274 views

用python重写下线段树模板，线段树的记忆点在于脑子里要有线段树，特点是自顶向下构建

class segment_tree:
    def __init__(self, nums):
        n = len(nums)
        self.nums = nums
        self.tree = [0] * 4 * n
        self.tag = [0] * 4 * n

    def update(self, root):
        self.tree[root] = self.tree[root * 2] + self.tree[root * 2

Read more

29C - 6 Mail Stamps

340 views

题意：从起点按序输出唯一路径
python写一直re，后面发现需要使用sys.setrecursionlimit(int(2 * 10**5))扩大python默认递归深度限制，以达到题目要求
邻接表建图用字典的setdefault方法初始化空列表最简洁

import sys
sys.setrecursionlimit(int(2 * 10**5))
n = int(input())
vised = {}
graph = {}
in_degree = {}
for _ in range(n):
    c1, c2 = map(int, input().split())
    graph.s

Read more