sitJac's Blog
0%

ECNU Dase Postgraduate Entrance Examination

Posted on In
  • 华东师范大学 数据科学与工程学院 2022年复试上机题分析:
    • 最大池化考察了二维数组的操作，滑动窗口，最大值查找等算法，同时需要对深度学习中池化概念有一定的了解。
    • 去商场是一个典型的图搜索问题，可以使用BFS来解决。
    • 表情拦截主要考察了二分搜索相关的知识点以及基本的C++的语法和特性。
    • 其余题目基本都是对题目本身的理解和特定的业务逻辑的处理。

2022

题目总览

A 最大池化

A.jpeg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;

int kx, ky, dx, dy;
int matrix[200][200];
int ans_matrix[200][200];

void InputMatrix(){ //输入原来的矩阵
    for(int i = 0; i < dx; i++){
        for(int j = 0; j < dy; j++){
            cin >> matrix[i][j];
        }
    }
}

void MaxPooling(){    //最大池化操作
    for(int row = 0; row <= dx-kx; row++){
        for(int col = 0; col <= dy-ky; col++){
            int max_num = INT_MIN;
            for(int i = row; i < row+kx; i++){
                for(int j = col; j < col+ky; j++){
                    max_num = max(max_num, matrix[i][j]);
                }
            }
            ans_matrix[row][col] = max_num;
        }
    }
}

void OutputMatrix(){ //输出池化后的矩阵
    for(int i = 0; i <= dx-kx; i++){
        for(int j = 0; j <= dy-ky; j++){
            cout << ans_matrix[i][j] << " ";
        }
        cout << "\n";
    }
}

int main() {
    cin >> kx >> ky >> dx >> dy;
    InputMatrix();
    MaxPooling();
    OutputMatrix();
    return 0;
}

B 去商场

B.jpeg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
使用BFS从小明家开始搜索，每次尝试向上下左右四个方向移动，如果遇到障碍或者已经访问过的格子就跳过，如果遇到商店就停止搜索。最后输出从小明家到商店的最短步长，如果无法到达商店就输出-1。
*/
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100;
int N, M, x;
char grid[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
pair<int, int> start, end;

int BFS() {
    queue<pair<pair<int, int>, int>> q;
    q.push({start, 0});
    visited[start.first][start.second] = true;
    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        if(cur.first == end) return cur.second;
        for(int i = 0; i < 4; i++) {
            int nx = cur.first.first + dx[i], ny = cur.first.second + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny]) continue;
            if(grid[nx][ny] == '#' || (grid[nx][ny] == '%' && x == 0)) continue;
            visited[nx][ny] = true;
            q.push({{nx, ny}, cur.second + 1});
        }
    }
    return -1;
}

int main() {
    cin >> x >> N >> M;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> grid[i][j];
            if(grid[i][j] == 's') start = {i, j};
            if(grid[i][j] == 'e') end = {i, j};
        }
    }
    cout << BFS() << endl;
    return 0;
}

D 数组变换

D.jpeg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200;

int n;
long long nums[MAXN];

void Function(){    //判断是否可以通过任意次操作，使数组变为不严格的升序数组
    if(n == 1){
        cout << "NO" << endl;
        return;
    }
    for(int i = 0; i < n - 1; i++){
        if(nums[i] > nums[i+1]){
            if((nums[i] % 2 == 0 && nums[i + 1] % 2 != 0) || (nums[i] % 2 != 0 && nums[i + 1] % 2 == 0)){
                long long temp = nums[i];
                nums[i] = nums[i + 1];
                nums[i + 1] = temp;
            }
        }
    }
    int flag = 1;
    for(int i = 0; i < n-1; i++){
        if(nums[i] > nums[i+1]){
            flag = 0;
            break;
        }
    }
    if(flag == 1){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}

int main(){
    cin >> n;
    if(n == 0){
        cout << "NO" << endl;
        return 0;
    }
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    Function();
    return 0;
}

E 表情拦截

E.jpeg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll k, x;

int main() {
    cin >> k >> x;
    ll sum = k * (k + 1) / 2;
    if(x <= sum) {
        ll l = 1, r = k;
        while(l < r) {
            ll mid = (l + r + 1) / 2;
            if(mid * (mid + 1) / 2 <= x) l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    } else {
        ll rest = x - sum;
        ll rows = rest / k;
        if(rest % k != 0) rows++;
        cout << min(2 * k - 1, k + rows) << endl;
    }
    return 0;
}

F 拍照队形

F.jpeg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;

int n;
string str;

bool isBeautiful(int number_of_0, int number_of_1){
    if((number_of_0 - 1) * 2 == number_of_1){
        return true;
    }
    else{
        return false;
    }
}

void Function(){
    int number_of_0 = 0;
    int number_of_1 = 0;
    for(int i = 0; i < str.size(); i++){
        if(str[i] == '0'){
            number_of_0++;
        }
        if(str[i] == '1'){
            number_of_1++;
        }
    }
    //先判断是否是美观的
    if(isBeautiful(number_of_0, number_of_1)){
        cout << "0";
    }
    else{
        // cout << "nobeautiful";
        int need = 0;
        need = (number_of_0 - 1)*2 - number_of_1;
        cout << need;
    }
    
}

int main(){
    cin >> n;
    cin >> str;
    Function();
    return 0;
}

G 树上异或和

G.jpeg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int pre[maxn], in[maxn], post[maxn], lch[maxn], rch[maxn], val[maxn], n;

int build(int L1, int R1, int L2, int R2, int dep) {
    if(L1 > R1) return 0;
    int root = pre[L1];
    int p = L2;
    while(in[p] != root) p++;
    int cnt = p - L2;
    lch[root] = build(L1 + 1, L1 + cnt, L2, p - 1, dep + 1);
    rch[root] = build(L1 + cnt + 1, R1, p + 1, R2, dep + 1);
    val[root] = dep;
    return root;
}

int dfs(int u) {
    if(!u) return 0;
    if(!lch[u] && !rch[u]) return val[u];
    if(lch[u] && rch[u]) return dfs(lch[u]) ^ dfs(rch[u]);
    return dfs(lch[u] ? lch[u] : rch[u]) * 2;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> pre[i];
    for(int i = 1; i <= n; i++) cin >> in[i];
    int root = build(1, n, 1, n, 0);
    cout << dfs(root) << endl;
    return 0;
}

2021

题目总览

ID.1 卷积

1卷积.png

ID.2 因数之和

2因数之和.png

ID.3 原型蛋糕

3圆形蛋糕.png

ID.4 选课

4选课.png

ID.5 子树

5子树.png

2019

题目总览

A 数字排序

A.png

B 找零钱

B.png

C 斐波那契数列

C.png

D 字符串拼接

D.png

E 矩阵求和

E.png

F 阶乘

F.png

G 分石子

G.png

H 小华的游戏

H.png

I 消消乐

I.png

m大的机试小tips

  • 必须熟练掌握并会运用一些基本的算法，例如模拟, 二分, 递归, 分治, 数学, 贪心, 动态规划, DFS, BFS，等等。

  • 关于参考书目，市面上关于机试的参考书目也相当多。
    王道系列《计算机考研：机试指南》内容非常详细，可惜针对此书的OJ已经关闭，王道论坛官方便将此书pdf发布出来供大家下载。不过，这类基础算法和上机考试书的内容都大同小异，胡凡、曾磊主编的《算法笔记》以PAT甲级和乙级的题目为实例，同样详细地讲解了各类基础算法。书上还提到C++ STL的简单使用方法，如果你只会用基本的C语言，没有接触过C++，那这本书可能会非常适合你，学着利用C++的STL提高做题效率，许多函数能省去自己编写的麻烦。百练OJ也有相应的参考书《算法基础与在线实践》。还有诸如《挑战程序设计竞赛》，《算法竞赛入门经典》等，当中有些内容针对ACM竞赛，其难度超过考研机试的水平，凡所种种不再列举。大家可以根据自己情况进行相应书目的参考和阅读。

  • 建议学习一下 C++ 标准模板库STL
    机试支持的语言有C, C++, Java, python3。最建议使用C++。大家在准备初试考试时可能还是主要用的C语言。C++比C语言难的地方主要在于面向对象的特性，但这部分内容在比赛时是可以不用的，所以掌握入门的C++知识的难度与C语言相比并没有太大区别。由于C语言在一些语法细节上不如C++用起来方便，建议比赛时用C++写，可以理解成用的是经过稍许改进的C语言。更重要的是，C++有STL这个使用非常方便的库是C语言没有的，
    例如，用STL写个整数的排序操作只要1行，而用C语言的写法，则需要六七行才能完成，而且还需要理解函数指针等复杂概念才可以。

  • 还可以学习一下简单的Python，遇到大数处理时，Python可能对非常大的整数计算，如果是几十位几百位的整数的运算，在Python中就当普通的运算就可以正确，大数处理用C或C++会比较麻烦。