在南大转专业到计算机科学与技术系

前言

本文为记录在南京大学转专业到计算机科学与技术系的历程,以及给在南大同样想转专业到计算机科学与技术专业的学弟学妹们分享经验。

本人由于提前批的原因,只能在大二转专业,但转专业考核都是和大一一起的,没什么区别。


前期准备

计算机科学与技术系可谓十分热门,每年基本都是爆满状态,即使报名人数少于分配名额,也会秉持“宁缺毋滥”的原则进行淘汰。并且,转专业考试的难度可以用困难来形容。

因此,如果想要转专业到计算机科学与技术系,要做好充足的前期准备,才能考好这场转专业考试。

首先,是自身的前提条件。如果是零基础的话,我不建议转专业,计科的课程的难度比较大,零基础学习起来比较困难。如果执意要转,肯定是要付出多倍努力的。如果有竞赛基础的话,建议参加ACM-ICPC,拿个牌好应对面试,具体竞赛相关联系马骏老师。

同时,要具备良好的心理素质。在这漫长的两年,会受到各种方面的压力和阻挠,包括但不限于来自老师的劝阻和课业的繁重。

自身前提条件说完就到了具体的课业准备了。

计科的准入要求现在为修读《程序设计基础》或者《计算机构造与解释》,并且修读完大学数学第一层次《微积分I》、《微积分II》和《线性代数》。

《程序设计基础》教学内容为C/C++的基础内容,《计算机构造与解释》教学内容为python的内容和一些Functional programming。零基础我建议只选《程序设计基础》,《计算机构造与解释》难度较大,适合有基础且有兴趣的同学学习。

当然这只是最低要求,转专业考试内容基本不在于此。转专业考试分为笔试、机试、面试三部分,下面就这三部分分别阐述。


笔试

笔试基本内容为微积分和《离散数学》,前几年有《数字电路设计》,不过今年没有了。《离散数学》是重中之重!四道大题有三道大题都是离散数学。一定要在大一下学好《离散数学》,这不仅对笔试有很大帮助,而且能培养良好的计算机思维。

下面来具体描述一下今年笔试的四道大题。

一、\(x \to \infty ,f(x)极限存在且二次可微,f”(x)有界,证明lim_{x \to \infty}f'(x)=0。\)

\(反证法,假设lim_{x \to \infty}f'(x) \neq 0。\)

 

二、证明6元生成的排列群不含有10阶元。

同样也是反证法,假设10阶元存在。由排列群的性质得每个元都可以构造一个图,图由6个点组成,这6个点能形成数个圈,所有圈的长度的最小公倍数即是该元的阶。

将10分解,能得到(1, 5)的圈组和(2, 2, 2)的圈组,但是这两个圈组的最小公倍数分别是5和2,矛盾,所以不存在10阶元。

 

三、\(证明10个顶点40条边的图含有K_{3,3}。\)

\(还是反证法,假设图不含有K_{3, 3}。\)

\(\Delta |V| \geq \Sigma_{v_i \in V} deg(v_i) = 2\times 40=80,得到\Delta \geq 8。\)

再根据这个最大度的顶点构造图应用鸽笼原理就行了。

 

四、\(A、B、C、D、E、F六个集合,D为A到B的映射,E为D \times C,F为A到B \times C的映射,\)

\(证明E和F等势。\)

构造双射或者构造两个单射。


机试

今年机试有3道题,和往年不同,都是有一定难度的,需要具备一定的算法基础并且注重细节。赛制采用OI赛制,可以拿部分分。

Game

题目描述

甲乙两人在一行N行N列的方格棋盘上玩一个小游戏,游戏只有一个棋子,在开始时放在棋盘上的某个格子里。从甲开始,移动这个棋子。每次移动只准在垂直向下,水平向左,沿45度对角线向左下这三个方向中选择一个,但移动的距离不限——只要不出棋盘就可以。

当棋子走到棋盘左下角的格子时,游戏结束,走出最后一步的一方获胜。

在本题中,你将获得棋子最初所在的位置,然后要求你判断甲乙两人中谁获胜(假设双方都足够聪明,能够选择最好的策略)。

输入

第一行包含一个整数T,表示测试用例的组数。

接下来T行,每行代表一个测试用例。每个测试用例包含3个整数n,x,y,其中n表示棋盘的行数和列数,x表示棋子初始位置所在的行数(以棋盘最上方为第1行),y表示棋子初始位置所在的列数(以棋盘最左列为第1列)。

输出

对于每个测试用例,输出一行一个整数:1表示乙获胜,2表示甲获胜。

样例输入

1

6 2 4

样例输出

2

提示

数据范围:

1 <= T <= 100,1 <= x, y <= n,(x, y) != (n, 1),1 <= n <= 1000000

 

很经典的一道博弈论的题目,需要具备基础的博弈论知识,必胜态和必败态的相互转换。

通过打表找规律可以找到对应每一行的必胜态和必败态,用O(n)预处理必胜态和必败态,用O(1)判断即可。

 

简单路径

题目描述

有一个图,含有N个顶点(2<=N<=1000),分别用1、2、……、N来标记。含有M条边(1<=M<=1000),分别用1、2、……、M来标记。已知第i条边的价格为ci(1<=ci<=1000),而它的容量为fi(1<=fi<=1000)。在该图有两个特别的顶点:源顶点1和汇顶点N。(请注意,从源顶点1到汇顶点N一定存在至少一条路径。)

我们的目标是,找到从源顶点1到汇顶点N的一条简单路径,使得其容量-价格比最高。这里,路径的价格等于路径含有的所有边的价格之和;路径的容量等于路径上所有边的容量最小值;路径的容量-价格比则等于路径的容量除以路径的价格。

输入

第一行含有两个整数n,m,表示顶点的数量和边的数量。顶点的编号为1到n。

接下来m行,每行包含四个整数x,y,w,c,表示一条关联x,y两个顶点,且价格、容量分别为ci,fi的边。所有的边均不区分方向。在同一对顶点之间可能存在多条边。

保证存在1到n的一条简单路径。

输出

输出一个整数,表示容量价格比与10^6乘积的整数部分。

样例输入

3 2

2 1 2 4

2 3 5 3

样例输出

428571

采用暴力方法,枚举固定容量,就是要使价格最小,转化成最短路问题,用Dijkstra解决,复杂度O(Fmlogn)。

 

障碍物

题目描述

考虑一个m行n列的长方形棋盘。以棋盘最上方为第1行,以棋盘最左方为第1列,建立坐标系。这样,对于棋盘的每一个格子,我们都可以用一对整数(x, y)表示位置。每一个格子(x, y)只与其上、下、左、右的四个格子(x-1, y)、(x+1, y)、(x, y-1)、(x, y+1)直接相连——如果这些格子存在的话。棋盘上已经有一些格子被障碍物占据。因此从棋盘左上角的(1, 1)通向棋盘右下角的(m, n)的道路有可能已经被堵住了。但是,也有可能还存在着这样的道路。而我们的目标就是添加一些新的障碍物,以保证从(1, 1)绝对无法走到(m, n)。当然,我们希望需要添加的障碍物越少越好。

输入

第一行包含两个整数m,n,表示长度和宽度。

接下来m行,每行包含n个字符,表示棋盘,其中‘.’表示无障碍物,‘#’表示有障碍物。保证左上角和右下角一定是‘.’。

输出

输出一个整数k,表示至少添加k个障碍物,就可以切断(1, 1)与(m, n)之间的所有道路。

样例输入

3 3

.#.

.#.

样例输出

1

提示

3 <= nm <= 1000000

 

可以建立一个图,目标就是找到最少的点,使得图不连通,转化成找图的点连通度问题,可以根据Menger定理用网络流解决。但是数据过大,不能用网络流。观察图的特性,不难发现,图的点连通度不大于2(起点或终点相连的只有2个点),就可以转化成求图的割点的问题,用Tarjan解决即可。但是要注意,要找从起点到终点的路上的割点,而不是整张图的割点。


面试

大一和大二的面试稍有不同。大一主要问的是《离散数学》中的知识点,比如阐述“罗素悖论”。大二主要问的是上了什么课程,根据上过课程的内容进行提问,也会问《离散数学》中的知识点。

有3个老师,每个老师大概问1个问题。

我的面试内容与上面的都不太一样,仅供参考。

Q0:自我介绍。

Q1(计算机系辅导员):计算机系的课程的学分绩如何?

Q2:网络流算法可以运用在哪些地方?竞赛中有无用到网络流算法解决线性规划的问题?知不知道Primal-Dual(对偶算法)?

Q3:阐述一下对量子计算机的理解。

Q4:阐述一下“群”的定义。


后序

两年的时间说快不快说慢不慢,当年为了转专业而孤注一掷,为了选课缓修了很多地学的课程,现在终于如愿归来。很多苦与泪已经不想再品尝一次。

计算机系有很多很有意思的课程和老师,比如计算机系统基础(ICS)、算法设计与分析、离散数学。(当然也有很呃呃的课程)

总的来说还是挺快乐和充实的:3。

最后可以给学弟学妹做个参考:

  • 计算机系课程GPA 4.5+;
  • NOIP 2016、2017 提高组一等奖;
  • CCPC 2020 长春站铜奖;
  • 转专业机试满分300分。

当然了,没有以上条件也可以成功转专业,重要的是平时的用心和备考的努力!

发表评论