转智算机试直通车-1

宇宙安全声明

本博客中所出现往年题目均来北洋维基的学长分享，不一定代表真实机试题目。此外，本人并非算法竞赛选手，且不掌握任何关于转专业机试的额外信息，因此本博客的任何内容均不构成备考建议，仅为算法分享。最后，由于本人水平有限，不保证题解绝对正确，如有任何错误或问题欢迎与我联系（QQ：2827924832）。

写在前面

考虑到最近几年的转智算的机试难度越来越高，且仍有继续上升的趋势，同时很多同学可能对OJ题目不太熟悉，不知道复习从何下手。因此萌生出写一篇机试往年题解的想法，为大家复习往年机试题的时候提供一点参考，也希望可以对大家的备考之路有一定的帮助。本博客预计会有5篇，覆盖21-24年四年的机试真题，并在最后给出几道对明年机试题的简单预测。不过最终更新情况还要取决于我的懒惰程度(bushi。

关于头文件

首先，由于机试时间有限，因此推荐各位在编程时引用合适的头文件，多使用已有库辅助编程，不仅能提升编程效率，还能简化代码，减少错误，十分滴珍贵。
据我的经验，我们学校的OJ系统是支持万能头的，所以只需在程序开始处声明如下语句，便能解决一切头文件问题。

万能头

#include <bits/stdc++.h>

不过，如果你因为各种原因无法使用万能头，以下是一些常用头文件的集合。

常用头文件

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>

关于复杂度

复杂度的相关知识和分析技巧在数据结构课程中应该会有所提及，因此在这里就不再详细展开了。在练习过程中，有些题目可能会对程序的运行时间或运行所需内存空间有所限制（也就是常说的TLE和MLE错误），因此对于较复杂的问题，你需要具备判断自己的程序能否满足题目限制的能力（天大OJ题目的限制普遍为时间1s，内存256MB）。内存大小的判断需要根据实际使用的不同数据类型进行计算，而对于时间长短的判断，只需要在分析完复杂度后记住：
1 s = 10^9 次运算

2021年题目解析

近几年的机试题目难度显著的随年份上涨而增加，因此直接按年份顺序复习即可。此外，21年的题目都很简单，如果对已经有一定的上机练习经验可以跳过此博客。

A

题目描述

输入一组整数，输出其中的最大值和最小值。
注：数据量很大。

题解及答案

这题简单易懂，要求一组数据中的最大值和最小值。因此，只需将所有数据读入，并不断记录已读入数据的最大值和最小值即可。但需要注意，由于需要读入的数据量可能极大，而cin/cout的数据读写速度要显著慢于scanf/printf，因此此题最好使用scanf来进行数据的读入。
我的答案如下：

A

int main() {
    int n;  // 数据量N
    int max, min;   // 用于记录已读入数据的最大值和最小值
    int x;  // 用于读入数据
    
    scanf("%d", &n);
    scanf("%d", &max);
    min = max;  // 初始化max和min为第一个数据
    for(int i = 1; i < n; i++) {
        scanf("%d", &x);    // 读入数据
        if(x > max)
            max = x;    // 更新当前max
        if(x < min)
            min = x;    // 更新当前min
    }
    printf("Max: %d\nMin: %d\n", max, min);
    
    return 0;
}

B

题目描述

输入两个整数，判断两数的最大公因数。
注：数据值很大。

题解及答案

这道题由于传入的数据可能很大，直接暴力搜索求解可能会时间超限，因此需要使用辗转相除法求解。这种题其实讲解的意义不大，就是考察你知不知道这种算法。但辗转相除法实在太过经典，所以还是很有必要记一下的。
我的答案如下：

B

int gcd(int x, int y) {
    if(y)
        return gcd(y, x % y);   // 递归计算gcd(y, x mod y)
    else
        return x;   // 当y为零时，x即为最小公因数
}

int main() {
    int x,y;
    cin>>x >>y;
    cout<<gcd(x, y) <<endl;
    
    return 0;
}

C

题目描述

首先输入一个整数，后面跟有多行输入，每行输入一个操作符(+ - *)和第二个操作数。
对于每行输入，输出运算后结果。

题解及答案

这道题本身是一道很简单的模拟题，只需按题目要求对每组输入的操作符进行switch判断，然后运算即可。但在北洋维基的题目要求中并没有明确指出如何进行多行输入，因此我这里假定为不预先给出行数N，也不给出跳出条件的输入方式。
对于这种无法判断何时结束的多行输入，我们只需通过while循环不断检测是否有下一组数据输入即可。由于OJ的判题方式是通过文件向程序输入，再将输出与结果文件进行比对，因此在输入结束处会读入一个EOF标志符，代表文件结尾。而对于EOF输入，cin函数会返回0，因此类似如下的语句就能顺利对组数未知的多组输入进行正确处理。
while(cin>>var) {}
据此，我们就能顺利解答本题。
我的答案如下：

C

int cal(int a, int b, char op) {
    switch (op) {
        case '+':           // 这里直接return，所以不需要break
            return a + b;   // 其它情况下switch语句记得写break
        case '-':
            return a - b;
        case '*':
            return a * b;
    }
    
    return 0;
}

int main() {
    int a, b;
    char op;
    
    cin>>a;
    cin.get();
    while (scanf("%c %d", &op, &b)) {
        cin.get();
        a = cal(a, b, op);
        cout<<a <<endl;
    }
    
    return 0;
}

D

题目描述

根据题目给出的判断条件，输入一个年份，判断其是否是闰年。

完全依赖题目给出条件的if else题，分享里也没有具体条件，因此不做解答。
猜测此题目和生环OJ上的 1025: 判断闰年I 一样，实在想做可以去尝试一下。

E

题目描述

读入两个长度为10的字符串，取第一个字符串的前五个字符和第二个字符串的后五个字符，拼接为一个新串并输出。

题解及答案

这道题的难度依旧不大，也不需要很多算法上的技巧，逐字符操作即可，只需注意字符串最后的结束符\0即可。
不过，借助此题，推荐大家熟悉一些字符串操作的常用函数，如strlen、strcmp、strcat等。此外，对于字符串相关的题目，我建议大家尽量使用string完成，可以在很大程度上避免对结束符操作不当等产生的错误，并且相关的函数也较为简单（此题用char数组更方便，因此不用string实现）。
我的答案如下：

E

int main() {
    char a[11], b[6];
    
    cin>>a >>b >>b;     // 丢弃b串的前五个字符，只需要后五个
    
    memset(a + 5, 0, 6);    // 覆盖a串后五个字符，只需要前五个
    
    strcat(a, b);   // 将b（b串后五个字符）拼接在a（a串前五个字符）后
    cout<<a<<endl;
    
    return 0;
}

总结

21级题目难度很小，可能还不及C++课程的上机作业题目，比较适合先前完全没有接触过C++程序设计的同学。后续22、23年的最后两题难度应该会有所提升。

持续更新中……