分类目录归档：刷题

339D - Xenia and Bit Operations

464 views

https://codeforces.com/problemset/problem/339/D
题意：2^n个数组成的数组，m次单点修改带查询。数组计算规则是相邻两数先做或运算得到新数组，新数组相邻两数再做异或运算，... ，最后得到一个数即为查询结果。
看到单点修改首先想到线段树或树状数组，再观察到2^n形式正好是一颗满节点的线段树，运算选择取决于线段树层数，叶子节点上一层或运算，再上一层异或，...，询问结果实际是问根节点的值
因此在单点修改的线段树模板上只需要根据层数切换update的方式即可 

import sys
n, m = map(int, sys.stdin.readline

Read more

一文解决逆序数

407 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

线段树模板

340 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

408 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