ACM 模板/思路整理

ACM 思路&模板

鸽子要开始卷了!!

鸽子鸽子了。。。

周末一定补一点呜呜呜

隔壁dag已经组好队了

对拍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <cstdlib>
int main()
{
int n=10000;
for(int i=1;i<=n;i++)
{
system("./data");
system("./Dew");
system("./bf");
if(system("diff Dew.out bf.out"))
{
printf("wrong in test %d\n",i);
break;
}
printf("ok in test %d\n",i);
}
return 0;
}

动态规划

背包

区间dp

树形dp(换根)

环形dp

数位dp

动态dp

状压dp

插头dp

斜率/四边形不等式优化



数据结构

链表

栈/队列/堆/ST表

树状数组/线段树

  1. 线段树

    展开

    【模板】线段树 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    #include <cstdio>
    #define ll long long
    #define ls id<<1
    #define rs id<<1|1
    const int N=1e5+10;
    ll sum[N<<2],tag[N<<2],a[N];
    void build(int id,int l,int r)
    {
    if(l==r) {sum[id]=a[l];return;}
    int mid=l+r>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    sum[id]=sum[ls]+sum[rs];
    }
    void pushdown(int id,int l,int r)
    {
    if(tag[id])
    {
    int mid=l+r>>1;
    sum[ls]+=tag[id]*(mid+1-l);
    sum[rs]+=tag[id]*(r-mid);
    tag[ls]+=tag[id];
    tag[rs]+=tag[id];
    tag[id]=0;
    }
    }
    void change(int id,int l,int r,int L,int R,ll k)
    {
    if(l==L&&r==R)
    {
    sum[id]+=k*(r+1-l);
    tag[id]+=k;
    return;
    }
    pushdown(id,L,R);
    int Mid=L+R>>1;
    if(r<=Mid) change(ls,l,r,L,Mid,k);
    else if(l>Mid) change(rs,l,r,Mid+1,R,k);
    else change(ls,l,Mid,L,Mid,k),change(rs,Mid+1,r,Mid+1,R,k);
    sum[id]=sum[ls]+sum[rs];
    }
    ll query(int id,int l,int r,int L,int R)
    {
    if(l==L&&r==R) return sum[id];
    pushdown(id,L,R);
    int Mid=L+R>>1;
    if(r<=Mid) return query(ls,l,r,L,Mid);
    else if(l>Mid) return query(rs,l,r,Mid+1,R);
    else return query(ls,l,Mid,L,Mid)+query(rs,Mid+1,r,Mid+1,R);
    }
    int main()
    {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
    int op,l,r;ll k;
    scanf("%d%d%d",&op,&l,&r);
    if(op==1)
    {
    scanf("%lld",&k);
    change(1,l,r,1,n,k);
    }
    else
    printf("%lld\n",query(1,l,r,1,n));
    }
    return 0;
    }

平衡树

  1. 无旋转treap

    展开
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    #include <cstdio>
    #include <cstdlib>
    const int N=1e5+10;
    int root,ch[N][2],siz[N],dat[N],val[N],tot;
    #define ls ch[now][0]
    #define rs ch[now][1]
    void updata(int now){siz[now]=siz[ls]+siz[rs]+1;}
    void split(int now,int k,int &x,int &y)
    {
    if(!now){x=y=0;return;}
    if(dat[now]<=k)
    x=now,split(rs,k,rs,y);
    else
    y=now,split(ls,k,x,ls);
    updata(now);
    }
    int Merge(int x,int y)
    {
    if(!x||!y) return x+y;
    if(val[x]<val[y])
    {
    ch[x][1]=Merge(ch[x][1],y);
    updata(x);
    return x;
    }
    else
    {
    ch[y][0]=Merge(x,ch[y][0]);
    updata(y);
    return y;
    }
    }
    int New(int k)
    {
    val[++tot]=rand(),siz[tot]=1,dat[tot]=k;
    return tot;
    }
    void Insert(int k)
    {
    int x,y;
    split(root,k,x,y);
    root=Merge(x,Merge(New(k),y));
    }
    void extrack(int k)
    {
    int x,y,z;
    split(root,k,x,y);
    split(x,k-1,x,z);
    z=Merge(ch[z][0],ch[z][1]);
    root=Merge(x,Merge(z,y));
    }
    int Rank(int now,int k)//排名为k
    {
    if(siz[ls]>=k) return Rank(ls,k);
    else if(siz[ls]+1<k) return Rank(rs,k-siz[ls]-1);
    else return dat[now];
    }
    int frank(int now,int k)//k的排名
    {
    if(!now) return 1;
    if(dat[now]>=k) return frank(ls,k);
    else return frank(rs,k)+siz[ls]+1;
    }
    int main()
    {
    int n;scanf("%d",&n);
    for(int op,x,i=1;i<=n;i++)
    {
    scanf("%d%d",&op,&x);
    if(op==1) Insert(x);
    else if(op==2) extrack(x);
    else if(op==3) printf("%d\n",frank(root,x));
    else if(op==4) printf("%d\n",Rank(root,x));
    else if(op==5) printf("%d\n",Rank(root,frank(root,x)-1));
    else printf("%d\n",Rank(root,frank(root,x+1)));
    }
    return 0;
    }
  2. splay

  3. 替罪羊

    展开
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    #include <cstdio>
    #define ls ch[now][0]
    #define rs ch[now][1]
    const int N=1e5+10;
    double alpha=0.7;
    int valit[N],siz[N],exist[N],ch[N][2],dat[N],tot,q[N<<4],l=1,r=0,s[N],cnt,root;
    #define bad (siz[now]*alpha<(double)(siz[ls])||siz[now]*alpha<(double)(siz[rs]))
    #define updata siz[now]=siz[ls]+siz[rs]+1,valit[now]=valit[ls]+valit[rs]+exist[now]
    int New(){return l<=r?q[l++]:++tot;}
    void del(int now){q[++r]=now;}
    void dfs(int now)
    {
    if(!now) return;
    dfs(ls);
    if(exist[now])s[++cnt]=dat[now];
    del(now);
    dfs(rs);
    }
    void build(int &now,int l,int r)
    {
    if(l>r){now=0;return;}
    now=New();
    int mid=l+r>>1;
    dat[now]=s[mid];
    exist[now]=1;
    build(ls,l,mid-1),build(rs,mid+1,r);
    updata;
    }
    void rebuild(int &now)
    {
    cnt=0;dfs(now);
    build(now,1,cnt);
    }
    void Insert(int &now,int k)
    {
    if(!now)
    {
    now=New();
    exist[now]=valit[now]=siz[now]=1;
    dat[now]=k;ls=rs=0;
    return;
    }
    ++siz[now],++valit[now];
    if(dat[now]>=k) Insert(ls,k);
    else Insert(rs,k);
    if(bad) rebuild(now);
    }
    int kth(int now,int k)
    {
    if(!now) return 1;
    if(dat[now]>=k) return kth(ls,k);
    else return kth(rs,k)+valit[ls]+exist[now];
    }
    void extrack(int now,int k)
    {
    --valit[now];
    if(k<=valit[ls]) extrack(ls,k);
    else if(k>valit[ls]+exist[now]) extrack(rs,k-valit[ls]-exist[now]);
    else --exist[now];
    }
    int fkth(int now,int k)
    {
    if(k<=valit[ls]) return fkth(ls,k);
    else if(k>valit[ls]+exist[now]) return fkth(rs,k-valit[ls]-exist[now]);
    else return dat[now];
    }
    int main()
    {
    int n;scanf("%d",&n);
    for(int opt,x,i=1;i<=n;i++)
    {
    scanf("%d%d",&opt,&x);
    if(opt==1) Insert(root,x);
    else if(opt==2) extrack(root,kth(root,x));
    else if(opt==3) printf("%d\n",kth(root,x));
    else if(opt==4) printf("%d\n",fkth(root,x));
    else if(opt==5) printf("%d\n",fkth(root,kth(root,x)-1));
    else printf("%d\n",fkth(root,kth(root,x+1)));
    }
    return 0;
    }

可持久化

  1. 主席树
  2. 并查集

LCT

kd-tree

启发式合并

  1. 左偏树
  2. 线段树
  3. 平衡树


图论

最短路

2-sat

分层图

生成树/重构树

仙人掌/圆方树

欧拉路

DAG

连通分量(tarjan)、割点/边

图的匹配

网络流

  1. 最大流/最小割
  2. 费用流
  3. 上下界

  1. LCA
  2. 笛卡尔树
  3. 点分治/动态点分治
  4. 链分治/动态链分治
  5. 虚树
  6. 树分块
  7. 树的直径


字符串

AC 自动机

KMP

manacher

tire 树

SA/SAM

PAM



数学

数论基础知识

  1. 费马欧拉
  2. 数论分块

数论进阶知识

  1. 反演
    • 二项式
    • 单位根
    • 莫比乌斯
    • 卡特兰数
    • 斯特林数
  2. CRT 相关
  3. 容斥原理
  4. BSGS
  5. 生成函数

卷积相关知识

  1. 狄利克雷卷积相关知识
  2. FWT等

线代相关知识

  1. 高斯消元
  2. 矩阵树定理
  3. 线性递推

筛法

  1. 线性筛/欧拉筛
  2. 杜教筛
  3. 洲阁筛/min25筛

概率期望

博弈

群论

计算几何

凸包

半平面交

旋转卡壳



独立板子/思想

分治

  1. CDQ 分治
  2. 整体二分
  3. 二进制分组
  4. 线段树分治

贪心/模拟费用流

补集转换

(高阶)差分

打表

离线

随机化

逆波兰表达式

bitset

Hash

倍增

分块

莫队/带修莫队

哈夫曼树

线性基

扫描线

  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 Dew
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信