Problems & Errors

做题记录（nt错误）合集

2026-4-18

• P1955 [NOI2015] 程序自动分析
  • 初试离散化 & vector

2026-4-16

• P1525 [NOIP 2010 提高组] 关押罪犯

  • 贪心是容易的，但考虑维护罪犯（点）之间的相对关系而不是维护监狱（树），算是扩展并查集吧

• P1621 集合

  • 过拟合， $p$ 不一定是质数，还有记得注释调试代码；另外，可以边筛边合并而不用 $O(\sqrt{n})$ 判素数
  • 了解到一些统计并查集数目的方法，比如统计father为自己的节点个数，边合并边算这种

2026-3-20

• P1802 5 倍经验日

  • 这道题我是直接用插值转化为 01 背包做的，基础值应该要另外拿出来或者最后加。总之就是不要把初值设为基础值之和。

• P1064 [NOIP 2006 提高组] 金明的预算方案

  • 一道有依赖的背包问题
  • 理论上可以用树形dp做，但是我注意到 附件没有附件 ，于是就分别对附件主件做一遍01背包
  • 因为附件对主件的依赖性处理不当导致 0ptsWA
  • 最后汇总主件时内外循环错误（感觉背包问题就是循环首尾或者内外换一下完全就是另一道题） 20pts
  • 上面的都修了然后 TLE 60pts
  • 最后注意到价格都是 10 的倍数，整体 /10 最后乘回来 100pts
  • ps：没注意到附件只有 0/1/2 个，可以单独枚举情况

2026-3-19

• P2196 [NOIP 1996 提高组] 挖地雷

  • 注意 dp 数组初值！

• P1434 [SHOI2002] 滑雪 & P4017 最大食物链计数

  • 这两题反映出我做之前还处于线性 dp 思维，对遍历顺序没有拓扑概念，这时可以考虑转化为记忆化搜索去做，尤其是后面一道 DAG 问题

2026-3-18

• P1827 [USACO3.4] 美国血统 American Heritage
  • 似乎用下标递归更好（不然似乎会 MLE ？）

2026-3-15

• P15795 【MX-J25-T2】「Cfz Round 8」Update Problem

  • 极端数据考虑（很大，很小，接近化归的情况，比如这题我把 $n$ 先 $\times-1$ 后多次 $+1$ 化成 $0$ 处理，但实际上 $|n|$ 较小时先 $+1$ 后 $\times-1$ 更优）

• P15796 【MX-J25-T3】「Cfz Round 8」Juice Problem

  • 开始是一个暴力模拟，就是按题意一个一个倒，溢出用取 $\min$ 处理，复杂度 $O(nq)$ , 70pts
  • 然后优化：合并 $\min$ 里面的公共部分，不用每次现取 $\min$ ，而是先前缀和（ $s[i]=\sum\limits_{i=1}^n b[i]$ ）出所有可能值，然后取 $\min$，即求 $\min\{b[0]+s[p],a[i]+s[p]-s[i]\}$ ，但复杂度依然是 $O(nq)$
  • 后来发现提取一个 $s[p]$ 就可以将题目化为求 $s[p]+\min\{b[0],a[i]-s[i]\}$ ，后者用前缀最小预处理，复杂度优化至 $O(n+q)$

2026-3-14

• P1241 括号序列

  • 如果栈是空的，取栈顶会 RE
  • 然后似乎不需要 replace，直接输出就行了

• P2234 [HNOI2002] 营业额统计

  • 学习 set（STL 大法好）

2026-3-12

• P2058 [NOIP 2016 普及组] 海港
  • 过于路径依赖，去重直接 map，然后并没有处理好
  • 实际上是维护一个动态的窗口，于是用队列

2026-03-11

• P1433 吃奶酪

  • 第一道状压 DP（也许）！
  • 似乎是经典问题（Traveling Salesman Problem, TSP）简化版（
  • 搜索用普通剪枝过不了（这里 $N$ 比较小，然后似乎感觉 DP 的时间复杂度确定一些？因为递归还要考虑栈）
  • 用 memset 的时候注意 memset 是按字节赋值的， double 赋值有bug

• P1596 [USACO10OCT] Lake Counting S

  • 这是什么Flood Fill 问题来着，求连通分量个数
  • 然后我用 BFS 写入队没标记重复入队爆队列 RE 了（也没用循环队列）
  • 似乎 DFS 更直观？
  • BFS 结尾神秘 \n 导致 10pts WA

• P1032 [NOIP 2002 提高组] 字串变换（疑似错题）

  • 第一次（？）用 STL
  • 学习 queue，map，包括 string 标准库
  • 用 map 是为了去重，原来 MLE 了甚至
  • map 的键似乎应具有可比性（结构体：… ）

• P1825 [USACO11OPEN] Corn Maze S

  • BFS 也要记得去重，不然反复入队也可能 TLE
  • 感觉去重的同时可以 DP ？
  • 预处理传送门可以三维数组（

• P3613 【深基15.例2】寄包柜

  • 稀疏数组，还得是 STL

2025-8 - 2026-2

之前记在洛谷上

任何一个伟大的思想，都有一个微不足道的开始。

• P5707 【深基2.例12】上学迟到 这是自己不hack的问题，只用样例，测评数据倒是挺到位的

• P5709 【深基2.习6】Apples Prologue / 苹果和虫子 又是没hack（确实太懒了），总结一些hack点：边界条件（越界和卡界），除法取整问题。 。

• P1980 [NOIP 2013 普及组] 计数问题 float精度不够，不开double见祖宗。 。

• P1914 小书童——凯撒密码 ASCII码只有128个。 。

• P1321 单词覆盖还原 题解区做法好哇，覆盖并没有改变什么，只是变得更好输入了

• P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two 做完看了看题解，发现有佬用农夫与牛的状态处理判断重复，很多用6维数组，最妙的一个是用农夫与牛的位置加权得到专属值，%%%

• P1098 [NOIP 2007 提高组] 字符串的展开 模拟题就该模拟，不要乱改写题意（比如反面的条件），一定要考虑边界情况！

• P1786 帮贡排序 当冒泡排序练习，两次排序多关键字，注意储存初始相对顺序

• P14972 『GTOI - 2C』Fliping 比赛题，错在n-2与n-1需要交换时没有特殊考虑，40pts

• P1249 最大乘积 对上界估计方面仍需严谨，当n较大误差也会很大

• P1088 [NOIP 2004 普及组] 火星人 似乎考虑 $M\le100$ 就以为只要后六位全排列，还是能有数据hack掉的。考虑剪枝全排列dfs或者直接next_permutation唔。然后似乎有康托尔展开的背景（原来是火星人）

• P1928 外星密码 递归但是只能处理最先出现的一些括号套，还得遍历。考虑一个一个字符读入会比字符串方便一些（？），找数字至少不用分类讨论。

• P1164 小A点菜 似乎是01背包，实测dfs剪枝+记忆化才能AC

• P3612 [USACO17JAN] Secret Cow Code S 一个分治，呃，卡了我两天（awa，后面又是各种细节出错，且没开long long，基础不扎实……感觉这道题可能是从正面考虑，按照题中延长 $s$ 的顺序来要方便一些，我从 $N$ 入手，结果就……了。看了题解发现就是这个位置好像本来就是字符串反转再平移了一下而已（

• P1498 南蛮图腾 要用数组！！！（卡了好久是因为想直接输出）看到有一个异或递推的（杨辉三角模2发现）的题解，感觉有点接近本质？

• P1803 凌乱的yyy / 线段覆盖 贪心。但是我是考虑优先选和其他比赛重叠最少的（可能不完全正确而且还TLE），而题解给出的做法普遍是优先选结束时间最早的（可以留更多时间去参加后面的比赛）。

• P1106 删数问题 一开始考虑删去比后一个数大的数这个贪心，然后发现这个删数有多轮，可能第一轮就把答案里的数删了。后来改进每轮只删一个数（我还不怎么用STL），这就等价于 $k=1$ 的情形，又忘记前导 0 。最后改了前导 0 ，发现还有一个答案就是 0 的点。呃…… 然后看题解，有可以选 $n-k$ 个数的，每次选第一位，设还要删 $m$ 个数，那这个第一位必然在前 $m+1$ 个数中产生，这样甚至可以边找边输出。orz 。然后，这似乎又是一个 RMQ 问题，有时间复杂度更优的算法，涉及一些数据结构之类的，之后学习一下，挖个坑（

• P5019 [NOIP 2018 提高组] 铺设道路 感觉很多贪心题都值得好好想一想，比如这个我感觉自己虽然一遍过了但是是一个递归的模拟，看了题解就有 $O(n)$ 的做法，每次两个坑填下去， $ans+=a[i]-a[i-1](a[i]>a[i-1])$。因为题目只关心次数（结果），而不是其中的过程，那么并没有必要模拟，就是你一个一个坑填过去，然后如果后面的坑更浅或一样就顺便填了，如果更深还要花费次数再去填。

• P4447 [AHOI2018初中组] 分组 看到队列标签才想到用队列的（虽然只有用到及时出队降低时间复杂度），我是维护一个分组人数及实力最强者，然后更强的依次入队。题解区还有俄罗斯方块图形化（但确实很有道理）……有一个维护单调性并且使用二分查找的可能比我这个效率高（好像确实欸，一般人看到什么最少的最大就直接二分了）

• P1080 [NOIP 2012 提高组] 国王游戏 邻项交换法似乎不是 $i$ 和 $i+1$ 项交换的意思

• P3853 [TJOI2007] 路标设置 二等分不一定最优（

• P2895 [USACO08FEB] Meteor Shower S 标记有无的桶就直接用bool吧，，，不然会 MLE

• P1019 [NOIP 2000 提高组] 单词接龙（疑似错题） 似乎s.length()返回无符号数，然后如果和有符号的-1比较，-1会被转化为有符号数

咕咕咕