2019中科大計(jì)算機(jī)夏令營(yíng)機(jī)試

今年是中科大計(jì)算機(jī)夏令營(yíng)第一次增加上機(jī)考試，而且在離開營(yíng)一個(gè)星期的時(shí)候才進(jìn)行通知。極其短暫的準(zhǔn)備時(shí)間，加上未知的不確定性，還是帶來了不小的挑戰(zhàn)。聽學(xué)長(zhǎng)說前些年科大夏令營(yíng)不刷人，然而今年刷掉了不少人，90個(gè)報(bào)道的同學(xué)，最后保留了60左右的樣子?？赡芤?yàn)槌鰢蝿?shì)不好，導(dǎo)致保內(nèi)人數(shù)激增，競(jìng)爭(zhēng)越來越激烈。話不多說，下面就分享一下科大的機(jī)試考核內(nèi)容。

機(jī)試時(shí)間為3個(gè)小時(shí)，上機(jī)環(huán)境為Dev C++，Codeblocks，VS2015。昨晚一個(gè)題，將源代碼保存到指定的文件夾下，最后會(huì)有老師考走你的程序，進(jìn)行人工評(píng)閱。

第一題 拆分?jǐn)?shù)字

給定一個(gè)數(shù)字，拆分成若干個(gè)數(shù)字之和，這些數(shù)字必須是連續(xù)的，如6可以拆成1+2+3，也可以拆成6，問對(duì)于這個(gè)數(shù)字來說有幾種拆分方法。

輸入：許多個(gè)數(shù)字，以0結(jié)束

輸出：每個(gè)數(shù)字對(duì)應(yīng)的拆分方式數(shù)目

樣例：

輸入：

6

3

5

0

輸出：

2

2

1

思路：沒想到什么好的方法，暴力雙重循環(huán)，大循環(huán)從1-n，小循環(huán)設(shè)一個(gè)變量，每次從0加到>=n做個(gè)判斷，如果等于n則總數(shù)加一，大于n直接continue。

第二題 最大正方形周長(zhǎng)

給定一個(gè)m*n大小的矩陣，矩陣中有0和1兩個(gè)數(shù)字，問矩陣中由1構(gòu)成的正方形中最大的正方形周長(zhǎng)

輸入：m n ?矩陣每個(gè)點(diǎn)的值

輸出：由1構(gòu)成的正方形的最大周長(zhǎng)

樣例：

輸入：

4 4

0 1 0 1

1 1 1 0

0 1 1 0

1 1 1 1

輸出：

4

思路：拿到這個(gè)題的時(shí)候，我的第一想法是dp，但是想不到狀態(tài)轉(zhuǎn)移方程怎么設(shè)計(jì)。想了很久，我設(shè)了一個(gè)二維數(shù)組dp，dp[i][j]表示以(i,j)為正方形右下角頂點(diǎn)的最大正方形邊長(zhǎng)。我們假設(shè)輸入的矩陣為A：

這樣的話，顯然有 并且

那么當(dāng)且時(shí)，根據(jù)正方形的特性，dp[i][j]顯然與dp[i-1][j-1]有一定的關(guān)系，那么這個(gè)關(guān)系怎么表達(dá)呢？

對(duì)于A[i][j] = 0的所有點(diǎn)來說，其都成立。

我們發(fā)現(xiàn)如果dp[i-1][j-1] = 0，那么根據(jù)dp的定義，A[i-1][j-1] = 0。那么對(duì)于dp[i][j]來說，如果A[i][j] = 1，則dp[i][j] = 1；否則dp[i][j] = 0。即? ?

對(duì)于dp[i-1][j-1]0的情況，我們假設(shè)t=dp[i-1][j-1]，則需要再設(shè)一層循環(huán)。令k從1開始，每次加1，一直增加到t，每次加1的時(shí)候判斷一下A[i-k][j]和A[i][j-k]是否為1，若兩個(gè)值都為1，則繼續(xù)遍歷；反之，則跳出循環(huán)。得到

最后遍歷dp，找到最大的數(shù)值，即最大正方形的邊長(zhǎng)。

第三題 走棋盤

給定一個(gè)m*n大小的棋盤，給定一個(gè)初始位置(a,b)，輸入一個(gè)數(shù)代表棋盤上不能走的點(diǎn)的個(gè)數(shù)t，給出t個(gè)點(diǎn)的坐標(biāo)。問一個(gè)馬（馬走日）從(a,b)出發(fā)，能否不重復(fù)的把棋盤上（除不能走的點(diǎn)之外）的所有點(diǎn)都走一遍，若能走，則輸出有多少種走完的方式；若不能，則輸出0。

輸入：第一行 m n，第二行 t 及 t個(gè)點(diǎn)的坐標(biāo)

輸出：不重復(fù)走完棋盤的方式數(shù)目

思路：當(dāng)時(shí)看到題干里寫到m n都是小于10的數(shù)，因此很明顯，該題使用dfs+回溯的方法。dfs的思想很普遍，這里的出口寫一個(gè)判斷棋盤是否走遍的判斷函數(shù)即可。

第四題 進(jìn)制轉(zhuǎn)換

給定兩個(gè)數(shù)m n，以及一個(gè)數(shù)t。其中m代表數(shù)轉(zhuǎn)換之前是幾進(jìn)制的，n代表數(shù)轉(zhuǎn)換之后是幾進(jìn)制的(m,n都是小于等于36)，t代表原來的數(shù)，要求求解n進(jìn)制下，原m進(jìn)制數(shù)t是多少。

輸入：m n t

輸出：n進(jìn)制下等同于的m進(jìn)制數(shù)t

思路：依稀記得王道考研機(jī)試?yán)锩娴脑}，不過印象不深了。36進(jìn)制，感覺應(yīng)該是對(duì)應(yīng)0-9和A-Z這36個(gè)字符。我當(dāng)時(shí)的思路是先把m進(jìn)制轉(zhuǎn)化為10進(jìn)制，再把10進(jìn)制轉(zhuǎn)化為n進(jìn)制。但題目中又說t的位數(shù)小于1000，因此很顯然涉及到大數(shù)問題，當(dāng)時(shí)感覺時(shí)間還夠就寫了個(gè)大數(shù)乘法。。。具體的代碼可以參考一下《王道考研機(jī)試》上面第四章最后一個(gè)題，它采用了運(yùn)算符重載的方法。當(dāng)然手寫大數(shù)運(yùn)算函數(shù)也沒問題，這題比較考驗(yàn)基本功。

第五題 活動(dòng)安排

這個(gè)題的描述有些復(fù)雜，記不太清了。大概是有若干個(gè)人，每個(gè)人要參加若干項(xiàng)活動(dòng)，問怎么安排能使得總的時(shí)間最短。我認(rèn)為這個(gè)題可以抽象為一個(gè)圖論問題，考察的是節(jié)點(diǎn)的度，邊的插入刪除等一些基本操作，當(dāng)時(shí)寫了200行左右，有點(diǎn)bug最后時(shí)間不夠沒調(diào)出來，還是自己tcl。。。

總結(jié)

機(jī)試和面試各100分，淘汰掉了機(jī)試低于50，或面試低于60，或總成績(jī)低于130的同學(xué)。最后很幸運(yùn)的拿了兩個(gè)80+，順利的拿到了優(yōu)營(yíng)。

歡迎小伙伴一起討論，如有疏忽，敬請(qǐng)指正～