USTC-BDAA-2023-保研机试全解
其他:
我是2024考研USTC的学生,在***老师的主页上发现了CODIA平台,题目均来源自CODIA平台。本人能力有限,不足以成为***老师的学生。但他的题目确实给了我许多启发。实话实说,题目难度并不简单。不愧是***老师。本着开源精神,本人将能做的题目用自己的方式做了,分享给考研保研USTC的大家。如果涉及侵权,请联系我,将以第一时间删除,另外,如果有做过这个机试的学长学姐,也希望您能分享关于这个机试的其他感受,比如做多少题才能录取等等。就我的发现来说,BDAA实验室只有20年的面经,21年以后的算法题难度和20年简直是天壤之别,不知道是突然难度提升了,还是***老师这里本来要求就高。
CODIA链接:首页 | CODIA (bdaa.pro)
2023-保研
1.纸上得来终觉浅
题目描述
卷积运算在数学、信号处理、深度学习等诸多领域中均有广泛应用,深度学习中的卷积神经网络模型(CNN)为使用卷积运算的代表模型之一。
对一个高为 ℎ、宽为w 的矩阵 I,和一个边长为 k 的方形卷积核 K,经基本正向卷积运算得到的矩阵S 满足:
。
其中 。
在 CNN 中,有时为了缩小特征尺寸,卷积运算中会指定步幅 进行下采样,使经过卷积运算的矩阵缩小约倍,即:
。
此时宜对 限制 ,从而矩阵的大小确定。
现在给定一个高为 ℎ、宽为的矩阵,和一个边长为的方形卷积核,并设置步幅为,求经正向卷积运算得到的矩阵。
输入描述
输入第一行四个正整数。 接下来输入矩阵,共计行,每行包含个整数。 接下来输入卷积核,共计行,每行包含个整数。
输出描述
输出运算后得到的矩阵。
数据范围
对于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
这个题意说的不清楚,或者说我没读懂,总有3个过不去,期待在评论区你的AC代码。
2.山回路转不见君
同22年螺旋矩阵。
3.不识庐山真面目
题目描述
对一个正整数,定义为的因子个数。 如12的因子有1,2,3,4,6,12,故而 。
现在给定正整数,求的值。
输入描述
输入一行,一个正整数。
输出描述
输出一行,一个正整数表示所求结果。
数据范围
对于30%的数据,满足 1≤N≤5000。 对于100%的数据,满足1≤N≤。
样例输入
4
样例输出
8
AC代码
//
// Created by liu'bo'yan on 2024/3/1.
//
#include <iostream>
using namespace std;
#define max_n 1000000
using ll=long long;
int prime[max_n + 5] = {0}; //素数表,存储找到的素数
int f[max_n + 5] = {0}; //f[i]表示数字i的因数的个数
int cnt[max_n + 5] = {0}; //cnt[i]表示数字i 最小质因数的幂次
void init() {
for (int i = 2; i <= max_n; i++) {
if (!prime[i]) { //若数字i是素数
prime[++prime[0]] = i; //存放在prime数组中
f[i] = 2; //素数的因数只有1和本身,所以f[i] = 2
cnt[i] = 1; //i = 1 * i,所以最小质因数的幂次为1
}
for (int j = 1; j <= prime[0]; j++) { //遍历之前找到的素数,若prime[j] 小于数字i的最小质因数,则我们标记prime[i * prime[j]] = 1
if (i * prime[j] > max_n) break; //我们只要在2到max_n范围内的素数,若超过max_n,此时直接跳出
prime[i * prime[j]] = 1;
if (i % prime[j] == 0) {
//这部分解释见下文
f[i * prime[j]] = f[i] / (cnt[i] + 1) * (cnt[i] + 2);
cnt[i * prime[j]] = cnt[i] + 1;
break;
} else { //prime[j]是素数,因此i和prime[j]的因数最多是1和prime[j],又i % prime[j] != 0,所以i和prime[j]互素
f[i * prime[j]] = f[i] * f[prime[j]];
//两元素互素,因此他们的因数除1外没有交集,所以i * prime[j]的因数个数 = i的因数个数 * prime[j]的因数个数
cnt[i * prime[j]] = 1;
//因为从prime数组1号位开始向后遍历素数并且i % prime[j] != 0,所以prime[j]始终小于i的最小质因数,
//所以i * prime[j]最小质因数的幂次为prime[j]的幂次,即为1
}
}
}
return ;
}
int main() {
init();
ll ans = 1;
int n;
cin>>n;
for(int i=2;i<=n;i++){
ans+=(ll)f[i];
}
cout<<ans;
return 0;
}
因子个数函数用代码计算,在网上一直没找到很好的资料,大部分都是从数论角度进行论证。lz数理基础不行。看不懂。这个线性筛版本计算因子个数函数的代码供大家参考。这题样例设置的也够狠。暴力1个都过不去。