Hello World!

为什么又要水一篇踩坑总结呢？

写这篇文章的缘由是我整理luogu/vijos评测记录时发现，有相当一部分的爆零代码根本不是算法写错了啊！都是一些小细节上的失误。然而NOIP并不会管你是不会还是失误，爆零就是爆零。因此有必要做一份交代码前的Checklist，以免你的代码变成 WA/CE/RE自动机 （逃）

NOIp结束前10分钟强烈建议停止写题，认真地核对此检查表。

1. 程序文件名，后缀（.cpp），文件夹路径是否全部正确
2. freopen文件输入输出是否全部打开，输入输出文件名是否正确
3. 调试输出是否全部关闭
4. 数组大小是否合适，满足题目要求并留有余量
5. 头文件是否全部包含且正确
   • windows下专用头文件是否已去除
   • 有些考场不让用的头文件（不如ctime）是否已经去除
   • 某些很容易漏的头文件：用了memset就要包含cstring，用了rand就要包含cstdlib
   • windows上测试，不包含头文件是可以编译通过的，Linux评测机上会爆零
6. 输出格式是否正确
   • Yes/No 或其他英文字符串的大小写是否正确
   • 数据分割方式是换行还是空格
7. 题目有多组数据的，检查每组数据间：
   • 全局变量是否清空
   • 栈、队列、vector是否清空
8. 变量、函数命名是否有重复、重复定义，临时变量所用ijkt是否定义过全局变量。有没有踩C++关键字
9. 检查数据类型，是否存在double/int计算，long long/int计算，或会溢出的计算。这些问题隐藏属性较高。
   • int*int 会溢出，建议用long long
   • abs、sqrt等数学函数返回double，因此不要直接 % 或与int计算。
10. 有条件切换linux的，去Linux评测一下。因linux对于内存泄漏管理严格，任何越界会强退，避免隐藏错误。

作为平衡BST里最简单的版本，Treap光是模板的难度就已经超过了提高+，达到了 省选 （luogu上的紫色标签）。但是NOIP去年还真的考了一题！因此有必要认真的学习一下。（这也是大学CS数据结构课的标配，早晚要学，不如现在学掉）。

本蒟蒻敲这个模板花了一个小时，调bug又花了半个小时。感谢lyd的算法竞赛进阶指南，他的代码是我唯一看得懂的一个treap版本。网上那些用指针实现的，阅读并不容易而且溢出调试麻烦….

原理不说了，出门右拐百度百科。https://baike.baidu.com/item/Treap/4321536

这里只列举一下写treap时易错的点。并且根据我的洛谷WA记录，treap一错那多半是大量RE， 很容易爆零 ，所以下面的坑一定要避而远之哦！

Treap易错点

1. 初始化时添加最小点和最大点，他们之间的关系容易写错。
2. 插入操作时最后需要维护当前节点的附加信息，如子树个数等，容易遗忘。
3. root节点在初始化时需要额外手动指定，容易遗漏。
4. 函数名如new、insert、update等注意不要踩C++编译器关键字。
5. 查前驱后继时，找到并更新答案（左走到底和右走到底）应应时刻判断当前节点p为空的情况：进入while之前设置if判断是否存在左/右节点以便进入while；在while中判断tn[p].l/r是否存在，而不是判断p是否存在。后者会造成越界访问不存在的虚拟节点0，造成答案错误。
6. 任何对treap的修改（插入、修改、删除、旋转）都要执行update命令，并且注意update顺序：先update儿子节点，再update当前节点。
7. 对treap的修改、递归执行时，定义函数时把当前节点的传参设为引用。否则会导致更新失败。
8. 删除操作时判断左旋还是右旋，左旋条件为右子树为空，或者左子节点treap key堆键值比右子节点大。两条件顺序不可颠倒，关系为或。 并且不要写成判断左子树是否存在，那是错的，会导致虚拟节点旋转上树进而造成树的断裂。
9. 按排名查找值和按值查找排名时，注意treap初始化时无穷大和无穷小节点的影响。为去除这两个节点的影响，输入排名时应+1，按值找到排名时应-1.

以下给出一份AC代码，对应

luogu上的treap模板题
https://www.luogu.org/problemnew/show/P3369

bzoj上的模板题
http://www.lydsy.com/JudgeOnline/problem.php?id=3224

请展开阅读

最近题目刷了不少，从普及/提高-，刷到提高+/省选-，最大的感触就是别把题目搞复杂了。就算是BZOJ里的省选题目，很水的签到题还一抓一大把。这种题目有了思路5分钟写完代码（这不是废话么），但是想复杂了反而想不到思路，因此总结一下常见思考路径，不应看到省选题就从难得开始想、本末倒置。

关于DP

能贪心的不要DP，能暴搜的也不要DP，暴搜会超时的先想状压DP，状压DP不行的再想普通DP。想出主体思路前先别想优化。优化和思路一起想出来了，也先把不带优化的程序敲敲对，保证主体思路正确后再想办法优化。

关于图论

先想办法DFS/BFS暴力求解，不行尝试预处理，Tarjan缩点、LCA初始化、入度出度计算，再想处理算法。毕竟树或DAG可比带着环内环的原始图好处理吧…

关于二分

碰到题先想二分！！！碰到题先想二分！！！碰到题先想二分！！！重要的事情说三遍，因为二分太强大了。只要答案有单调性、二分大概率行得通！！写个判断函数总比写全局最优搜索简单吧！！可以解决很多想不出其他算法的题目！！

未完待续
（2018/4/3编辑）

普通的坑

• 数据没有读入
  尤其是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更新）

Every line of code is a breakthrough of myself.

SAM, originally launched in 2014, was a campus homework platform built for students and teachers. From the time (Sept. 2016) I joined the Computerization, I have been working on its updates, bringing new functions to it. Last Semester, I worked with Jedi and used the whole semester on the new User Interface of old SAM. Eventually, we finished the project in June, just before the end of the semester. Although SAM looked very different from previous one, still few students and teachers used it. A collaboration system with a so small scope seems no longer in demand.