错误集

发表于 | 更新于 | 分类于
本文字数： 1.8k

从今天开始，把自己平常刷题时出现的各种sb错误记录下来，以免再犯。

2019.5.2-洛谷P3398-仓鼠找sugar

众所周知，倍增求lca时需要用到一个存储父亲及祖先编号的数组。把$dp[100100][21]$写成了$dp[100100][20]$导致数组访问越界，喜提WA0分。

2019.5-洛谷P3369-【模板】普通平衡树

写kth时把赋值语句搞错了顺序，导致WA。

错误代码:

1
2
x = rson;
k -= splaytree[lson].size + splaytree[x].cnt;

正确代码:

1
2
k -= splaytree[lson].size + splaytree[x].cnt;
x = rson;

2019.5.18-洛谷P3391-【模板】文艺平衡树

无论搞什么操作，多加点特判，比如查询第$k$大时判断一下根结点的$size$值是否大于等于$k$，等等。

2019.6.22-洛谷P3868-[TJOI2009]猜数字

不开longlong见祖宗。函数参数把$long long$写成了$int$导致爆$int$。

2019.7.5-洛谷P2152-[SDOI2009]SuperGCD

写高精减法漏了个加号。

1
x.data[i] = data[i] - a.data[i];

1
x.data[i] += data[i] - a.data[i];

2019.7.5-洛谷P1967-货车运输

写倍增$lca$忘了特判$x=y$的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
int lca(int x, int y) {
    int ans = 0x3fffffff;
    if (depth[x] < depth[y]) swap(x, y);
    for (int i = 20; i >= 0 && depth[x] != depth[y]; i--)
        if (depth[dp[x][i]] && depth[dp[x][i]] >= depth[y]) ans = min(ans, mindis[x][i]), x = dp[x][i];
    for (int i = 20; i >= 0 && dp[x][0] != dp[y][0]; i--) {
        if (dp[x][i] != dp[y][i]) {
            ans = min(ans, min(mindis[x][i], mindis[y][i]));
            x = dp[x][i], y = dp[y][i];
        }
    }
    return min(ans, min(mindis[x][0], mindis[y][0]));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lca(int x, int y) {
    int ans = 0x3fffffff;
    if (depth[x] < depth[y]) swap(x, y);
    for (int i = 20; i >= 0 && depth[x] != depth[y]; i--)
        if (depth[dp[x][i]] && depth[dp[x][i]] >= depth[y]) ans = min(ans, mindis[x][i]), x = dp[x][i];
    if (x == y) return ans;
    for (int i = 20; i >= 0 && dp[x][0] != dp[y][0]; i--) {
        if (dp[x][i] != dp[y][i]) {
            ans = min(ans, min(mindis[x][i], mindis[y][i]));
            x = dp[x][i], y = dp[y][i];
        }
    }
    return min(ans, min(mindis[x][0], mindis[y][0]));
}