数组跳跃序列长度 题目描述 给定长度为 n 的数组 a 和整数 d。对于每个起点 i，从当前位置不断寻找最小的下标 j > i 满足： aj≥ai+d a_j \ge a_i + d 找到后跳到 j，令 i = j 继续；找不到则停止。 输出从每个下标出发能经过的下标序列长度。 输入格式： 第一行 t，测试用例数量； 每个测试用例：第一行 n, d，第二行长度为 n 的数组 a。 输出

NDCG 计算题解 题意 给定 JSON 数据，包含： y_true：每个样本的真实相关性标签； y_score：模型给出的预测分数； K：只计算前 K 个结果的指标。 需要计算并输出： dcg：按预测分数降序排序后的折损累计增益； idcg：按真实相关性降序排序后的理想折损累计增益； ndcg：归一化折损累计增益，即 NDCG=DCGIDCG \mathrm{NDCG} = \frac{

Custom Comparators and Coordinate Compression 自定义比较器和坐标压缩 本文介绍两种在竞赛编程中常用的技术：自定义排序和坐标压缩。 一、自定义排序 排序不仅限于数字，还可以用于任意对象。 方法一：使用元组 将对象与排序关键字打包成元组： edge_num = 4 edges = [] for _ in range(edge_num): a, b

使用递归的穷举搜索 Subsets  子集 https://cses.fi/problemset/task/1623 递归生成子集 编写一个递归函数，遍历所有可能的分组方式。 在某个索引处，我们要么将 𝚊𝚙𝚙𝚕𝚎i\texttt{apple}_i​ 添加到第一个集合，要么添加到第二个集合，存储两个总和 𝚜𝚞𝚖1\texttt{sum}_1​ 和 𝚜𝚞𝚖2\texttt{sum

Rectangle Geometry 矩形几何 什么是矩形几何问题？ 矩形几何问题是指涉及边平行于坐标轴的矩形的计算问题。这类问题在 USACO Bronze 中非常常见，主要考察对矩形面积、交集等概念的理解。 矩形表示方法 通常使用两个对角顶点来表示矩形： - 左下角 (bottom-left)：(bl_x, bl_y) - 右上角 (top-right)：(tr_x, tr_y) 注意：blx

有向图中的环检测 在有向图中检测是否存在环（Cycle）是一个经典问题。环是指从某个节点出发，沿着有向边最终能回到该节点的路径。 方法一：DFS + 三色标记 算法思想 使用三种颜色标记节点的状态： - 白色 (0)：未访问 - 灰色 (1)：正在访问（在当前递归栈中） - 黑色 (2)：已访问完成（不在递归栈中） 如果在 DFS 过程中遇到灰色节点，说明找到了环。 为什么有效？ 灰色节点表示

数论 取整 # 向上取整到 k 的倍数 (n + k - 1) // k * k import math math.ceil(n / k) * k # 更易读 # 四舍五入（整数版，避免浮点误差） def round_div(a, b): # 计算 a / b，四舍五入到整数 # 原理：判断小数部分是否 >= 0.5 return a // b + (2

图论 邻接表建图 # 邻接表 adj = [[] for _ in range(n)] # 无向图 adj[u].append(v) adj[v].append(u) adj[u].append((v, w)) # 带权重 图论基础：BFS 适合求最短路，DFS 适合遍历/搜索 ## DFS（深度优先搜索） 核心思想 “一条路走到黑，走不通就回头。” DFS 沿着一个方向一直往深处走，直到

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

经典题型 五、区间 DP 状态为 dp[i][j] 表示区间 [i, j] 的最优解。遍历顺序：区间长度从小到大。 LC 516. 最长回文子序列 516. 最长回文子序列（中等） 给定一个字符串，找到其中最长的回文子序列的长度（子序列不要求连续）。 状态：dp[i][j] = s[i..j] 中最长回文子序列的长度 转移： s[i] == s[j]：dp[i][j] = dp[i+1][