当前位置：首页 > news >正文

常见错误及细小知识点锦集

news 来源：原创 2024/5/19 14:47:59

考场策略

1、别把子串看成子序列！！

2、千万千万别把模数看错！

3、在bash中用<a.in读入的话在程序中不能开文件！

4、打比赛的时候每个题都要重写const int maxn = xxx

5、看清输出格式，不要在题目要求输出3个数的时候输出两个数

6、样例玩不出来一定是自己算错了！考虑用最无脑的方法算，再算不出来重读题目

7、数组大小！！！

8、注意排序的时候greater<int>()是否应该写为greater<LL>() 比较隐蔽。

数据结构

LCT

splay只有该点的父亲节点不是根节点的时候才转两次

    for(int y = fa(x); !IsRoot(x); rotate(x), y = fa(x))
        if(!IsRoot(y))//注意 
            rotate( ident(x) == ident(y) ? y : x );

access的时候需要将节点转到全局的根，所以循环边界为x==0

而splay的时候只要转到当前根就可以了

  access：  for(int y = 0; x; x = fa(y = x))

 splay： for(int y = fa(x); !IsRoot(x); rotate(x), y = fa(x))

FFT

while(limit <= N + M) limit <<= 1, L++;

for(int R = mid << 1, j = 0; j < N; j += R) {//这里要写<N

这里一定要取等号，$N$表示了一个长度为$N+1$的多项式，因此乘起来的多项式的最高次项为$N+M$，共有$N+M+1$位

ST表

int Query(int l, int r) {
    int k = Log[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);//不要写成f[r - k + 1] 
}

圆方树

圆方树求一个点跳到环上的位置时

    int las;
    while(top[x] != top[lca]) las = top[x], x = fa[top[x]];//las = top[x] not x
    return x == lca ? las : point[dfn[lca] + 1];//这里要写lca

CDQ分治

    while(tl <= mid || tr <= r) {
        if((tr > r) || (tl <= mid && a[tl].x < a[tr].x)) st[++tot] = a[tl++];//这里要加上tl <= mid 
        else st[++tot] = a[tr++];
    }

字符串

后缀自动机

    int now = ++tot, pre = last; last = now;//这里不要把last重新int一遍

if(len[pre] + 1 == len[q]) fa[now] = q;
//注意这里和下面都不能写fa[ns] = pre，因为q的父亲不一定是pre，q的len应当是一段区间[x, y]，它父亲节点的len的最大值为x-1，而且per节点的len为y-1 
else {
    int ns = ++tot; fa[ns] = fa[q]; len[ns] = len[pre] + 1;
    memcpy(ch[ns], ch[q], sizeof(ch[q]));
    fa[q] = fa[now] = ns;
    for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = ns;
}