西南大学蓝桥杯参赛选手集训计划
本计划由西南大学ACM实验室制定并执行，仅为参加蓝桥杯大赛的选手准备，非强制计划，参赛选手自行选择是否跟随训练。
概览
计划分为四周，从2021年3月27日开始
第一周
- C++基础巩固
- 语法与结构
- 结构体、指针、数组
- 基础数据结构
- 蓝桥杯做题技巧
- 递归、什么时候使用递归
- IO优化，快速读写
- 吸氧(打开编译器$O_2$优化)
- 分治、什么时候使用分治
- 打表法，骗分法，暴搜法
- 如何做填空题
- Excel、Python的高级运用
- RE、TLE、MLE的常见解决思路
- STL(C++ Strandrad Template Library)的使用【重点】
- 数据结构(vector, stack, queue, set, map)
- 算法(string, cstdlib, sort)
- 简单数据结构
- 模拟【重点】
- 穷举
- 进制转换
- 高精度
第二周
对于ACM实验室的大一成员而言，本周留有作业，请在本周日前完成并提交。
- 数据结构算法【重点】
- 最小生成树(Kruskal算法、Prim算法)
- 并查集(路径压缩)
- 拓扑排序(AOE网、AOV网)
- 最短路(Dijkstra算法、Floyd算法)
- 强连通分量(Tarjon算法、Kosaraju算法、Gabow算法)
- 搜索【重点】
- 深度优先搜索、广度优先搜索
- 记忆化搜索、路径回溯、剪枝
- 数学与数论【难点、拉分点】
- 素数与素数理论，费马定理、欧拉公式
- 筛法求素数
- 同余，剩余类、剩余类域、剩余类环
- 快速幂、矩阵快速幂
- 组合数学，排列组合，容斥原理
- 概率论、博弈论、线性代数、高精度、进制转换
第三周
- 贪心
- 计算几何【难点】
- 动态规划【难点】
第四周
- 蓝桥杯真题练习与评讲
详情
第一周
1. C++基础巩固
这一部分建议同学们自己搞定，需要完全掌握的至少有：
- 动态开辟二维数组
- 掌握指针与引用的使用
- 了解并掌握递归函数的设计与实现
- 了解结构体与结构体内存控制
- 掌握基本输入输出操作
- 了解数组、链表、树、图等基本数据结构的性质与其实现
2. 蓝桥杯做题技巧
这一部分由2019级计算机科学4班-陈羿羽同学讲解，主要内容包括：
- 递归的使用技巧
- 什么是递归，怎么写一个递归函数
- 什么时候应该使用递归
- 递归与循环的转换
- 递归的常见使用情景
- IO优化，快速读写
- iostream与cstdio的异同
- iostream如何关闭流同步与关闭流同步可能出现的问题
- 快速读入与快速输出的使用场景
- 快速读入与快速输出的实现(模版)
- 吸氧
- 什么是吸氧，吸氧的等级与用处
- 怎么手动吸氧
- 分治(后文有专题详解)
- 什么是分治思想
- 萌新有三法：打表暴搜和骗分
- 三大法的使用场景
- 三大法的使用示范
- 填空题的解题方法
- 使用数学方法解题
- 揣测出题人想法，大胆猜想题目规律
- 只要心态不滑坡，办法总比困难多(人力计算法)
- 三大法(上文已讲)
- Python大法好(见下文)
- Excel的高级使用(见下文)
- 常见模版要背好(素数、日期、进制…)
- Excel与Python的高级使用
- 灵活应用Excel计算日期
- 灵活应用Python进行数学运算、字符串搜索、日期计算
- RE/TLE/MLE的常见解决思路
- RE: Runtime Error，即运行时错误。出现的最多的场景为数组越界，其次可能的场景为除数为0，栈溢出，指针越界，程序抛出异常。
- TLE: Time Limit Exceeded，即程序超时。出现最多的场景是深度优先搜索剪枝不完整，其次是出现了死循环(包括出口递归)，程序本身复杂度过高。
- MLE: Memory Limit Exceeded，即程序超内存。一般不会出现此情形，可能的场景为开辟数组过大，动态规划未优化内存。
3. STL的使用【重点】
这一部分请同学们阅读文档。如果有不懂的可以自己先动手试一下，还有疑惑的话就开issue询问。
可以参考的资料有：
4. 简单数据结构
这一部分请同学们自己搞定，需要完全掌握的有：
- 了解并掌握数组、链表、树、图的性质与定义
- 掌握树的四序(先序、后序、中序、层序)遍历
- 掌握图的搜索(深度优先、广度优先)
- 熟悉各数据结构的常见使用场景
可以参考的资料有：
- 数据结构 - 西南大学：熊海灵教授(需要校园网IP)
- 数据结构 - 青岛大学：王卓
- 数据结构 - OI-Wiki【适合提高选手阅读】
5. 模拟【重点】
这一部分由2019级计算机科学3班-吴银杰(吴大佬是国一大佬喔)同学讲解，主要内容有：
- 模拟练习
- 如何理清题意
- 如何跟着题目写代码
第二周
第二周再写，start仓库到时再看就行了
其他
重要链接
- 蓝桥杯真题
- 蓝桥杯练习系统
- 西南大学SOJ练习平台(需要校园网IP)
若提示证书安全问题，请选择”高级选项”并点击”继续访问”，这是因为我们的网络安全证书暂未更新，我们将在ACM实验室搬迁后进行服务器维护，届时我们会解决这一问题。 - 直播课录屏
- 集训课程直播间
贡献
- 感谢西南大学商贸学院ACM实验室提供在线训练系统
- 感谢信息管理与信息系统系杜治国主任对本次集训的支持与帮助
- 感谢ACM实验室的现役队员为本次集训的策划与执行做出的贡献，同时感谢退役、预退役队员为本次集训提供的意见与支持