基础冬令营 暂别

「

基础冬令营

Basic winter camp

」

为了提高计算机学院学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力，俞教授于1月12日在信息楼A101开展了为期8天的寒假ACM集训，并邀请了ACM亚洲区导师吴永辉老师前来讲解，参加集训的有TS、蜘蛛人的团队成员及部分学院学生。

在本次冬令营过程中，采用了上午授课，下午和晚上进行实践的方式对同学们进行训练。吴永辉老师在集训期间，上午依次为大家讲解了基本编程能力、线性表、树、图、最佳路径算法以及状态空间搜索初步等。在吴老师授课过程中，大家都饱以充足的热情投入其中，聚精会神的听着吴老师的讲授。而在下午、晚上的比赛训练中，同学们也丝毫没有懈怠，不断地结合吴老师上课讲授的知识及题目的例题进行解题，展现了宁夏理工学子积极向上的精神风貌。

去年6月，在宁夏理工学院成功举办ACM-ICPC国际程序设计技术大赛。冬令营主要针对ningli大赛讲学和训练，讲授要点，各个击破；同学们有了训练的基础，继续基于基础知识，安排各自的解题操练。

1月12日:历练基本编程能力（I）

简单计算、简单模拟。程序设计是技术。正因为程序设计是技术，所以，程序设计、数据结构、算法这样的课程不是听会的，也不是看会的，而是练会的，是在编程实践的过程中逐步掌握通过编程解决实际问题的能力。

1月13日：历练基本编程能力（II）

所谓计算题，指的是在“输入-处理-输出”的模式中，“处理”这一环节所涉及的运算规则比较浅显，编程训练的重心放在如何正确地处理输入和输出，以及优化计算上。

主讲：递归与回溯；线性表；数组应用

1月14日：线性表（I）

数组:是存储于一个连续存储空间中的、并且具有相同数据类型的数据元素的集合，是一种定长的线性表。

字符串：是一种以字符为元素的线性表，具有线性表的有限性、有序性、均匀性的特性；线性表可以为空，字符串也可以是空串。

栈：是一种只允许在表头存取数据的线性表，在表的顶端插入数据元素，而且也只能从表的顶端移出数据元素。

1月15日：线性表（II）

哈希表和哈希方法、:哈希表是一种通过关键码（key）进行索引的广义类线性表。 在记录（或表项）的存储位置address与它的关键码key之间建立一个对应的函数关系address=hash(key)，使得每个关键码与结构中的一个存储位置相对应。查找记录时，首先计算address=hash(key)，并在结构中取address位置的记录。若关键码相同，则搜索成功。存储记录时也同样计算address=hash(key)，并将记录存入address位置。这种方法称为哈希方法，在哈希方法中使用的函数称为哈希函数（亦称散列函数）。按照此方法构造出来的表或结构称为哈希表（亦称散列表）。

STL:STL(Standard Template Library，标准模版库)是C++标准程序库的核心，它封装了许多数据结构和算法，包括排序功能。

1月16日：树（I）

树的遍历：按照一定的规律不重复地访问（或取出节点中的信息，或对节点作其它的处理）树中的每一个节点，其遍历过程实质上是将树的非线性结构按一定的规律转化为线性结构。

并查集：在一些应用中，需要把n个不同元素划分成不相交的若干组，每一组的元素构成一个集合，由于这类问题主要涉及对集合的合并和查找，因此称为并查集。

1月17日：树（II）

二叉树：二叉树和普通的树一样，也是一个无回路的连通图，树中任意节点至根的路径有且仅有一条。

二叉堆：二叉堆（heap）是一棵满足下列性质的完全二叉树；如果某结点有孩子，则根结点的值都小于孩子结点的值，我们称之为小根堆。 如果某结点有孩子，则根结点的值都大于孩子结点的值，我们称之为大根堆。

哈夫曼树：在具有n个带权叶结点的二叉树中，第k个叶结点的权值为wk；其到根的路径长度为pk，则wk*pk为第k个叶结点的带权路径长度（1≤k≤n）。使所有叶结点的带权路径长度之和为最小的二叉树称为哈夫曼树。

1月18日：图（I）

图的遍历（BFS、DFS）：从图的某一节点出发，访问图的所有节点，每个节点被访问一次且仅被访问一次，这一访问过程被称为图的遍历。

最小生成树（Kruskal算法、Prim算法）：

Kruskal算法：初始时，森林由n个节点组成的n棵树； ▸然后，反复找出森林中连结任意两棵树的所有边中具有最小权值的边(u, v)作为安全边，把它添加到森林中，直至产生最小生成树为止。

Prim算法：初始时，A为空； ▸设r为出发节点；节点i是生成树外的节点，且d[i]为节点i与生成树相连的最短边长，简称节点i的距离值； ▸所有不在树中的节点按照d值递增的顺序组成一个优先队列Q； ▸接下来每次添加到A的边都是使得树的权尽可能小的边，这个过程一直进行到生成树产生为止。

1月19日:图（II）

最佳路径算法（Warshall算法、Floyd-Warshall算法），状态空间搜索初步

典

型

例

题

小孩报数问题

有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。

通过吴老师淳淳的教诲和同学们不断的实践，大家在本次集训都收获到了许多，在创新、团队协作以及强压力下的工作能力都取得了很大的进步，希望同学们在未来的学习道路上，能够保持这种ACM精神，不忘初心，砥砺前行，方能实现自己的梦想！

不关注

就捣蛋

长按上方二维码，关注“蜘蛛人”