栈

表达式解析

leetcode 1006
逆波兰表达式需要维护数字和操作符两个栈，这题由于操作符顺序是固定的，可以不用操作符栈。
题目乘法和除法是连在一起算的，加法是单独算的，减法减去的值总是乘除的结果，模拟一下即可。
需要注意除法的负数取值。

未完待续...

Read more

前缀和

前缀和与哈希表

leetcode 523
题意：问是否存在子数组（长度大于1）的和能被k整除。
前缀和的经典问题，务必掌握。
子数组的和可以表示为两个前缀和相减的形式，看到整除第一反应应该是对k求余余数为0，因此推出两个前缀和关于k同余。
把前面的前缀和对k对余数加入哈希表，遍历前缀和的时候O(1)查找

未完待续...

Read more

滑动窗口和双指针

分组循环

一种特殊情况的同向双指针，可以优化一个指针

适用场景

数组会被分割成若干组，每一组处理逻辑是相同的。

核心思想

外层循环负责遍历组之前的准备工作（记录开始位置），和遍历组之后的统计工作（更新答案最大值）。
内层循环负责遍历组，找出这一组最远在哪结束。

模板

n = len(nums)
i = 0
while i < n:
    start = i
    while i < n and ...:
        i += 1
    # 从 start 到 i-1 是一组
    # 下一组从 i 开始，无需 i += 1

题目

leetc

Read more

平方剩余核

定义

平方剩余核 core(n) 为 n 除去完全平方因子后的剩余结果。

模板

MX = 100_001
core = [0] * MX
for i in range(1, MX):
    if core[i] == 0:
        for j in range(1, isqrt(MX // i) + 1):
            core[i * j * j] = i

复杂度证明

例题

leetcode 3715
问题转化：两个数x, y相乘要想是完全平方数 => core(x) == core(y)
接着把树转成一个无向图dfs即可，注意搜索顺序，只

Read more

数位DP

leetcode 2376
模板题，用记忆化搜索实现会更加直观，需要知道的信息有：
1. 当前到第几位
2. 已选集合，避免重复
3. 是否到上限，到不到上限在同一位上可选范围是不一样的
4. 是否开始计数（考虑前导0）

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        s = str(n)
        @cache
        def dfs(i, mask, is_limit, is_num):
            if i == len(s):
       

Read more

优化DP

前缀和优化

leetcode 3699
寻找子问题：如果长度为n的序列此时是递增的，它的前一个状态必须是递减的且位置n(index从1开始)的数必须大于位置为n-1的数。这时我们发现需要两个维度和两个数组定义状态，一个维度表示当前序列长度i，另一个维度表示当前结尾的数字j。一个数组dp1表示当前状态是递增时的方案数，另一个数组dp2表示当前状态是递减时的方案数。两个数组的计算方式完全对称。为简化计算，[l, r]区间可以对应到[0, r - l]。

dp1[i][j] = dp2[i - 1][0] + dp2[i - 1][1] + ... + dp2[i - 2][j - 1

Read more

堆

第k大/小

leetcode 264
用最小堆解决，先把最小的丑数1入堆，每次出最小的x，把2x、3x、5x入堆，用哈希表去重。
leetcode 373
如果说要枚举所有点对，复杂度至少是O(n^2)起步。
想办法利用非递减顺序排列的性质：想象一个矩阵，纵坐标表示nums1下标，横坐标表示nums2下标，矩阵的值是数对和，这样一个矩阵有什么性质？显然每行都是非递减序列，每列也都是非递减序列，左上角(0, 0)点对和最小。
这样维护一个最小堆，先把第一列入堆，然后开始出堆，出堆元素坐标(i, j)，每出堆一个元素对应入堆一个元素，入堆元素坐标有两个选择：(i + 1, j)和(i, j +

Read more

二叉树

二叉搜索树

特点：一般用中序遍历 性质：中序遍历会得到一个单调递增的序列
leetcode 2476
中序遍历得到递增序列，对于每个询问做一次二分查找，时间复杂度O(n*logn)
leetcode 1932
需要观察出两个性质：
1、根节点是唯一的
2、合并方式是唯一的
1解释：一棵树能成为根节点，说明它没有出现在任何叶子节点上，无法“被”合并，如果不是唯一的，最后不可能合并成一棵树
2解释：一棵树如果能被多个叶子节点合并，假设最后能合并成一棵树，必然会有值相同的节点，不符合二叉搜索树的性质
理解上面两个性质，可以得到做法如下：
1、先找到最终树的根节点，这个根节点必然没有出现在任何

Read more

https://codeforces.com/problemset/problem/2078/D

一、题意

有 n 对门，每对门都有左、右两个通道。初始时，左右通道各有一个人，并且这些人不能中途切换通道。

当我们通过第 i 对门的某个具体门（左或右）时： * 如果是加法门 (+ a)：会额外产生 a 个新的人。该通道内原先存在的人数不变。 * 如果是乘法门 (x a)：假设该通道在操作前有 P 个人，操作后会变为 P * a 个人。这相当于原有的 P 个人每人变成了 a 个人中的一个“基底”，同时额外新增了 (a-1) * P 个人。

规则核心：在每一对门的操作完成后，所有在这一步新产生的

Read more

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

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

Read more