ACM 模板/思路整理

算法竞赛
Word count: 1.7k   |   Reading time≈ 9 min

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. 数
    • 卡特兰数
    • 斯特林数
  3. CRT 相关
  4. 容斥原理
  5. BSGS
  6. 生成函数

卷积相关知识

  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:

请我喝杯咖啡吧~

支付宝
微信