题目链接：https://www.luogu.com.cn/problem/P3956题目大意给定一个 m * m 的棋盘，部分格子有颜色（红色 0 或黄色 1），其余为无色。你从左上角 (1,1) 出发，要走到右下角 (m,m)。规则如下：你只能站在有颜色的格子上（包括通过魔法临时染色的）；相邻移动时：若两格颜色相同，花费 0 金币；若不同，花费 1 金币；可以花费 2 金币施展魔法，将一个相邻的无色格子临时变为你指定的颜色（必须与当前格子颜色相同）；魔法不能连续使用：只有当你站在一个原本就有颜色的格子上时，才能再次使用魔法；魔法效果只在你站在该格子时有效，一旦离开，格子恢复无色。目标：求从...

题目链接：https://www.luogu.com.cn/problem/P5194题目大意给定一个天平，最大承重为 C。有 N 个砝码，质量按非降序排列，并且从第 3 个开始，每个砝码的质量 至少等于前两个砝码质量之和（即满足类似斐波那契的性质）。要求选出若干砝码，使得它们的总质量 不超过 C，并且尽可能大。换句话说：在满足总质量 ≤ C 的前提下，求能选出的最大砝码质量和。关键观察1. 砝码序列具有“快速增长”特性题目中给出一个重要条件：从第 3 个砝码开始，每个砝码 ≥ 前两个砝码之和。这意味着砝码序列增长非常快（至少是斐波那契级别），因此：即使 N = 1000，实际有效的砝码数量也...

题目链接：https://www.luogu.com.cn/problem/P1093题解：奖学金（NOIP2007 普及组 T1）题目大意有 n 名学生（5 <= n <= 300），每人有语文、数学、英语三科成绩。定义每个学生的总分为三科成绩之和。现需按以下规则对所有学生排序，并输出前 5 名的学号和总分：首先按总分从高到低排序；若总分相同，按语文成绩从高到低排序；若总分和语文成绩都相同，按学号从小到大排序（即学号小的排在前面）。注意：学号从 1 开始，对应输入的第 i 行（i = 1 到 n）。解题思路本题是一道典型的多关键字排序问题，关键在于正确实现比较规则。我们可以为每个...

题目链接：https://www.luogu.com.cn/problem/P1883题解：求多个二次函数最大值的最小值题目大意给定 n 个形如 f_i(x) = a_i x^2 + b_i x + c_i 的二次函数（允许退化为一次函数），定义F(x) = max{f_1(x), f_2(x), ..., f_n(x)}求 F(x) 在区间 [0, 1000] 上的最小值。输出结果保留小数点后四位，四舍五入。关键观察每个 f_i(x) 是凸函数或线性函数因为题目保证 a_i >=0（输入范围：0 <= a <= 100$），所以每个 f_i(x) 要么是开口向上的抛物线，要...

题目链接：https://www.luogu.com.cn/problem/P3382题解：单峰函数极值点的三分查找题目大意给定一个 N 次多项式函数f(x) = a0 x^N + a1 x^(N-1) + ... + a（N-1）x + aN（输入顺序为从高次项到常数项），并保证在区间 [l, r]上存在唯一一点 x，使得：在 [l, x] 上函数单调递增；在 [x, r]上函数单调递减。即：函数在 [l, r]上是严格单峰的，存在唯一极大值点。要求：求出该极大值点 x 的值，满足与标准答案的绝对或相对误差不超过 10^(-5)，或其对应的函数值误差满足该条件。解题思路由于函数在给定区间上是...

题目链接：https://www.luogu.com.cn/problem/P2678题目大意在一条长度为 L的河道中，起点位于位置 0，终点位于位置 L。中间有 N 块岩石，位置已知且按升序给出。现在最多可以移走 M 块岩石（不能动起点和终点），目标是使得选手在跳跃过程中所有相邻两步之间的最短距离尽可能大。输出这个最大可能的最短跳跃距离。解题思路1. 转化问题：最大化最小值 → 二分答案这是一个典型的 “最大化最小值” 问题，非常适合使用 二分答案：我们猜测一个最短跳跃距离 mid。判断是否可以通过移走不超过 M 块岩石，使得任意相邻保留岩石之间的距离都不小于 mid。如果可以，则说明答案至...

题目链接：https://www.luogu.com.cn/problem/P1419题目大意给定一个长度为 n 的整数序列 a，以及两个整数 S 和 T。要求在所有长度在区间 [S, T] 内的连续子数组中，找出平均值最大的那个，并输出其平均值（保留三位小数）。解题思路1. 暴力法不可行若直接枚举所有满足长度在 [S, T] 范围内的子数组，时间复杂度为：O(n * (T - S + 1))约等于 O(n^2)对于 n = 10^5 来说显然会超时。2. 二分答案 + 单调队列优化我们考虑使用 二分答案 的思想：我们可以构造新数组 bi = i - mid，然后判断是否存在长度在 [S, T...

题目链接：https://www.luogu.com.cn/problem/P1102题解：统计满足 A - B = C 的数对个数题目大意给定一个长度为 N 的正整数序列和一个正整数 C，求有多少对 (i, j)（i ！= j，位置不同即视为不同）满足：Ai-Aj=C注意：即使数值相同，只要位置不同就算作不同的数对。解题思路转化问题将等式变形：Ai = Aj + C也就是说，对于每个元素 x，我们想知道序列中有多少个元素等于 x + C。于是问题转化为：对每个 x，统计 x + C 出现的次数，并累加。方法一：排序 + 双指针核心思想先将数组排序；使用两个指针 l 和 r，维护 nums[r...

题目链接：题解：合并果子（哈夫曼编码思想）题目大意有 n 堆果子，每堆有一定数量的果子。每次可以合并任意两堆，消耗的体力等于这两堆果子数量之和。目标是通过 n-1 次合并将所有果子合并成一堆，使得总消耗体力最小。解题思路问题本质这是一道经典的 哈夫曼树（Huffman Tree） 构造问题。每次合并两堆果子，相当于在哈夫曼树中合并两个叶子节点；合并代价 = 两堆重量之和；总代价 = 所有内部节点的权值之和；要使总代价最小，应总是优先合并当前最小的两堆。贪心策略：每次从所有堆中选出最小的两个进行合并，这样可以让小的数尽可能少地参与后续累加，从而最小化总代价。数据结构选择为了高效地获取和维护当前最...

题目链接：https://www.luogu.com.cn/problem/P1168题解：动态维护前奇数项的中位数题目大意给定一个长度为 N 的非负整数序列 A ，要求对每个前缀 A_1, A_2, ，，A_{2i-1} （即前 1 项、前 3 项、前 5 项……）求出其中位数，并输出。解题思路中位数定义回顾对于一个奇数长度的有序序列，中位数是排序后位于中间位置的那个数。例如：[1,3,5] 的中位数是 3；[1,3,5,6,9] 的中位数是 5。因此，对于前 2i - 1 个元素，我们要找出第 i 小的数。暴力做法（不可行）每次读入新元素后，对当前前缀排序并取中间值。时间复杂度为 O(N^...

题目链接：https://www.luogu.com.cn/problem/P1030题目大意给定一棵二叉树的 中序遍历 和 后序遍历 序列（每个节点用不同的大写字母表示，节点数 ≤ 8），要求输出该二叉树的 先序遍历 序列。解题思路1. 三种遍历的特点回顾先序遍历（Preorder）：根 → 左子树 → 右子树 中序遍历（Inorder）：左子树 → 根 → 右子树 后序遍历（Postorder）：左子树 → 右子树 → 根关键性质：后序遍历的最后一个元素 一定是当前子树的 根节点在 中序遍历中找到该根的位置，其左边是左子树，右边是右子树利用这个划分，可以递归地重建整棵树，并直接输出先序序列...

题目链接：https://www.luogu.com.cn/problem/P1229题目大意给定一棵二叉树的前序遍历和后序遍历序列（每个字符唯一），要求计算可能的中序遍历序列的总数。注意：仅凭前序 + 后序 无法唯一确定一棵二叉树（特别是当某个节点只有一个子节点时，无法判断是左孩子还是右孩子），因此可能存在多种合法的中序遍历。核心观察1. 前序与后序的特点前序：根 → 左子树 → 右子树 后序：左子树 → 右子树 → 根设前序为 pre，后序为 post，长度为 n。pre[0] 和 post[n-1] 都是整棵树的根节点。若树只有一个节点（n == 1），则中序只有一种可能。2. 关键难点...

题目链接：https://www.luogu.com.cn/problem/P1087题目大意给定一个长度为 2^N 的 01 字符串，按照如下规则构建一棵 FBI 树：如果字符串全是 0，称为 B 串，对应节点类型为 'B'如果字符串全是 1，称为 I 串，对应节点类型为 'I'否则（既有 0 又有 1），称为 F 串，对应节点类型为 'F'构建方式是递归的：根节点表示整个字符串若字符串长度大于 1，则从中间切开成两个等长子串，分别构造左右子树最后要求输出这棵 FBI 树的 后序遍历序列。解题思路1. 递归建树 + 后序遍历题目已经给出了明确的递归结构，我们可以直接模拟这个过程：对于当前区间...

题目链接：https://www.luogu.com.cn/problem/P1739 题目解析输入是一个由小写字母、运算符（+ - * /）、左右括号 () 和结束符 @ 组成的字符串。只需关注 圆括号的匹配性，其他字符（包括字母、运算符、@）均可忽略。匹配规则：每个 ) 必须有其前面未匹配的 ( 与之对应；最终不能有多余的 ( 或 )。示例：(a+b) → YES ((a+b) → NO（多一个左括号） a+b) → NO（右括号无匹配）核心思想遍历字符串中的每个字符：遇到 (：入栈；遇到 )：若栈为空 → 多余的右括号，直接输出 NO 并退出；否则弹出一个 (（表示匹配成功）；遍历结束后...