ICPC铜牌算法

铜牌算法

2021ICPC上海站

铜牌开题:

D:数学思维构造
E:贪心思维
G:树形dp
H:图论克鲁斯卡尔重构树
I:背包dp
K:思维构造

2021ICPC沈阳站

铜牌开题:

B:并查集
E:字符串简单查找
F:字符串简单构造模拟
J:BFS预处理

2021ICPC南京站

铜牌开题:

A:思维
C:暴力均摊stl
D:贪心暴力模拟
H:树形dp
M:思维

2021ICPC济南站

铜牌开题:

C:组合数贪心
D:三分法差分数组
J:高斯消元
K:模拟DFS

2021ICPC昆明

铜牌开题：

H:傻逼签到
I:简单计算几何
J:贪心思维构造
K:麻将大模拟
L:树状数组/线段树
M:主席树

2021CCPC桂林

铜牌开题

A:傻逼签到
D:字符串思维贪心
E:Dijkstra
G:贪心/dp
I:思维优化

2021CCPC广州

铜牌开题

I:思维找规律
C:数论构造
H:二分答案

2021CCPC

任务分配

1:英语
2:字符串
3:动态规划
4:数据结构
5:图论
6:数论
7:计算几何
8:杂项

算法范围

字符串

基础字符串
c++字符串库函数
字符串hash
KMP
字典树
EXKMP
AC自动机(会用模板即可，可以先跳过)
后缀数组(同上)

动态规划

贪心算法
记忆化搜索
背包DP
    01背包
    完全背包
    多重背包
    二进制优化背包
区间dp
环形dp
DAG上dp
树形dp
状态压缩dp
dp优化
    单调队列单调栈
    斜率优化
    四边形不等式优化

数据结构

c++基础STL库
栈
队列
链表
hash表
并查集
带权并查集
堆
块状数据结构
    分块暴力均摊
单调队列单调栈
ST表
树状数组
线段树
主席树
树链剖分
区间操作
简单莫队(在线离线)
二维莫队(在线离线)

图论

基本概念
存储
DFS与BFS
LCA
矩阵树定理
DAG
拓扑排序
最小生成树
    克鲁斯卡尔
    普利姆
最短路
    dijkstra
    floyd
    spfa
次短路
差分约束
割点与桥
环
    Tarjan
二分图
    匈牙利算法
    KM算法
最小环

数论

组合数学
    生成函数
    简单排列组合模型
    排列组合计算公式及恒等式
    LGV引理
    群论
        置换群计数
概率论
    简单概率计算
    简单期望计算
    简单概率dp
基础数论
    gcd
    exgcd
    剩余系
    欧拉定理/费马小定理
    CRT
    exCRT
    同余方程
    逆元
简单数学
    常用数列求和公式
    递推转通项公式
    方程/函数求解
    函数最值
    泰勒展开式
    洛必达定理
    求导与积分

计算几何

高中简单几何知识
积分求面积法
基础方法
    点积
    叉积
二维几何:
    点
    线
    多边形
    圆
三维几何
    点
    线
    面
凸包
极角排序
最小圆覆盖
线段交问题（扫描线法）
跨立实验
点在内部问题
半平面交

杂项

搜索
    BFS
    DFS
    及以上剪枝优化
    二分查找/答案
    三分查找/答案
随机化算法
    乱搞
    模拟退火
大模拟
思维构造

英语

具有能读清楚题的能力即可，建议六级550+