2023南京理工大學計算機復試上機真題
2023南京理工大學計算機復試機試真題
歷年南京理工大學計算機復試上機真題
在線評測：傳送門：pgcode.cn
括號匹配二
題目描述
苗苗今天剛剛學會使用括號，不過他分不清小括號，中括號，大括號和尖括號，不知道怎么使用這些括號，請幫助他判斷括號使用是否正確。
輸入格式
輸入只包含’<’，’(’，’{’，’[’，’>’，’)’，’}’，’]'的字符串（長度不超過 10000）
輸出格式
對應每行輸入，如果輸入的字符串中的括號正確匹配則輸出 yes，否則輸出 no。
輸入樣例
(){}
輸出樣例
yes
求階乘
題目描述
給出一個數 n(1<=n<=13)，求出它的階乘。
輸入格式
輸入只有一個整數 n。
輸出格式
對于輸入的 n，求出它的階乘并輸出。
輸入樣例
3
輸出樣例
6
樹的高度
題目描述
樹是一種特殊的圖結構，有根樹是一個有固定根的樹。
現在給定一棵有根樹，編程求出樹中所有節點到指定的根節點最遠距離。
輸入格式
第一行是兩個整數 N，M（1<=N<=10000,1<=M<=N），表示數的頂點數和根節點的編號。
接下來 N-1 行，每行兩個整數 u,v（1<=u,v<=N），表示編號為 u 的節點和編號為 v 的節點間有一條邊。
輸出格式
輸出距離根節點最遠的點到根的距離。
輸入樣例
5 5
1 2
1 4
1 5
2 3
輸出樣例
3
搬箱子
題目描述
華華要給廠里進一批新箱子共 n 個(n<=500)，編號為 1 到 n，用一個正整數 ai(1<=ai<=10000)(1<=i<=n)來表示編號為 i 的箱子的高度。
現在華華要按照編號從小到大的順序選出 m 個箱子運到廠房，要確保編號大的箱子比編號小的箱子高。
也就是對于任意的 i<j 有 ai<aj，那么 m 最大可以是多少呢？
輸入格式
第一行是正整數 n，表示 n 個箱子。
第二行 a1,a2…an 分別表示編號為 i 的箱子的高度。
輸出格式
輸出華華最多可以搬運的箱子個數。
輸入樣例
7
1 7 3 5 9 4 8
輸出樣例
4
女士優先
題目描述
午餐時間還未到，饑餓的程序員們早早就在食堂門口排隊了。
假設現在的隊列是這樣的：MFM。
從左往右，第一位是男程序員（Male），第二位是女程序員（Female）,第三位是一位男程序員。
但是男程序員不會讓女程序員排在他們后面。
于是就會發生這樣的情況：只要一位男程序員發現自己后面是一位女程序員，他就會和這位女程序員交換位置，這樣的交換需要消耗一秒。
當然，在同一秒內可能會有多位男程序員和自己后面的女程序員交換位置。
現在，請問最少要消耗多長時間，隊伍不再變動。
輸入格式
輸入一個字符串，僅包含‘M’和‘F’兩種字母，表示當前的排隊情況。
（最左邊表示隊伍頭，字符串長度<=100000）
輸出格式
隊伍不再變動的時間。
輸入樣例
MMFF
輸出樣例
3
架線方案
題目描述
電信公司要在多個城市之間架設通信線路，有些城市之間可以架設，而有些由于條件限制不可以架設，可以架設線路的城市之間的架設線路成本為 c。
現有 n 個城市，求出使這 n 個城市互相聯通最節省的費用。
輸入格式
第一行是兩個整數 n，m(2<=n<=100,1<=m<=n*(n-1)/2)。
n 表示城市數，m 表示可以架設的線路數。
接下來 m 行每行三個整數 a，b，c，表示編號為 a 的城市與編號為 b 的城市之間架設通信線路的成本為 c。
輸出格式
對于每組測試數據，給出一個整數，表示最節省的費用。
(若不存在則輸出-1)
輸入樣例
3 3
0 1 1
2 1 2
2 0 1
輸出樣例
2
最大遞增子序列和
題目描述
一個數的序列 bi，當 b1 < b2 < … < bS 的時候，我們稱這個序列是上升的。
對于給定的一個序列(a1, a2, …,aN)，我們可以得到一些上升的子序列(ai1, ai2, …, aiK)，這里 1 <= i1 < i2 < … < iK <= N。
比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。
這些子序列中序列和最大為 18，為子序列(1, 3, 5, 9)的和。
你的任務，就是對于給定的序列，求出最大上升子序列和。
注意，最長的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和為 100，而最長上升子序列為(1, 2, 3)。
輸入格式
輸入包含多組測試數據。
每組測試數據由兩行組成。
第一行是序列的長度 N (1 <= N <= 1000)。
第二行給出序列中的 N 個整數，這些整數的取值范圍都在 0 到 10000（可能重復）。
輸出格式
對于每組測試數據，輸出其最大上升子序列和。
輸入樣例
7
1 7 3 5 9 4 8
輸出樣例
18
南京理工-最短路徑問題
題目描述
給你 n 個點，m 條無向邊，每條邊都有長度 d 和花費 p，給你起點 s 終點 t，要求輸出起點到終點的最短距離及其花費，如果最短距離有多條路線，則輸出花費最少的。
輸入格式
輸入 n,m，點的編號是 1~n,然后是 m 行，每行 4 個數 a,b,d,p，表示 a 和 b 之間有一條邊，且其長度為 d，花費為 p。
最后一行是兩個數 s,t;起點 s，終點 t。
n 和 m 為 0 時輸入結束。
(1<n<=1000, 0<m<100000, s != t)
輸出格式
輸出一行有兩個數， 最短距離及其花費。
輸入樣例
3 2
1 2 5 6
2 3 4 5
1 3
0 0
輸出樣例
9 11
有趣的天平
題目描述
Gigel 有一種奇怪的“天平”，他想平衡它。
事實上，這種裝置不同于任何其他普通的天平。
它訂購了兩條重量可忽略不計的手臂，每條手臂的長度為 15。
一些鉤子連接在這些手臂上，Gigel 想掛上他收集的 G（1<=G<=20）個砝碼，因為他知道這些砝碼重量在 1…25.范圍內有不同的值。
鉤子可以放下任何重量的砝碼（一個鉤子下可以放多個砝碼），但他必須使用完所有的重量。
最后，Gigel 利用他在國家信息學奧林匹克運動會上獲得的經驗，成功地平衡了設備。
現在，他想知道該設備可以通過多少種方式實現平衡。
知道鉤子的位置和砝碼重量后，編寫一個程序來計算平衡設備的可能性。
輸入格式
第一行包含數字 C（2<=C<=20）和數字 G（2<=G<=20）
下一行包含范圍為-15.15 的 C 個整數（這些數字也不同，按升序排序），表示鉤子的位置；
每個數字表示相對于 X 軸上的天平中心的位置（當沒有連接重物時，設備平衡并與 X 軸對齊；距離的絕對值表示掛鉤和平衡中心之間的距離，數字的符號決定掛鉤所連接的平衡臂：左臂為“-”，右臂為“+”）；
在下一行，有 G 個自然數、不同的、按升序排列的數字，范圍為 1…25，代表權重值。
輸出格式
輸出使天平平衡總共有多少種方案。
輸入樣例
2 3
-2 4
1 3 8
輸出樣例
1
堆排序問題
題目描述
給一個序列，要求把它調整為大頂堆需要交換的最小次數。
輸入格式
第一行輸入一個數 n，表示序列有 n 個整數
第二行輸入 n 個整數
輸出格式
輸出結果
輸入樣例
3
1 2 3
輸出樣例
1
緊急支援
題目描述
緊急支援，你有一個直升機，可以飛過連續 k 個城市(可以飛 k 個城市中的任意一個)，但只能飛一次且所需時間固定 2h，給出相鄰城市之間步行需要的時間 a(1)~a(n-1)。
現在要求出從城市 1 走到城市 n(即線性 1~n)最少時間。
輸入格式
第一行輸入 n 和 k 以及 h，表示有 n 個城市和可以連續飛 k 個城市，0<=k<=n-1。
第二行輸入 n-1 個數，表示從起點開始相鄰城市步行需要的時間
輸出格式
如題
輸入樣例
5 2 1
3 6 2 4
輸出樣例
6
AQIP 操作
題目描述
給定一個字符串以及幾個操作。
- A 操作后面跟一個字符 b 表示在字符串后面插入這個字符。
- I 操作后面跟兩個字符 b，c 表示在字符串的第 b 個位置插入字符 c。
- Q 操作后面跟一個字符 b 表示查詢字符串中字符 b 的數量并輸出。
- P 操作表示輸出整個字符串，每個字符中間用空格隔開
輸入格式
第一行輸入一行字符串
第二行輸入一個整數 m，表示有 m 次操作
接下來 m 行輸入操作指令
輸出格式
如題
輸入樣例
abcde
4
A x
I 3 a
Q a
P
輸出樣例
2
abacdex
)