小红书9月20日机考题目与解析（题意按回忆整理）第一行 n q，初始有一个长度为 n 的全 0 数组，q 个操作： 1 x：反转第 x 个位置（0 变 1、1 变 0） 2 l r：只对区间 [l, r] 从左到右执行下面的 tmp 规则，并输出 ans： tmp 为空 → 当前数字放入 tmp 当前数字 == tmp → 什么都不做 当前数字 != tmp → ans += 1，然后 tmp

小红书9月20日机考题目与解析（题意按回忆整理）给定数组，可以反复删除和为 0 的连续子数组——删除后左右两侧拼接，拼接产生的新零和区间可以继续删。求最多能删除多少个元素。 例如原数组： [1, -1, 2, 3, -5, 4] 任何一个和为 0 的连续区间都可以删。 思路关键转化：删除后左右拼接、继续删除的过程，最终效果等价于——选若干个互不重叠的、原数组中的零和子数组，使总长度最大。 以 [1

排序竞赛中优先使用内置 sorted / list.sort（Timsort，稳定 $O(n \log n)$）；手写六大排序主要用于理解算法与应付考点。排序本身很少是考点，考点是排序后的性质——贪心按序取、双指针要求有序、二分要求有序。 arr.sort(key=lambda x: (-x[0], x[1])) # 第一维降序、第二维升序 b = sorted(arr, key=lambda

Chicken Jockey 题解题目描述有 n 个怪物叠在一起，怪物 i (从下到上编号) 初始血量为 h[i]。 一次攻击可以对任意一个怪物造成 1 点伤害。当怪物血量 ≤ 0 时死亡，其上方的所有怪物会掉落。掉落的怪物中，底部的怪物会受到等于其下方怪物数量的摔落伤害。如果摔落后死亡，过程继续。 求最少需要多少次攻击才能消灭所有怪物。 解法问题类型：线性 DP（状态转移只与前几个状态相关，呈

网格路径问题问题概述DP 问题的一个常见原型涉及由正方形单元格组成的 2D 网格（类似于方格纸），我们需要分析”路径”。路径是一系列单元格的序列，其移动仅限于在 $x$ 轴的一个方向和 $y$ 轴的一个方向（例如，你可能只能向下或向右移动）。通常，路径还必须从网格的一个角落开始，并在另一个角落结束。问题可能要求你计算满足某些属性的路径数量，或者可能要求你在所有路径中找到某个量的最大值或最小值。

最长递增子序列令 $A$ 为我们要寻找最长递增子序列（LIS）的数组。 慢速解法令 $dp[i]$ 表示以 $arr[i]$ 结尾的最长递增子序列的长度。我们可以通过简单的方法在 $O(N^2)$ 时间内计算 $dp$（从而得到 ans）： from typing import List def find_lis(arr: List[int]) -> int: ans = 0

背包DP模板0-1 背包（倒序）N, W = map(int, input().split()) w = list(map(int, input().split())) v = list(map(int, input().split())) dp = [0] * (W + 1) for i in range(N): for j in range(W, w[i] - 1, -1):

输入输出基础输入# 单个整数 n = int(input()) # 多个整数（空格分隔） a, b = map(int, input().split()) # 一行整数转列表 arr = list(map(int, input().split())) # 去除换行符 s = input().strip() # 去除首尾空白（含 \n） # 读取 n 行到列表 arr = [int(inp

优先队列模板import heapq pq = [] heapq.heapify(pq) # 把已有列表原地转成堆，O(n) heapq.heappush(pq, x) # 插入元素 smallest = pq[0] # 获取最小元素（不弹出） smallest = heapq.heappop(pq) # 弹出并返回最小值 方

二分查找模板有序数组：bisect bisect 函数 对应 C++ 含义 bisect.bisect_left(arr, x) lower_bound 第一个 >= x 的下标 bisect.bisect_right(arr, x) upper_bound 第一个 > x 的下标 import bisect arr = sorted([...]) # 先