多么痛的领悟!

多么痛的领悟!记录一下做题时犯的一些错误。

错误:多次调用 strlen 导致超时。

来源P5357 【模板】AC自动机(二次加强版)

分析:strlen 的时间复杂度为 O(n)O(n),因为它是通过循环来求它的长度,因此像下面一样

for(re int i = 0, u = 0;  i < strlen(s);  ++i) {
       u = ac[u].s[s[i] - 'a' + 1];
       ++siz[u];
}

时间复杂度就是 O(n2)O(n^2) 的。

解决方法:用个变量存一下长度,避免反复调用。

int len = strlen(s);
for(re int i = 0, u = 0;  i < len;  ++i) {
       u = ac[u].s[s[i] - 'a' + 1];
       ++siz[u];
}

错误:在更新一些数值的时候(比如 dp 转移时)因为开始给数值赋过值,所以在更新时不能直接写 ==,而要写 +=+=

来源P2922 [USACO08DEC]Secret Message G


错误:在减法取模时出现负数。

来源:2021.7.21 模拟赛 T1,10070100 \leftarrow 70

解决方法:以后取模时候出现减法的话一定要加上模数,一定!以防万一。


错误:一道题有想法时自以为过不了,结果就没打。

来源:AtCoder Beginner Contest 208。

解决方法:以后有想法了一定要去打,就算真的过不了也可以当作暴力。


错误:记忆化搜索时记忆化数组初始化为 00,导致 TLE。

来源:6.2 模拟赛

分析:在搜索中 00 也是一种结果,而记忆化时将两者混为一类,导致大量的重复计算。

解决方法:初始化为一个永远选不到的值,比如 1-1


错误:堆优化 dijstra 重载运算符时应为

bool operator< (const node &x) const {
    return dis > x.dis;
}

结果写成了

bool operator< (const node &x) const {
    return dis < x.dis;
}

就 TLE 了。

分析:其实我也不知道。

2021.7.222021.7.22 更新:据 shy 哥说,这是因为 STL 内部的比较规则导致的,比较玄学。


错误:重载运算符时没有注意变量顺序,前后弄反了,结果爆蛋了。

来源P3216 [HNOI2011]数学作业


错误:floyd 中间点没有放在最外面枚举。

来源P1850 [NOIP2016 提高组] 换教室

分析:因为在 floyd 中边权会改变。


错误:把 == 打成 =

来源:2021.5.4 模拟赛(直接丢失 100 分,一定要注意)。


错误:定义一个 string 类型的变量时没给它分配空间,出现 UB。

来源P2730 [USACO3.2]魔板 Magic Squares

解决方法:给变量分配空间,如 string ans = "......."