做题常见错误

记录亿些神奇的错误

警钟敲烂

关于链式前向星

用了链式前向星的题的最后几个点TLE/MLE/RE等等非常神奇的错误，一般都是链式前向星数组开小了！

有多个图时最好把Edge封装成Graph结构体 (要不然会很乱)

struct Graph {
    struct Edge {
       int from, to, pre; 
       int w;
    } es[maxn];
    int last[maxn], cnt;
   
    inline void addEdge (int u, int v, int w) {
        es[++cnt] = Edge { u, v, last[u], w };
        last[u] = cnt;
    }
   
    inline int from (int i) { return e[i].from; }
    inline int to (int i) { return e[i].to; }
    inline int pre (int i) { return e[i].pre; } 
    inline int w (int i) { return e[i].w; }
};

双向边…

没用的数组别留着

会 MLE 呜呜呜

初始化

一定要初始化
位置不要放错

啊啊啊

而且尽量避免在较大时, 每次都 memset () , 会 TLE /kk

关于树上信息的统计

一般使用dfs

void dfs (int now)
{
    // if (vis[now]) return; // 最好不放在这里
    for (int i = last[now]; i ; i = pre[i])
    {
        int t = to[i];
        if (vis[t]) continue;

        /* ... 树上信息统计(自上而下) ... */

        dfs (t);

        /* ... 树上信息统计(自下而上) ... */       
    }   
}

用vis判断是否是父亲时要把它放在for循环中int t = to[i];的后面而不是新的一遍递归的开始

十年OI一场空, 不开long long见祖宗

2023.07.09 22:29 at QBXT SC 有幸见了两次祖宗

改ll要改全!!

upd: 现在已经改成类似jiangly的写法 i64

P2891 Dining

我认为这题必须单独拿出来当典型

同时犯两个有关返回值毒瘤错误调了2天晚上大概6h, 我真的…

返回值竟然被搞成了, 呵呵
返回值缩进写错了, 竟然每遍for都要return, 呵呵呵呵呵呵

if / for / while后面不要加分号

这都什么毒瘤错误啊!!!!!

多测?!!

清空

离散化

用vector离散化的话

正确写法是

inline void descrete () {
    vector <int> temp;
    for (int i = 1; i <= n; i++) {
        temp.push_back (a[i].s);
        temp.push_back (a[i].t);
    }
    sort (temp.begin (), temp.end ());
    m = unique (temp.begin (), temp.end ()) - temp.begin();

    for (int i = 1; i <= n; i++) {
        a[i].s = lower_bound (temp.begin (), temp.begin() + m, a[i].s) - temp.begin() + 1;
        a[i].t = lower_bound (temp.begin (), temp.begin() + m, a[i].t) - temp.begin() + 1;
    }
}

注意是temp.begin() + m

~~所以还是别用了罢~~

upd:

原来我不会 std::vector 离散化

正确的方法是:

1	vals.erase (std::unique (vals.begin (), vals.end ()), vals.end ());

取模取模取模

别把看成

!!! !!!

upd 2025.7.16 我咋这个时候还忘 pushdown

要用儿子结点的信息的时候必须先 pushDown

也就是说, 线段树 modify() 的时候也要 pushDown()

因为 modify() 了以后要 pushUp()

如果不先 pushDown() , 那么 pushUp() 更新当前节点的信息就会是错的

树剖

关于树剖 , ~~她似了~~ 我死了

能在同一个代码里犯三个不同的树剖错误, 我也是很有实力的

要从开始 (?)

即 dep[1] = 1

注意初始化

每次先 siz[now] = 1

跳链的时候, 比较的应为 `dep[top[u]]` 和 `dep[top[v]]`

而不是 dep[u] 和 dep[v] 这样的复杂度是错的

~~但是为什么这样写又 WA 又 TLE 啊?~~

~~不应该只是 TLE 吗?~~

01-trie

有个人 tr[maxn << 5][2] 开了倍

但是 siz[maxn] 了 (没开倍)

所以这个人给大家的建议是

定义一个 struct , 包括 ch[2] 和 siz 两个属性

位运算优先级

包括但不限于 << , >> , & , |, xor, ^

全部都要加括号来表示优先级 !!!!

upd: 2025.7.17 !!!!!!!!

i64 exgcd (i64 a, i64 b, i64& x, i64& y) {
	if (not b) { x = 1; y = 0; return a; }
	i64 d = exgcd (b, a % b, y, x);
	y -= (a / b) * x;
	// x -= (a / b) * x;
	return d;
}

不要写被注释掉的那一行!!!

调了一晚上

唐

关于快速幂,

我死了。

实在太可怕

在枚举左边的时候需要计算

~~然后我们就直接用快速幂”快速”的把她算出来了~~

~~然后复杂度就比别人多一个 log~~

正确的方法是: 先使用快速幂计算 , 然后发现 , 直接在动态维护即可

Rainbow-Automaton's blog