2019中科大计算机夏令营机试
今年是中科大计算机夏令营第一次增加上机考试,而且在离开营一个星期的时候才进行通知。极其短暂的准备时间,加上未知的不确定性,还是带来了不小的挑战。听学长说前些年科大夏令营不刷人,然而今年刷掉了不少人,90个报道的同学,最后保留了60左右的样子。可能因为出国形势不好,导致保内人数激增,竞争越来越激烈。话不多说,下面就分享一下科大的机试考核内容。
机试时间为3个小时,上机环境为Dev C++,Codeblocks,VS2015。昨晚一个题,将源代码保存到指定的文件夹下,最后会有老师考走你的程序,进行人工评阅。
第一题 拆分数字
给定一个数字,拆分成若干个数字之和,这些数字必须是连续的,如6可以拆成1+2+3,也可以拆成6,问对于这个数字来说有几种拆分方法。
输入:许多个数字,以0结束
输出:每个数字对应的拆分方式数目
样例:
输入:
6
3
5
0
输出:
2
2
1
思路:没想到什么好的方法,暴力双重循环,大循环从1-n,小循环设一个变量,每次从0加到>=n做个判断,如果等于n则总数加一,大于n直接continue。
第二题 最大正方形周长
给定一个m*n大小的矩阵,矩阵中有0和1两个数字,问矩阵中由1构成的正方形中最大的正方形周长
输入:m n 矩阵每个点的值
输出:由1构成的正方形的最大周长
样例:
输入:
4 4
0 1 0 1
1 1 1 0
0 1 1 0
1 1 1 1
输出:
4
思路:拿到这个题的时候,我的第一想法是dp,但是想不到状态转移方程怎么设计。想了很久,我设了一个二维数组dp,dp[i][j]表示以(i,j)为正方形右下角顶点的最大正方形边长。我们假设输入的矩阵为A:
这样的话,显然有 并且
那么当且时,根据正方形的特性,dp[i][j]显然与dp[i-1][j-1]有一定的关系,那么这个关系怎么表达呢?
对于A[i][j] = 0的所有点来说,其都成立。
我们发现如果dp[i-1][j-1] = 0,那么根据dp的定义,A[i-1][j-1] = 0。那么对于dp[i][j]来说,如果A[i][j] = 1,则dp[i][j] = 1;否则dp[i][j] = 0。即
对于dp[i-1][j-1]0的情况,我们假设t=dp[i-1][j-1],则需要再设一层循环。令k从1开始,每次加1,一直增加到t,每次加1的时候判断一下A[i-k][j]和A[i][j-k]是否为1,若两个值都为1,则继续遍历;反之,则跳出循环。得到
最后遍历dp,找到最大的数值,即最大正方形的边长。
第三题 走棋盘
给定一个m*n大小的棋盘,给定一个初始位置(a,b),输入一个数代表棋盘上不能走的点的个数t,给出t个点的坐标。问一个马(马走日)从(a,b)出发,能否不重复的把棋盘上(除不能走的点之外)的所有点都走一遍,若能走,则输出有多少种走完的方式;若不能,则输出0。
输入:第一行 m n,第二行 t 及 t个点的坐标
输出:不重复走完棋盘的方式数目
思路:当时看到题干里写到m n都是小于10的数,因此很明显,该题使用dfs+回溯的方法。dfs的思想很普遍,这里的出口写一个判断棋盘是否走遍的判断函数即可。
第四题 进制转换
给定两个数m n,以及一个数t。其中m代表数转换之前是几进制的,n代表数转换之后是几进制的(m,n都是小于等于36),t代表原来的数,要求求解n进制下,原m进制数t是多少。
输入:m n t
输出:n进制下等同于的m进制数t
思路:依稀记得王道考研机试里面的原题,不过印象不深了。36进制,感觉应该是对应0-9和A-Z这36个字符。我当时的思路是先把m进制转化为10进制,再把10进制转化为n进制。但题目中又说t的位数小于1000,因此很显然涉及到大数问题,当时感觉时间还够就写了个大数乘法。。。具体的代码可以参考一下《王道考研机试》上面第四章最后一个题,它采用了运算符重载的方法。当然手写大数运算函数也没问题,这题比较考验基本功。
第五题 活动安排
这个题的描述有些复杂,记不太清了。大概是有若干个人,每个人要参加若干项活动,问怎么安排能使得总的时间最短。我认为这个题可以抽象为一个图论问题,考察的是节点的度,边的插入删除等一些基本操作,当时写了200行左右,有点bug最后时间不够没调出来,还是自己tcl。。。
总结
机试和面试各100分,淘汰掉了机试低于50,或面试低于60,或总成绩低于130的同学。最后很幸运的拿了两个80+,顺利的拿到了优营。
欢迎小伙伴一起讨论,如有疏忽,敬请指正~