【No.2】蓝桥杯暴力求解与高频考点
·
暴力求解方法
- ACM赛制
没有部分分，有没有过所有的测试数据，
不断的提交，实时得到你代码的反馈 - OI赛制
有部分分，过了几个测试点，有多少分
最终只能提交一次，一锤子买卖
为了保证没有语法错误，在当地的编译器跑一下代码，看看能不能过测试用例，自己在造几个数据，再看看能不能的到想要的结果，可以的话再去提交
- 关键在于有部分分
拿到全部的分数可能很难，拿到部分的分数是很简单的
如果蓝桥杯的一套题，8个编程题，有一两道题拿到全部分数，其他题目用最简单的方法拿部分分，最终成绩会不错
面对一道蓝桥杯的题目
- 先想暴力做法（时间复杂度较高的做法），拿到部分分数
- 根据数据范围判断正确的时间复杂度，根据时间复杂度确定出这道题的算法范围
暴力做法
- 模拟题干中的过程
数据范围是10^5，大概率是nlogn
- 二分，堆…
高频算法考点
-
基础算法
前缀和、二分、差分
DP
搜索（BFS、DFS）
图论（最短路、最小生成树）
数据结构（STL） -
在不同数据范围下，代码的时间复杂度和算法该如何选择
-
n
≤
30
n \le 30
n≤30,
指数级别, dfs+剪枝，状态压缩dp -
n
≤
100
n \le 100
n≤100 =>
O
(
n
3
)
O(n^3)
O(n3)，
floyd，dp，高斯消元 -
n
≤
1000
n \le 1000
n≤1000 =>
O
(
n
2
)
O(n^2)
O(n2)，
O
(
n
2
l
o
g
n
)
O(n^2logn)
O(n2logn)，
dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford -
n
≤
10000
n \le 10000
n≤10000 =>
O
(
n
∗
n
)
O(n * \sqrt n)
O(n∗n)，
块状链表、分块、莫队 -
n
≤
100000
n \le 100000
n≤100000 =>
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) =>
各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树 -
n
≤
1000000
n \le 1000000
n≤1000000 =>
O
(
n
)
O(n)
O(n), 以及常数较小的
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 算法 =>
单调队列、 hash、双指针扫描、BFS、并查集，kmp、AC自动机，常数比较小的 O ( n l o g n ) O(nlogn) O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa -
n
≤
10000000
n \le 10000000
n≤10000000 =>
O
(
n
)
O(n)
O(n)，
双指针扫描、kmp、AC自动机、线性筛素数 -
n
≤
1
0
9
n \le 10^9
n≤109 =>
O
(
n
)
O(\sqrt n)
O(n)，
判断质数 -
n
≤
1
0
18
n \le 10^{18}
n≤1018 =>
O
(
l
o
g
n
)
O(logn)
O(logn)，
最大公约数，快速幂，数位DP -
n
≤
1
0
1000
n \le 10^{1000}
n≤101000 =>
O
(
(
l
o
g
n
)
2
)
O((logn)^2)
O((logn)2)，
高精度加减乘除 -
n
≤
1
0
100000
n \le 10^{100000}
n≤10100000 =>
O
(
l
o
g
k
×
l
o
g
l
o
g
k
)
，
k
表示位数
O(logk \times loglogk)，k表示位数
O(logk×loglogk)，k表示位数，
高精度加减、FFT/NTT
-
n
≤
30
n \le 30
n≤30,
高频知识点
- 二分
- 前缀和
- 差分
- 双指针
- 归并排序
- 多路归并
- 贡献法
- 日期问题
- 区间合并
- 递归
- DFS
- 剪枝
- BFS
- Flood Fill
- 并查集
- 哈希表
- 单调队列
- 树状数组
- 状态压缩DP
- 线性DP
- 背包问题
- 区间DP
- 树形DP
- 快速幂
- 最大公约数
- 分解质因数
- 矩阵乘法
- 组合计数
- 数学期望
- 欧拉函数
- 最短路
- 贪心
- 括号序列
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
17
0- 0
已为社区贡献1条内容
所有评论(0)