中国科学技术大学计算机保研上机真题
在线测评链接：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）)
快速幂算法)
