中國科學技術大學計算機保研上機真題
在線測評鏈接：https://pgcode.cn/problem
運動會比賽日程安排
題目描述
某運動會設立 M M M 個比賽項目，每個運動員（共 N N N 個運動員）可以參加多個項目，每個項目的比賽時長相同。
試問如何安排比賽日程，既可以使同一運動員參加的項目不安排在同一單位時間進行，又使總的競賽日程最短。
輸入格式
第一行包含兩個整數 N N N 和 M M M，分別表示運動員的數量和比賽項目的數量。
接下來的 N N N 行，每行包含若干個整數，表示該運動員參加的比賽項目編號。
輸出格式
輸出一個整數，表示最短的競賽日程（單位時間數）。
輸入樣例
3 4
1 2 3
2 3
3 4
輸出樣例
3
卷積運算
題目描述
卷積運算在數學、信號處理、深度學習等諸多領域中均有廣泛應用，深度學習中的卷積神經網絡模型 C N N CNN CNN 為使用卷積運算的代表模型之一。
對一個高為 h h h、寬為 w w w 的矩陣 I I I，和一個邊長為 k k k 的方形卷積核 K K K，經基本正向卷積運算得到的矩陣 S S S 滿足：
S ( i , j ) = ∑ 0 ≤ m < k ∑ 0 ≤ n < k I ( i + m , j + n ) ? K ( m , n ) S(i,j) = \sum_{0 \leq m < k} \sum_{0 \leq n < k} I(i+m,j+n) \cdot K(m,n) S(i,j)=0≤m<k∑?0≤n<k∑?I(i+m,j+n)?K(m,n)
其中 0 ≤ i ≤ h ? k 0 \leq i \leq h-k 0≤i≤h?k, 0 ≤ j ≤ w ? k 0 \leq j \leq w-k 0≤j≤w?k。
在 C N N CNN CNN 中，有時為了縮小特征尺寸，卷積運算中會指定步幅 s s s 進行下采樣，使經過卷積運算的矩陣縮小約 s s s 倍，即：
S ( i , j ) = ∑ 0 ≤ m < k ∑ 0 ≤ n < k I ( s ? i + m , s ? j + n ) ? K ( m , n ) S(i,j) = \sum_{0 \leq m < k} \sum_{0 \leq n < k} I(s \cdot i+m, s \cdot j+n) \cdot K(m,n) S(i,j)=0≤m<k∑?0≤n<k∑?I(s?i+m,s?j+n)?K(m,n)
此時宜對 i , j , m , n i,j,m,n i,j,m,n 限制 s ? i + m < h s \cdot i+m < h s?i+m<h, s ? j + n < w s \cdot j+n < w s?j+n<w，從而矩陣 S S S 的大小確定。
現在給定一個高為 h h h、寬為 w w w 的矩陣 I I I，和一個邊長為 k k k 的方形卷積核 K K K，并設置步幅為 s s s，求經正向卷積運算得到的矩陣 S S S。
輸入格式
輸入第一行四個正整數 h h h, w w w, k k k, s s s。
接下來輸入矩陣 I I I，共計 h h h 行，每行包含 w w w 個整數。
接下來輸入卷積核 K K K，共計 k k k 行，每行包含 k k k 個整數。
輸出格式
輸出運算后得到的矩陣 S S S。
數據范圍
對于 100 % 100\% 100% 數據，滿足 0 < s ≤ k ≤ min ? ( h , w ) ≤ 100 0 < s \leq k \leq \min(h,w) \leq 100 0<s≤k≤min(h,w)≤100。
矩陣 I I I 和 K K K 中各元素的絕對值不超過 100 100 100。
輸入樣例
4 4 2 1
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 0
0 -1
輸出樣例
-2 -2 2
-2 2 2
2 2 -2
 122. 買賣股票的最佳時機 II （貪心）)
 語法知識點及案例（22）)
快速冪算法)
