OI填坑指南

普通的坑

  • 数据没有读入
    尤其是n

  • 数组没有初始化
    vis数组没有初始化,dp数组没有初始化,上一组数据的答案数组没有清空

  • 数组初始化不正确
    vis初始化为0,邻接矩阵初始化为INF,dp数组起始点初始化不正确

  • 数据溢出
    中间结果溢出(尤其是组合数、完全图运算),int与long long计算导致溢出

  • 输出格式不正确
    多组输出,没有换行;大小写

  • 死循环
    搜索时vis数组设置不正确或没有判断vis,环形链表,图上BFS/DFS遇到环

  • 强退
    内存非法操作,数组越界(务必小心,有时候本地测试少量数据可能不报错,交上去就爆零了),除以0,对0求余,STL爆栈,爆队列

  • 位运算符错误(2018.3.2加)
    &&,||,是用来判断多个条件的。
    只有&,|,~,^才是位运算。 尤其是&&和&,||和|,容易搞混,错了还找不到…..

  • 错误最大值
    初始化数组成INF常使用 memset(a, 0x3f, sizeof(a)); ,但是0x3f只能在memset中使用。0x3f并不是最大值,0x3f=67,若直接赋值 tmin = 0x3f; 会出错。

  • 倍增时log值开错(2018.4.2加)
    普通倍增、树上倍增时,log值的顶为 (log(n)/log(2))+1 ,直接写logn会变成log(10)n,漏+1会在极其极端的数据下无法抵达倍增最远点。

  • 分块、倍增二维数组大小(2018.4.2加)
    分块数组的第二维大小是根号n,而倍增数组的第二维大小是log(n)。倍增若开成根号n会爆内存,导致MLE。

  • DFS/BFS时对重边和自环的处理(2018.4.3加)
    用图论算法贴模板时,有重边和自环对结果影响不大,因为这些算法已经考虑了上述情况。但是自己写DFS/BFS等传(bao)统(li)算法的时候,是无法自动处理重边自环的,因此递归函数中一定要加入对此的处理,不然样例能过然后爆零(隐蔽错误+1)

  • 树链剖分时的top判断(2018.4.3加)
    注意是判断 depth[top[x]]-depth[top[y]],光比较xy节点的深度没有意义,应按xy所处的树链顶部节点深度决定先处理x还是y。

  • 树链剖分时的线段树建树(2018.4.3加)
    注意是按剖分完成后第二次dfs的dfs序建树,因此init函数赋值是node[node_id]=a[dfn[l]],查询时使用query(dfn[top[x]], dfn[x], 1, 1, n),同时注意dfn[top[x]]应在dfn[x]前面,因为其dfs序更小。

天坑

原标题:细数OI里WA了一百遍还会继续踩的天坑

之前总结了一篇OI里常见WA原因,久而久之练习多了,这些问题大都不会再犯。

可是OI里总是有些天坑,踩了一遍又是一遍,活活拉低AC率!回头调试时,才发现这些错误已经不知是犯了几次了….

以下内容都是我用数十数百次的WA经验总结出来的:

  • 无向图、有向图区分
    一般接受输入数据时,都会定义并使用一个add_edge的函数进行加边操作。但是这个函数执行一次,添加的是一条有向边!!!! 如是无向图,则需颠倒from和to节点添加反向边!!! 太容易漏了!
    后果:不能遍历图,导致大量漏解、WA,严重者可爆零!
    我的踩坑次数:>=20

  • 多组数据间 数组、变量清零
    又一个天坑。样例数据给的少,不清零出错概率小。因此这是一个 隐藏属性很高 的坑!解决办法很简单,能定义局部变量的就用局部变量,可自动销毁。不能定义的(空间太大的数组),把程序开头所有数组都清零,无论是否需要!
    并且千万注意堆、栈、vector的清零,更容易遗忘, 隐藏属性更高!
    后果:所有包含多组数据的测试点WA
    我的踩坑次数:>=5

未完待续….
(2018/4/3更新)