那些写码5分钟，调试2小时的岁月

其实就是错题集了..不会做或者立马知道怎么错的就不写了，那些WA一整页的，调试一个多小时的……都在这了。 从2018.2.11起（包括前几天做的题），长期更新，按做题时间降序排列 --- [CF1200F](http://codeforces.com/contest/1200/problem/F) RE7，然后发现，`#define int long long` 它爆栈了... --- 输出调试究竟应该用 cerr 还是 cout / printf 呢。 cout 可能忘删就 WA 了。 但 cerr 可能让你不会 WA 只会 TLE，然后盯着自己的代码看一年为什么常数那么大。 总之记得删调试信息... ------------ FFT中 $w_n^i=cos(\frac{2\pi}i)+sin(\frac{2\pi}i) i$，然而如果枚举的 $i$ 是区间长度的一半，就要相应地改成 $w_n^i=cos(\frac\pi i)+sin(\frac\pi i) i$。 ------------ 由于窝一开始看的杜教筛教程（事实上很多杜教筛教程）（事实上很多数论教程都）乱用字母，于是经常把 $g(1)S(n)=\sum\limits_{i=1}^n h(n)-\sum\limits_{d|n}g(d)S(\left\lfloor\frac n d\right\rfloor)$ 中的 $n$ 和题目中的 $n$ 搞混..要注意qwq ------------ 稠密图求全源最短路不要用 dijkstra... ~~Floyd是世界上最优秀的最短路算法，好写常数小，n^3过1000~~ ------------ Splay insert 之后一定要 Splay，不只是复杂度的问题，不Splay就没有上传siz。 ------------  $O(n^2(\frac{2\times10^5}{32}+n))$了解一下。 人要有梦想，memset不能有。（无意冒犯某杭二julao） ------------ noi.ac上sort的重载运算符都要const...一般只有pq要的，但为了保险以后记得用于排序的重载运算符都要const（其实按照工程标准，不修改的所有地方都应该用const..） ------------ P2515 [HAOI2010]软件安装 `有些课程必须在某些课程之前学习` 与 `软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作` 之区别... ------------ P2149 [SDOI2009]Elaxia的路线 搜索最短路dp时没有加vis爆炸... 虽然最短路搜不出环，但可能从不同的分支重复搜到某个点。 （所以说还是尽量判个vis，即使没用也没关系嘛...） ------------ P1896 [SCOI2005]互不侵犯 老年oi选手，把&当|用，脑抽了以为是把1“并”起来..... ------------ 使用`std::priority_queue`要确保无论何时pq内元素进行比较结果相同，即，不能比较dis[x]和dis[y]但在x、y已进入pq时修改dis[x]或dis[y]。 ------------ 今天写了下模板才发现自己之前一直写的假的堆优化dijkstra...要确保每个节点只用于松弛一次。 ------------  ------------ 最近快速幂连着两题把&打成&&...需要注意. ------------ [TC12373开车车](https://bbs.codeaha.com/problem-12373.html) 遇到长相奇怪的最短路不要脑抽用dfs求... ------------ **bool** operator<() ------------ CF1063B Labyrinth 我太菜了，向右走-向左走=横坐标之差都没看出来... 多个限制条件记得看各个条件之间的关系。 ------------ P3916 图的遍历 之前一直用的鬼畜至极的缩点方式..然后今天愉快地WA了一面..貌似正确的缩点姿势是把读入存进来，跑完tarjan之后清空原图，不在同一个scc的连边。 ------------ 膜你赛埃氏筛写错了...................................... 要枚举到 $n$ 而不是 $\sqrt{n}$ ------------ 有时函数不带返回值-Wall都不会警告... ------------ P1903 [国家集训队]数颜色 / 维护队列 ~~因为是第一次写带修莫队~~ 修改时间的函数是进行/回退某次修改，而不是修改至某时间，所以 ```cpp while (now>q[i].t) { modify(i,now--); } ``` 是now--而不是--now ------------ P4014 分配问题 看下面P3381那条...该打！（~~考虑以后树的dfs都把vis写着~~） ------------ P3386 【模板】二分图匹配 Dinic记得 for (i=head[u];i**&&minn-out**;i=nxt[i]) ------------ P3796 【模板】AC自动机（加强版） 多组数据记得cnt=0... ------------ P4305 [JLOI2011]不重复数字 无需排序时用unordered_set比set快得多，几乎和手写哈希一样快。 ------------ P3381 【模板】最小费用最大流 dinic在求最大流的时候因为分层不会重复访问，求最小费用最大流时则可能重复访问，要用vis标记避免重复访问 总结：平时树之类的写多了都不习惯写vis了...除了树或者像求最大流的dinic一样有特殊限制的图，以及像P2279之类需要重复访问的问题，一般的dfs要记得用vis避免重复访问 ------------ P2740 [USACO4.2]草地排水Drainage Ditches [最大流] 虽然感觉是因为初学网络流没理解透以后应该不会再错.. 过了模板题之后直接复制过来然后84，以为是重边的原因，想了半天都觉得EK应该是可以过重边的，后来才发现反向边边权应该为0而不是-w...互为相反数的是流而不是边权。 ------------ 牛客网NOIP赛前集训营-提高组（第一场） A 中位数 直接check i==x不满足二分性时不妨试试check所有的i>=x，必然满足二分性。 ------------ P1629 邮递员送信 堆优化dijkstra是 $O(mlogn)$ 的..稠密图不要用.. ------------ P1032 字串变换 首先恭喜自己终于填上了远古搜索巨坑！（to be finished: css,bxsd） 然后是string::size()的返回值是unsigned，可能会减爆.而且int遇上unsigned会变成unsigned，就是说所有size()都得套上一个int().当然移项变成加号就没有这个问题了。 ------------ P1631 序列合并 IDE内根据编译错误信息就立刻修正了，还是注意一下priority_queue如果重载<参数要const，即类似于： ``` struct T { //XXXXXXXX bool operator<(const T XXX) const { return XXXXXXXXX; } }; priority_queue<T> q; ``` ------------ P3369 【模板】普通平衡树 前一天晚上对着题解愣是把Splay敲出来了，然后对照一看，说我是复制粘贴Ctrl+F的我都没话说... 于是今天试着自己写，Del愉快地忘判cnt>1了....... ------------ 安师大附中膜你赛Day1T2 简单(~~个鬼~~)数据结构 这题我用了很奇妙的算法，在线段树内二分查找，导致即使查询区间覆盖当前区间也可能访问儿子，然后愉快地忘记down了。 以后要记得线段树内只要访问儿子就得down ~~然而这题就算记得加down也炸了~~ ------------ CF1016E Rest In The Shades 当你在CFTLE时，不要慌张，把所有没有必要的long long改成int，long double改成double，endl全部改成\n，快读快输都用上，输出为浮点数时不要忘了还有printf.TM就可以卡常卡过去了 ------------ T39158 大逃亡 神仙错误.......（幸好我交之前用luogu IDE跑了一遍而且代码类型没有选C++11）y0,y1之类的变量会与math.h库冲突，参见[博客](https://blog.csdn.net/changjiale110/article/details/78043531)以及[这个](https://msdn.microsoft.com/en-us/library/h7zkk1bz.aspx) ------------ P1122 最大子树和 鱼唇的我看了讨论才发现前向星数组双向边没有开两倍..这才明白之前dewdalao的一堆<<1..~~反正是刚刚开始用前向星~~错了就是错了！ ------------ 这次并不是错题QwQ 模拟赛的时候被老师提醒了，NOIPfreopen不加cstdio会爆零的... 用了大半年fstream刚改freopen的我被吓到了QAQ ------------ CF 1009C Annoying Present 我果然还是太菜了... 不写precision默认只输出6位有效数字.. 所以即使没让你保留如果精度要求高也要precision %%% 至截图时他还在hack ~~身为LGM每场div2坚持hack100+~~ ------------ P2279 [HNOI2003]消防局的设立 [DFS][贪心] 花式（4种不同的方法）螺旋（WA+RE+TLE）20分 dfs要延伸两格，所以vis==true也不能return。 也是告诉我们如果多种方法都过不了，要注意每次都没有修改的部分。 ------------ P2512 [HAOI2008]糖果传递 这个不算错题，但在最优解中找到了个好东西：nth_element 用法： ``` #include <algorithm> template <class RandomAccessIterator> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); ``` 即：void nth_element(指向开始位置的迭代器l，指向第n大的位置的迭代器nth，指向结束位置的迭代器r) 效果：将[l,r)重新排列，使得*nth为[l,r)中第n大的元素，并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后，但不能保证他们是有序的。 ------------ P3932 浮游大陆的68号岛 [线段树] [前缀和] 取模后大小关系会变，因此可能减法时会出现原本不会出现的负数，要注意加上模数 ------------ P1937 [USACO10MAR]仓配置Barn Allocation [线段树] down忘记下传标记了...服了自己 ------------ P1140 相似基因 [dp] dp时取最大值如果可能出现负数要初始化为-0x7fffffff ------------ T34477 贝茜的飞行路线 [模拟] 读入的过程中不要break..... ------------ Codeforces Round #493 (Div. 2) for语句单句没加分号导致后面的语句被套进去... ------------ Educational Codeforces Round 46 (Rated for Div. 2) >substring必须是原字符串中连续的字符串，而subsequence可以不是。 ------------ Educational Codeforces Round 45 (Rated for Div. 2) 开long long不只是声明变量！！ 少了“1ll*”的我怕不是身为pupil要继续掉rating 这一是告诉我们不仅储存结果的变量要声明为ll，过程中也不能运算溢出；二是告诉我们直接Ctrl+F无脑替换ll有时是有用的，比如这次a数组中的值不可能爆int，但如果我开了ll就不用“1ll*”了 ------------ Avito Code Challenge 2018 打CF千万不要用hash！！！ 就算用hash也一定要随机取模！！！ 血的教训！！！ （每次取模的锅我都会咆哮吗..） ------------ P2323 [HNOI2006]公路修建问题 [最小生成树][二分答案] 这题要二分答案然后输出方案。 日常二分玄学，答案是l+1。 然后没有check(l+1)就WA了。 ------------ P2024 食物链 [带权并查集] 用到取模的题一定每个地方都要取模！！！ ------------ P1821 [USACO07FEB]银牛派对Silver Cow Party && P1828 香甜的黄油 Sweet Butter [SPFA] 两道模板题.. 虽然都是很快就发现了问题，但因为连错两次，所以写在这吧。 用-1标识为不连通时d[起点]一定要初始化为0！！！ 另外一开始忘记判断inq直接入队，虽然A了，但不知道哪题忘了inq就会被卡 ------------ P2023 [AHOI2009]维护序列 [线段树] 18.3.24 几年（雾）没写线段树了.. 各种炸. 首先是down，直接上代码，不记得一开始写成啥了： ``` ll.sum=(ll.sum*cc.ti+cc.ad*(ll.right-ll.left))%p; rr.sum=(rr.sum*cc.ti+cc.ad*(rr.right-rr.left))%p; ll.ti=(ll.ti*cc.ti)%p; ll.ad=(ll.ad*cc.ti+cc.ad)%p; rr.ti=(rr.ti*cc.ti)%p; rr.ad=(rr.ad*cc.ti+cc.ad)%p; cc.ad=0; cc.ti=1; ``` 然后是add，cc.sum=(cc.sum+delta*(cc.right-cc.left))%p;直接写成cc.sum=(cc.sum+delta*(r-l))%p;... ------------ P3390 【模板】矩阵快速幂 18.2.18 很难受，非常难受，一个星期没怎么做题了，上洛谷发现自己橙名，随手做了一道，结果，因为太久没打，写了个memset(a,sizeof(a),0); 凌乱至极 另外还有就是按位快速幂的时候k最大会爆int，一开始1<<kkk，应该1ll<<kkk 总结： memset(地址，数值，内存块大小); 按位计算时如果1<<k会爆int就要1ll<<k P.S.感觉不重载赋值运算符会浅复制..然而A了..赶寒假作业中，有时间再研究研究 ------------ P1967 货车运输 [最大生成树，LCA] 18.2.11 主要是两个大的错误吧 一个是当图不连通时有多个生成树，但只dfs了一次 另一个是LCA的dp循环套反了 总结： 用生成树+LCA求路径问题时，如果有可能不连通，一定要对每个未访问节点dfs LCA的dp:f[i][j]=f[f[i][j-1]][j-1]; 循环一定要把j写在i外面 ------------ P1456 Monkey King [左偏树] 18.2.10 没啥好说的了..就是把总结那句写错了，还检查了半天没检查出来orz 总结： 可并堆（左偏树）合并是s[x].r=merge(s[x].r,y);不是s[x].r=merge(s[x].l,y); ------------ P2380 狗哥采矿 [dp] 18.2.9 错解： for (i=n;i>=1;--i) for (j=m;j>=1;--j) cout<<f[1][1]+max(prea[1][1],preb[1][1])<<endl; 正解： for (i=n;i>=0;--i) for (j=m;j>=0;--j) cout<<f[0][0]<<endl; 像错解那样就默认了左上第一个是单独运的，然而并不一定 总结： dp一般都是直接输出某状态，如果不是一定要三思，仔细想清楚状态表示的意义。有时虽然有的状态的实际意义看起来很奇怪，但算出来的答案是正确的。 ------------ P3377 【模板】左偏树（可并堆） 18.2.9 玄学..至今不知道哪错了..指针WA，多个数组MLE，结构体AC 应该不是写法的问题，而是越写越熟练，之前修改找不到错的地方，最后全部重写就过了吧 以后自己变成大牛了再来仔细看看到底哪里错了 https://www.luogu.org/recordnew/show/5683349 https://www.luogu.org/recordnew/show/5689685 https://www.luogu.org/recordnew/show/5691652 ------------ P3378 【模板】堆 18.2.8 一开始删除的时候没有判断正在往下降的节点是否会越界，最后一次WA是判断反了（i*2>=len） 总结： 堆的删除操作一定要i*2<=len（i为正在下降的节点编号）