ouuan 的博客

ouuan 的博客

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

posted on 2018-02-11 20:40:19 | under 错题集 |

其实就是错题集了..不会做或者立马知道怎么错的就不写了,那些WA一整页的,调试一个多小时的……都在这了。

从2018.2.11起(包括前几天做的题),长期更新,按做题时间降序排列


CF1200F

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开车车

遇到长相奇怪的最短路不要脑抽用dfs求...


bool operator<()


CF1063B Labyrinth

我太菜了,向右走-向左走=横坐标之差都没看出来...

多个限制条件记得看各个条件之间的关系。


P3916 图的遍历

之前一直用的鬼畜至极的缩点方式..然后今天愉快地WA了一面..貌似正确的缩点姿势是把读入存进来,跑完tarjan之后清空原图,不在同一个scc的连边。


膜你赛埃氏筛写错了......................................

要枚举到 $n$ 而不是 $\sqrt{n}$


有时函数不带返回值-Wall都不会警告...


P1903 [国家集训队]数颜色 / 维护队列

因为是第一次写带修莫队

修改时间的函数是进行/回退某次修改,而不是修改至某时间,所以

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库冲突,参见博客以及这个


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为正在下降的节点编号)