【OI学习注意事项】

1. 必备知识

普及组必学

1、模拟算法(暴力枚举),按照题目的要求,题目怎么说就怎么做,保证时间和正确性即可。

2、搜索与回溯,主要的是(DFS)(深度优先搜索)和(BFS)(宽度优先搜索),基本没有直接的暴力搜索。一般是记忆化搜索加剪枝,普及组第三题难度。

3、简单操作:如筛法、前缀和、快速幂、高精度、辗转相除法等,掌握全面即可应对大部分处理数据上的问题。

4、队列(单调队列)、栈、堆、链表等基础数据结构。

5、简单二分和分治(快速排序,归并排序)。

6、贪心,要保证贪心的正确性,如果无法证明也可以用来骗分。

7、数学知识、公式计算,要点在于公式的化简与变形,经过反复操作后也许就能得出重要结论。

8、简单的动态规划,容易推出状态转移方程,要注意初值与计算边界条件。

9、字符串基本操作,插入、删除、查找等。

10、经典例题变形加深:八皇后、马的走法、背包问题等。

提高组必学

0、普及组的(10)条。

1、较难的动态规划,多维的状态,转移方式较多。

2、简单数论,如扩展(GCD),欧拉函数等。

3、进阶算法:倍增,并查集,差分约束、拓扑排序,排列组合数,逆元,哈希。

4、最短路问题,需要掌握弗洛伊德算法、(SPFA)算法、(dijkstra)算法,以及它们对应的优化,再根据题目实际要求进行变形,用同样模板达到各种不一样的效果。

5、最小生成树问题,主要的两种算法为(Prims)(Kruskal),同样要加上对应的优化,再根据题目进行变形,以满足题目的实际要求。

6、二分图染色、二分图匹配,一般题目都隐藏得很深,需要找到题目的本质,才能发现正确的解法。

7、强连通分量(Tarjan),最近公共祖先(LCA)

8、数据结构:线段树、字典树、主席树、树状数组等。

9、树的更多操作:树链剖分、树的直径、树的重心等。

10、字符串操作:(KMP)等。

更多拓展

大部分是省赛内容,如果想NOIP(CSP-J/S)取得好成绩的话,挑一些简单的学习一下吧!

搜索:

启发式搜索((A*)

迭代加深((ID))

(IDA*)

随机化搜索

图论:

网络流

仙人掌算法

树:

平衡树

树套树

圆方树

线段树合并

数学:

容斥原理

莫比乌斯反演

中国剩余定理

欧拉定理

矩阵乘法

(FFT)

博弈论相关

计算几何

字符串:

字符串哈希

(AC)自动机

后缀数组

后缀自动机

回文自动机

(manacher)

共计25大类

高二学长的学习建议

1、尽快学习数学和(DP)

2、要重视网课的题目,找大佬题单

3、不会的题针对数据范围尝试打部分分,不要硬肝正解

4、不要开车,开车劝退

5、(t1)简单不要放过

6、先盲猜算法,尝试硬套

7、洛谷刷题不要点开标签

8、可以去无难度标签等的(OJ)刷题

9、多翻翻大佬博客

10、学习新算法要深一些,不要太快,适当放下脚步

11、高级数据结构不着急

12、考试完要做到考后(300),重视模拟题。对于好的题可以写博客记录

13、要自信

14、博客园的博客比较好

15、一些算法应用很多,如线段树,树状数组等。不能只停留在大板子的水平

16、如果想要进省队,可以多接触外面的人。不要飘,因为优势可能会消失。有了优势不要太高兴。

17、多练习

18、NOIp不会考高级算法,但省选会。刷题量,积累很重要。扩大见过题的概率。

19、可以多做一些思辩题,做自己能力范围内的题

20、训练自己不要犯诸如(freopen)未注释,空间开大的问题。

21、可以进行互测。

原文地址:https://www.cnblogs.com/UssEnterprise/p/12081421.html