复习
2025-08-11 09:47:44
发布于：浙江
1阅读
0回复
0点赞
复习
DAY1
1、模拟: 按照题目意思实现代码, 考察代码的基本功
2、贪心算法
求解问题: 最大值/最小值等。
思想：每一步做当前“看起来最优”的选择，希望得到全局最优。
如果能举出反例, 说明贪心策略错误
3、时间复杂度的分析
DAY2
二分查找
三种需要掌握的查找方式:
1、找x的下标
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] == x) return mid;
else if (a[mid] < x) l = mid + 1;
else r = mid - 1;
}
return -1;
2、找第一个>=x的下标
int l = 1, r = n, ans = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] >= x) { ans = mid; r = mid - 1; }
else l = mid + 1;
}
return ans;
3、找第一个>x的下标
int l = 1, r = n, ans = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] > x) { ans = mid; r = mid - 1; }
else l = mid + 1;
}
return ans;
4、系统函数的使用 (lower_bound,upper_bound)
// 对于数组a 区间 [1,n] 查找第一个>=x的数的下标
lower_bound(a+1,a+n+1,x)-a;
// 对于数组a 区间 [1,n] 查找第一个>x的数的下标
upper_bound(a+1,a+n+1,x)-a;
5、注意：要是用二分查找，必须先排序
DAY3
二分答案
对于答案需存在单调性：设 check(x) 表示“答案取 x 是否可行”，则 x 越大或越小时可行性应单调。
// [l,r]表示答案的范围
int l = 1;
int r = 1e9;
int ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) { // check函数检查答案为mid的情况下.....
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans;
DAY4
进制转化
前中后缀表达式
原码、反码、补码
位运算
排列组合
DAY5
动态规划
求方案数
求最大值/最小值
可行性问题
建模四问（核心）
- 状态定义：f[i][...] 表示“前 i 个/到 i 点、附加维度 ... 的最优值/可行性/方案数”。
- 转移关系：从更小状态到更大状态的公式或枚举。
- 初始化：边界；不可达置为 -INF/INF/0。
- 答案位置：是 f[n] / f[n][*] / max(min)
DAY6
栈 stack<T> ：后进先出（LIFO），只允许在栈顶操作。
常用成员：`push(x)`、`pop()`、`top()`、`empty()`、`size()`。
- 复杂度：入栈/出栈/取顶均均摊 O(1)。
队列 queue<T>：先进先出（FIFO），从队尾入，从队头出。
常用成员：`push(x)`、`pop()`、`front()`、`back()`、`empty()`、`size()`。
- 复杂度：入队/出队/取首/取尾均均摊 O(1)。
DAY7
树与图基础概念
图（Graph）
元素：顶点（V）与边（E）。无向图/有向图；可带权/不带权；简单图（无自环、无重边）。
度：无向图的度；有向图的入度/出度。
树（Tree）
定义：连通且无环的无向图。性质：|E| = |V| − 1；任意两点间路径唯一；加入任一新边必成环。
根与层次：根树（Rooted Tree）定义父/子/兄弟/祖先/后代/叶子；深度（root 到该点边数）、高度（子树最大深度）。
二叉树：每个结点度 ≤ 2；满二叉树、完全二叉树；遍历：先/中/后序与层序。
DAY8
深度优先搜索
深度优先搜索（Depth-First Search, DFS）是一种遍历图或树的算法，遵循“尽可能深入再回溯”的策略：从某个起点出发，沿着未访问的邻接点一路向前，直到无法前进时返回上一层继续探索。它可用递归或显式栈实现，必须对节点做已访问标记以避免重复和环
伪代码
void dfs(int u) {
// enter u
for () {
dfs();
}
// exit u
}
DAY9
步骤（广度优先搜索 BFS）
1、起点入队并标记已访问（距离置 0）。
2、取出队头 u。枚举 u 的所有邻点 v：若 v 未访问，则标记访问、入队。
3、重复第2步，直到队列为空
// S是起点
queue<int> q;
vis[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
// 处理 u
for (遍历u的邻居v) {
if (!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
这里空空如也
有帮助，赞一个