[备忘记录]蓝桥杯AC题单

🏆 备战蓝桥杯 AC 题单

Deadline: 2026-4-11 9:00:00 (最终验收日)

---

🟢 模块一：前缀和与差分（1D & 2D）

核心架构：用极小的空间代价换取绝对的时间降维。前缀和将“$O(N)$ 区间查询”压缩至极速的 $O(1)$，差分将“$O(N)$ 区间修改”降维至 $O(1)$。这是算法世界中最优雅的“预处理引擎”，本质是空间换时间的物理魔法。

平台	题号	题目	考察点 (实战陷阱 / 降维技巧)
洛谷	P10233	dx 分计算	1D 前缀和的基础构建与区间查询。
洛谷	B4192	分数线	数据溢出预警：$10^5$ 级别运算强制开启 long long；1-Index 优势：完美规避 $k-1=0$ 时的下标越界；注意多重约束条件的漏判。
洛谷	P2367	语文成绩	1D 差分的标准起手式：b[l] += d 与 b[r+1] -= d，注意数组防越界多开 5 个单位。
洛谷	P11853	植树节	1D 差分的区间操作验证，强化差分还原为原数组的逻辑。
洛谷	P2004	领地选择	静态内存炸弹：警惕 $N^2$ 级别的大数组（$10^5$ 的二维数组会占 40GB 导致直接 RE）；矩阵四角容斥公式推导；避免全局变量与局部变量同名遮蔽。
洛谷	P3397	地毯	2D 差分的核心引擎：矩形区域的四角修改操作（+ - - + 容斥结构），以及利用二维前缀和恢复原矩阵。
洛谷	P1387	最大正方形	语法刺客：警惕 if(temp = len*len) 的致命赋值错误，必须用 ==；跨界降维：使用 2D前缀和 + 暴力枚举边长（$O(N^3)$）硬刚 DP 题。
洛谷	P8648	油漆面积 (真题)	坐标系平移：点坐标不等于网格面积，强制加 1 平移消灭 -1 越界死劫；极限内存压榨：将 int 降级为 short（2字节），在 256MB 限制下跑通 $10000 \times 10000$ 差分矩阵进行暴力骗分。

---

🟡 模块二：模拟与工程能力（Simulation）

核心架构：将繁杂的现实物理规则，精准翻译为数据流与状态机。杜绝暴力的 if-else 堆砌，利用“取模周期 %”、“全局查表法 (Table-driven)”和“坐标系平移”建立极简的工程级代码骨架，极其考验后端的边界防爆破能力。

平台	题号	题目	考察点 (实战陷阱 / 降维技巧)
洛谷	P1042	乒乓球	字符串与状态机：处理跨行、极长的混合字符串输入流；处理 11 分制与 21 分制的双轨计分；暗坑：必须满足“领先 2 分”才算胜出（如 12:10），且要处理刚好打完一局后出现 E 的极端情况。
洛谷	P1067	多项式输出	极端格式恶心人：蓝桥杯最爱的输出格式考察。暗坑遍地：系数为 $1$ 或 $-1$ 时省略数字只输出符号；次数为 $1$ 时不输出 ^1；系数为 $0$ 时整项跳过；第一项是正数时绝对不能输出 + 号。
洛谷	P1563	玩具谜题	环形数组与周期：蓝桥杯必考的“围成一圈”模型。降维技巧：不要用复杂的链表，直接用一维数组配合取模运算 % 来模拟顺时针和逆时针的坐标移动。利用 异或(^) 操作简化朝向与指令的判断。
洛谷	P1328	生活大爆炸版石头剪刀布	周期嵌套与查表法：两人周期不同，求 $N$ 轮后的得分。降维技巧：千万不要写几十个 if-else 去判断谁赢谁输，直接在全局建立一个 5x5 的二维常量胜负表 table[A][B]，用取模获取当前出拳，一招绝杀。

🔴 模块三：二分查找（Binary Search）

核心架构：从“在物理数组中找下标”跨越到“凭空猜答案并验证（二分答案）”。

平台	题号	题目	考察点 (实战陷阱 / 降维技巧)
洛谷	P2249	查找 (深基例)	防爆破基础：找第一个 >= target 的左边界。陷阱：死循环。降维技巧：纯手写边界控制，向下取整 mid = l + r >> 1 配合 r = mid 与 l = mid + 1，彻底杜绝死锁。
洛谷	P1824	进击的奶牛	二分答案母题（最大化最小值）：陷阱：完全迷失在 check 的编写中。降维技巧：丢掉数组，直接对“牛与牛的距离”进行二分。在单调序列 true, true, false, false 中找最后一个 true，必须果断使用 mid = l + r + 1 >> 1 补上决定生死的 +1。
洛谷	P1024	一元三次方程求解	实数二分与精度幽灵：致命暗坑：浮点数漂移与右极限逃逸（错过刚好为 100 的根）。热修复补丁：放弃 double 遍历改用 int i 锚定绝对坐标；用 -1e-8 极小值做容差判定 fl * fr < -1e-8；并在循环外单独对 100 打补丁。
洛谷	P1182	数列分段 Section II	二分答案双子星（最小化最大值）：二分枚举每一段和的上限 mid。贪心验证：写一个 check(mid) 贪心切分数段，看切出的段数是否 $\le M$。
洛谷	P2678	跳石头 (NOIP 真题)	蓝桥杯绝对圣杯：经典“最小距离的最大值”变体。操作变为“最多移除 M 块石头”，对状态机思维的终极考验，蓝桥杯整数二分必刷。

---

🟣 模块四：双指针与滑动窗口（Two Pointers / Sliding Window）

核心架构：利用单调性，让指针永远不回头（$O(N)$ 降维打击），彻底抛弃暴力的嵌套循环。

平台	题号	题目	考察点 (实战陷阱 / 降维技巧)
洛谷	P1147	连续自然数和	基础对撞与同向指针：双指针的基础形态，感受左右指针如何交替向中心收缩或同向滑动。
洛谷	P1638	逛画展	状态机双指针的分水岭：致命陷阱：写出每次扫描 $M$ 的 check() 导致 $O(N*M)$ 暴毙。降维技巧：搭建 $O(1)$ 的“动态仪表盘（diff 计数器）”。外层 r 专心吃进并更新种类，内层 l 只要满足 diff == m 就启动碎纸机榨干冗余，极其优雅。
洛谷	P1102	A-B 数对	数学降维与重复元素：题意降维：将 $A - B = C$ 转化为 $A = B + C$。双规解法：1. STL 官方外挂流（lower_bound 和 upper_bound 找连续段边界）；2. 三指针流（同向滑动的极境，一个慢指针扮演 $B$，两个快指针永远不回头地框定 $Target$ 区域）。
洛谷	P2058	海港 (NOIP 真题)	带时间戳的滑动窗口：核心变异：物理坐标轴从“数组下标”变成了“动态时间轴”。降维技巧：放弃常规双指针，直接使用队列 queue<Passenger> 作为带时间戳的传送带，结合结构体 struct 和国籍仪表盘，实现完美的进出清洗逻辑。

🔵 模块五：STL 底层架构与排序贪心 (STL & Greedy)

核心架构：拒绝重复造轮子。将复杂的业务逻辑托付给经过千锤百炼的底层容器（红黑树 map/set、大根堆 priority_queue）。掌握 cmp 自定义排序规则，就掌控了蓝桥杯大模拟与贪心调度的核心调度权。

平台	题号	题目	考察点 (实战陷阱 / 降维技巧)
洛谷	P3378	【模板】堆	兵器校验：绝对不手写数组模拟堆。直接使用 priority_queue<int, vector<int>, greater<int>> 召唤小根堆，掌握 push/top/pop 的 $O(\log N)$ 极值维护。
洛谷	P1090	合并果子	优先队列母题：经典哈夫曼树贪心。每次 pop 出两个最小值，相加计入消耗，再把和 push 回去。动态极值维护的绝对标杆。
洛谷	P1803	凌乱的yyy	结构体排序 (cmp)：区间调度模型（类比后端抢占式并发调度）。致命陷阱：按开始时间排序必死。降维技巧：必须按“结束时间”从小到大排 a.end_time < b.end_time，把更多时间留给后面的任务。
洛谷	P1059	明明的随机数	红黑树去重 (std::set)：要求去重 + 升序输出。降维技巧：抛弃繁琐的桶排序或快排双指针，直接把数字扔进 set<int>，利用其底层红黑树自动完成 $O(N \log N)$ 排序去重，代码短到令人发指。
洛谷	P1097	统计数字	键值对映射 (std::map)：统计出现次数并按数字升序输出。致命陷阱：数字高达 $1.5 \times 10^9$，开普通数组 cnt[x] 直接爆内存（超 1.5GB 段错误）。降维技巧：使用 map<int, int> 完美处理大数字离散映射。
洛谷	P3613	寄包柜	稀疏矩阵与内存压缩：要求开一个 $10^5 \times 10^5$ 的二维数组。致命陷阱：40GB 内存直接炸毁评测机。降维技巧：后端极其经典的“稀疏数据”处理思维，使用 map<int, map<int, int>>，只为实际存放了物品的格子分配内存空间，将空间复杂度降至极小。

🟠 模块六：底层数学 API 与算力降维 (Math & Complexity Reduction)

核心架构：拒绝低效的物理模拟，深入 CPU 吞吐极限。利用预处理建表（空间换时间）、二进制切割（$O(N) \to O(\log N)$）以及初等数论定理，实现绝对的算力降维。遇到 $10^5$ 以上规模的数据请求，永远优先思考如何用“查表”、“位运算”或“数学定律”去砍掉冗余的 for 循环。

平台	题号	题目	考察点 (实战陷阱 / 降维技巧)
洛谷	P5736	【模板】质数筛	全局建表与值域映射：抛弃试除法与会破坏业务顺序的无脑排序。系统启动即用 $O(N \log \log N)$ 的埃氏筛打好 bool 标记表，后续实现 $O(1)$ 极速查表。致命暗雷：作为值域映射的数组，大小必须按最大数值（$10^5$）开辟，严防内存越界 (RE)。
洛谷	P1865	A % B Problem	极致连招 (筛法+前缀和)：将埃氏筛的 bool 值隐式转换为 1/0 整型累加，构建素数前缀和数组。将 $O(N)$ 的暴力区间统计瞬间降维至 $O(1)$ 的 pre_sum[r] - pre_sum[l-1]。防御暗雷：严禁帮出题人加戏，严格按照题意只拦截 `l < 1
洛谷	P1226	【模板】快速幂	二进制降维魔法：利用 b & 1 和 b >>= 1，将 $O(N)$ 次乘法死循环物理切割至 $O(\log N)$ 的位运算拼图。终极防御矩阵：必须全员开启 long long 防爆护盾，且在 res 累乘和 base 平方升级的每一步必须立刻 % p，防止指数爆炸导致整型溢出。
洛谷	P1029	最大公约数和最小公倍数问题	数学定理的绝对剪枝：利用 $P \times Q = GCD \times LCM$ 这一初等数论绝对真理，将 $O(N^2)$ 的两重循环砍成只遍历到 $\sqrt{prod}$ 的单层循环。配合极简的三目运算符手搓 GCD 引擎，实现完美秒杀。注意 LCM 必须“先除后乘”防溢出。
AtCoder	ABC-C	袋中求最小值 (Balls in Bag)	$K+1$ 抽屉原理与游标跳跃：面对 30 万个球和 20 万次查询（暴力需 600 亿次运算必死 TLE）。绝地反击：利用“全局只排序一次” + “游标 cur_min_idx 每次从 1 开始跳跃最多 $K$ 步” + “只擦除拿走球标记的微创复原”。将 $O(N \cdot Q)$ 的必死局化解为 $O(N \log N + \sum K)$ 的极速引擎！