多么痛的领悟!
多么痛的领悟!记录一下做题时犯的一些错误。
错误:多次调用 strlen 导致超时。
分析:strlen 的时间复杂度为 ,因为它是通过循环来求它的长度,因此像下面一样
for(re int i = 0, u = 0; i < strlen(s); ++i) {
u = ac[u].s[s[i] - 'a' + 1];
++siz[u];
}
时间复杂度就是 的。
解决方法:用个变量存一下长度,避免反复调用。
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,。
解决方法:以后取模时候出现减法的话一定要加上模数,一定!以防万一。
错误:一道题有想法时自以为过不了,结果就没打。
来源:AtCoder Beginner Contest 208。
解决方法:以后有想法了一定要去打,就算真的过不了也可以当作暴力。
错误:记忆化搜索时记忆化数组初始化为 ,导致 TLE。
来源:6.2 模拟赛
分析:在搜索中 也是一种结果,而记忆化时将两者混为一类,导致大量的重复计算。
解决方法:初始化为一个永远选不到的值,比如 。
错误:堆优化 dijstra 重载运算符时应为
bool operator< (const node &x) const {
return dis > x.dis;
}
结果写成了
bool operator< (const node &x) const {
return dis < x.dis;
}
就 TLE 了。
分析:其实我也不知道。
更新:据 shy 哥说,这是因为 STL 内部的比较规则导致的,比较玄学。
错误:重载运算符时没有注意变量顺序,前后弄反了,结果爆蛋了。
错误:floyd 中间点没有放在最外面枚举。
分析:因为在 floyd 中边权会改变。
错误:把 ==
打成 =
。
来源:2021.5.4 模拟赛(直接丢失 100 分,一定要注意)。
错误:定义一个 string
类型的变量时没给它分配空间,出现 UB。
来源:P2730 [USACO3.2]魔板 Magic Squares
解决方法:给变量分配空间,如 string ans = "......."
。