学到✏️

基础算法

模拟, 贪心, 枚举, 二分, 前缀和, 差分, 分治, 离散化, 搜索, 尺取法(双指针)

• 贪心: 要多想, 多动手推一下🧐

• 二分: 换一种思路, 枚举答案或者某种限制, 注意答案需要具有某种性质(一般为单调性), 答案位于此性质成立与不成立的分界点, 分界处有且只有一个

• 搜索: 贪心不成立, 无明显可验证的性质时可以进行搜索, 深搜记得搜完恢复起始状态

基础数据结构

顺序表, 链表, 栈, 队列, 树与二叉树, 堆/优先队列, stl容器与算法, 并查集, 树状数组, st表......

要清楚什么情况用什么数据结构, 各种数据结构增删改查的复杂度是多少

• 单调栈/单调队列: 容器中元素时刻保持有序(新增元素如果使其无序就删先进入的, 删到有序), 由于单调性, 被删除的元素不可能作为答案

• 树: 树的基本术语, 二叉树的性质, 特殊二叉树及性质, 二叉树的三种遍历方式

• stl容器及算法: 看文档, 记得拼写和初始化方式, 注意时间和空间复杂度

• 并查集: 重要, 路径压缩, 按秩和并, 扩展域并查集(更多关系)和带权并查集(权值维护)

• 树状数组: 重要, 维护前缀和, 预处理为$O(nlongn)$, 改查时间复杂度均为$O(logn)$

• st表: 主要解决RMQ(Range Maximum/Minimum Query) 问题, 使用倍增思想, $O(nlongn)$预处理, $O(1)$查询,st[i][j]代表从$i$开始$2^j$长度的区间的最大值，即区间$[i, i + 2^j − 1]$的最大值, 主要记预处理, 查询, 注意性质是否可由重叠区间求得

基础动态规划

难且重要🥲, 线性dp, 区间dp, 背包dp, 状压dp, 概率dp......

动态规划不是某种特定的算法, 而是一种解决特定问题的方法, 要理解其概念及思想

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法

动态规划的思想是将一个问题划分为若干子问题进行求解, 动态规划的实现方法大致也可以分为递推法和递归法

做题时要先能看出来要用动规求解

各种dp都需要经验积累, 多做题吧😢

图论

DFS, BFS, 树与图的深度/广度优先遍历, 拓扑排序, Dijkstra, bellman-ford, spfa, Floyd, Prim

要时常复习, 别忘了, 多练几次就熟了, 记得各种算法的应用场景和时间复杂度

数学知识

质数, 约数, 欧拉函数, 快速幂

同上, 几天不看就忘差不多了

还有分数求模, 模运算非常重要, 还有位运算

犯过的错误⚠️

• 一定要手推一遍样例, 确定理解正确题意再开始写题 不要再写完看到样例有个对不上, 发现看错题了😭

• 变量名不要重复使用, 容易弄混还找不出错来

• unordered_map和unordered_set会被卡😅, 能用map和set就用

• stl容器的size方法返回类型为size_t, 同unsigned long long, 尽量不要对其进行减法, 否则可能会数据溢出导致卡循环re

• 使用单独的\n换行时要使用单引号, 否则可能出现未知错误

• 注意数据范围, 别爆int或数组开小了

• 多组测试数据时记得全局变量初始化

• 函数内变量如果只有增量操作记得初始化时赋值

• 改类型时记得把改函数的返回类型, 要不然会隐式转换

• 数字默认时int类型, 需加ll后缀变为long long类型, 同理, 小数默认double类型, 需加l后缀变为long double类型

• 不要进行小数判等, 会有误差, 应使用abs(a - b) <= eps等方法

• 遍历容器时不要边遍历边删元素, 如果非要这么做的话建议使用迭代器控制访问

技巧💡

如果有的话记得选择c++17开O2优化

滚动数组可以使用stl容器如vector的swap, 效率$O(1)$👍

输入时若变量名与全局变量冲突时可以在for初始化语句中定义变量, 如:

vector<int> p;
void solve() {
    for (int i = 1, p; i <= n; i++) {
      cin >> p;
      ::p.push_back(p);
    }
}

pair装不下的也可以用tuple:

tuple<int, int, string> t;
get<0>(t) = 0;
get<1>(t) = 1;
get<2>(t) = "hello"s;

正无穷可以用0x3f3f3f3f, 负无穷可用0xcfcfcfcf

中位数最值可二分答案后二值化求解

其他

要补题, 写总结

得多练, 时常复习

比赛🏆

寒假集训 个人赛

场次	排名	AC	罚时
01	11	7/11	255
02	28	6/11	310
03	19	7/11	509
04	10	9/11	420

codeforces

Codeforces Round 996 (Div. 2)

• 分数 2758
• AC 3/6
• 评级变化 1375 -> 1528

Codeforces Round 997 (Div. 2)

• 分数 2369
• AC 3/6
• 评级变化 1528 -> 1499

atcoder

ABC388

• 分数: 1000
• AC: 4/7
• 罚时: 33:25

ABC389

• 分数: 950
• AC: 4/7
• 罚时: 36:21

---