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

今年是中科大計(jì)算機(jī)夏令營第一次增加上機(jī)考試弃酌，而且在離開營一個(gè)星期的時(shí)候才進(jìn)行通知引谜。極其短暫的準(zhǔn)備時(shí)間型宙，加上未知的不確定性，還是帶來了不小的挑戰(zhàn)吝梅。聽學(xué)長說前些年科大夏令營不刷人虱疏，然而今年刷掉了不少人，90個(gè)報(bào)道的同學(xué)苏携，最后保留了60左右的樣子做瞪。可能因?yàn)槌鰢蝿莶缓茫瑢?dǎo)致保內(nèi)人數(shù)激增装蓬，競爭越來越激烈著拭。話不多說，下面就分享一下科大的機(jī)試考核內(nèi)容牍帚。

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

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

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

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

輸出：每個(gè)數(shù)字對應(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。

第二題 最大正方形周長

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

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

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

樣例：

輸入：

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)的最大正方形邊長纳胧。我們假設(shè)輸入的矩陣為A：

這樣的話，顯然有 并且

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

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

我們發(fā)現(xiàn)如果dp[i-1][j-1] = 0，那么根據(jù)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的情況蛆挫，我們假設(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ù)值妇垢，即最大正方形的邊長巾遭。

第三題 走棋盤

給定一個(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)該是對應(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)基本功。

第五題 活動安排

這個(gè)題的描述有些復(fù)雜菩彬，記不太清了凶异。大概是有若干個(gè)人，每個(gè)人要參加若干項(xià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业舍，或總成績低于130的同學(xué)。最后很幸運(yùn)的拿了兩個(gè)80+，順利的拿到了優(yōu)營舷暮。

歡迎小伙伴一起討論态罪，如有疏忽，敬請指正～