消耗战合集

只计算编写代码和调试时间。

P2086 [NOI2012]魔幻棋盘

耗时:5h

原因:

  1. 写树套树试图代替二维线段树写挂(卡在单点修改不会写)放弃。
  2. 边界判断处理不当(命名可以从0开始避开一切bug,却傻乎乎从2开始)
  3. 没有处理负的gcd
  4. (c) 没有开long long;query没有开long long;gcd[]没有开long long;(res) 没有开long long;不敢define int long long
  5. (gcd)(g) 重复定义,交叉使用
  6. 一维线段树查询处把 (m) 写成 (n)
  7. 四分树query的时候将 (D) 写成 (R)
  8. (arr) 数组没有清空。
  9. 测试数据不算很弱,但不好造较强的数据(对拍时怎么拍两个的答案都是全1)

P3511 [POI2010]MOS-Bridges

耗时:3h(掺杂看题解的时间)

原因:

  1. 傻乎乎地连了个:addedge(u, v, 1), addedge(u, v, 0) 然而实际应该是 addedge(u, v, 1), addedge(v, u, 0)

  2. 不会快速找欧拉回路。首先上百度搜,方法看起来都不太一样,甚至还有和“桥”有关系的。然后看洛谷题解,题解里说:出题人应该没有毒到卡欧拉回路的求法,那么我们随机打乱边再 DFS 就完事了,并且给了个 random_shuffle 的代码,然后我就高高兴兴地去写了个暴力DFS+random_shuffle,然后交了三次都TLE了。然后又上网学,版本不一,并且找不到一篇好博客,随便拿了一个博客的方法半信半疑的写好交上去,结果WA+RE。最后凭借着之前TLE的90分看别人的AC代码,最后才过。可见网上会有一些恶毒的题解,不可全部相信啊

P2305 [NOI2014]购票(点分治做法)

耗时:约3.5h

原因:

  1. 没有看懂题解,于是晚上睡觉的时候自己瞎想了一个做法,比较复杂,过来实现了半个小时发现想假放弃。多谢zzy大佬的指导让我少走了不少弯路。

  2. Siz -= siz[] 写错位置导致无限死循环。

  3. get_dis的时候没写 if (vis)... 导致复杂度爆炸。

  4. 斜率优化没有清空凸包的栈。

  5. nw != fa[anc] 写成 nw != anc,导致少考虑了祖先。

  6. 二分凸包判断方向写反。

  7. 二分凸包未考虑到 mid == 1 而右边还有其它可能更优的决策点的特殊情况。

P5385 [Cnoi2019]须臾幻境

(硬生生把 170 行左右的代码写到了四百七十多行,估计能赶上 substring 了。)

耗时:3.5h

原因:

  1. pushup 中只对“边”点进行了初始化,并没有给“点”点初始化为 (infty)。(这个调了两个小时)

  2. fa[son[cur][flag ^ 1]] = faa;faa 写成了 cur

  3. Access没有 (splay(p))

  4. 强制在线应该 %m 却写成了 %n。(感谢机房大佬yxt的提醒)

  5. (根本原因)尝试在 LCT 内部使用输出调试,却只静态查错查了两遍

P3920 [WC2014]紫荆花之恋

耗时:4.5h

原因:

  1. 删除替罪羊树重构部分的时候忘记删除 stk[++stop] = ...,导致一直 RE。

  2. work 函数忘记连点分树上的边。

  3. work函数忘记将新建的点的 (vis) 设为 (true)

  4. work函数忘记初始化点分树子树大小

  5. 重构函数中忘记将原先的“根”重构。

  6. 重构函数中没有特判 (faa) 为0时的新根的 dian_fa 的情况。

  7. 重构函数中连边情况搞乱

  8. 点分治时计算 (f2) 时算出 (Rt)(f2),却传给了 (cur)

  9. 解决问题 8 的时候将 (Rt) 写成了 (to)

  10. 拍扁重新点分治的时候忘记在点分树上连边。

  11. 解决问题 10 的时候将 (cur -> Rt) 写成了 (cur -> to)

  12. 拍扁的删除操作中没有将 (rt1, rt2) 置零,导致下次仍然能正常调用。

  • 总结:

有的时候先写暴力的外层框架,再写比较难的部分(比如这道题先不重构,再只进行替罪羊树的重构,再写点分树的重构),在保证前面写的那些暴力框架不出错的前提下,调试后面的时候就不用怎么担心前面的部分会不会出错了。

静态查错是调数据结构的常用方法,但是有的时候对拍小数据调错也是不错的选择。

Continued...

原文地址:https://www.cnblogs.com/JiaZP/p/13281821.html