机试list

Posted on Edited on In

机试的难度

个人认为，机试难度可以分四个等级：

第一级，清北难度，能通过且取得不错成绩的很多都是打ACM竞赛的大佬，没受过专业训练很难拿高分，这个难度下题目很多都是ACM竞赛等级。不过北大的难度貌似没有那么高。

第二级，华五难度，题目涉及基础算法和数据结构，如果只会暴力算法无法通过机试，但如果你刷过一些算法和数据结构的题目，非低分通过机试应该不成问题。

第三级，基础难度，以北航华科为代表，题目涉及大量基础数据结构和编程细节，主要考察编程而非算法能力，个人认为接触过基础数据结构且编程细心的同学应该能够通过。但这些高校往往会限定标准C编程，这点还要注意。

第四级，不进行机试，以国防科大、中科院自动化所为代表，这些学校只有面试没有机试。
刷题

整理出一些典型题目或“板子”以备考前复习。

南大计算机 300分的题目一共三道题，每道题100分、通过样例点给分（每道题10个样例点），是在线OJ形式、可以看到自己的实时排名（和浙大类似）,动态规划多一些 120以下的同学貌似被淘汰了、同学190都是专硕。
浙大 三小时四道英文题，题目难度号称PTA甲级难度（实际难度是PTA乙级到甲级之间），题目分值是20,25,25,30这样.题目是OJ形式，根据通过的样例点得分，不计罚时，采用PTA的系统，能够看到自己的实时得分和排名
中科大 机试和上交的机试形式差不多，都是非OJ形式。具体而言，三小时做五道算法题，开始的时候给你发纸质的题目和示例（中文），然后自己写程序自己想样例测试，最后工作人员拷走你电脑上的程序。题目采用C/C++，允许使用STL，编译器有VC,VS,code blocks, dev c++等。题目样例没有全通过的话最后会有老师阅卷打分，这点和北航一样。
 2019
北航 题目采用C/C++，允许使用STL，编译器有VC,VS,code blocks, dev c++等。虽然之前的通知和宣讲会说最好是C标准编程，但实际上都是可以用的。然而北航的评测系统不是OJ形式，只能显示你提交的代码编译是否通过，具体能不能AC只能靠本地自己编用例测试了（所以一定要细心！！）。不过还好，如果你有一道题没有AC的话，老师会查看你的源代码，根据你代码体现的思想和编码习惯什么的给分，所以就算做不完也一定要记得提交呀！
上交 上交的机试不是OJ形式的，而是发给你英文的纸质题目描述和一个样例（运行时间10s以内都ok），自己编写、本地调试，结束后由老师过来把源代码和可运行的exe文件拷走，可选择的编译器有VS/code blocks/DEV C++等
北深
清深

参考: https://blog.csdn.net/qq_38633884/article/details/97178586

自动化所:问数学和机器学习多一些，自动化所只有面试没有机试

中科大的考核机制：学院机试+学院面试+课题组考核，其中学院的机试、面试小分和学院考核总成绩都达标即可获得优营资格，听过优营比例很高的，我们这届计算机夏令营貌似有六七十人

二分图模板题

https://www.cnblogs.com/shenben/p/5573788.html

位运算

[link]

找出只出现一次的数

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。

所有的数进行异或

m的n次方

也可以参考快速幂的做法

1
2
3
4
5
6
7
8
9
10
11
12
//快速幂的递归写法,复杂度为 logb 
long long mypow(long long a,long long b){
    if(b==0)   return 1;
    else{
        if(b&1==0){//为偶数
            return mypow(a,b/2)*mypow(a,b/2);
        }
        else if(b&1==1){
            return a*mypow(a,b-1);
        }
    }
}

找出不大于N的最大的2的幂指数

​ 把N的二进制中最左边的 1 保留，后面的 1 全部变为 0, 如何实现?

​ ans=最左侧的1,eg: N=19 = 0001 0011, ans = 0001 0000

代码实现:

1
2
3
4
5
6
7
int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。
    return (n + 1) >> 1;
}

上交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1. 给定两个英文单词，每次操作可以删去任一单词中的任一字母，求使两个单词最终一样的最少操作次数
Eg：给定eat和sea，最少操作次数为2。
输入：eat/sea
输出：2

2. 商店中有若干商品，它们也会打包在一起优惠出售，现给出需要购买的商品数量，求最低购买价格。要求购买的商品数量刚好符合题目要求。
eg：
输入信息：[2,4],[[3,0,5],[1,2,10]],[3,2]
题目解释：
输入：第一个矩阵是商品单买的价格，第二个矩阵为各种打包售卖时的数目与价格，第三个矩阵是各类商品需要购买数量
输出：最低价格
举例：商店中有A、B两种商品，A价格为2元，B价格为4元；优惠组合一包含3个A商品，0个B商品，共5元；优惠组合二包含1个A商品，2个B商品，共10元；现在要购买3个A商品，2个B商品；
答案：最低价格是，购买1个优惠组合一（含3个A、0个B），5元；再单独购买2个B，8元；共计13元
输出信息：13

3. 一个有序三元组（a,b,c）, 1<=a<=X, 1<=b<=Y, 1<=c<=Z，且a，b，c皆为正整数。
 给定X,Y,Z求所有能够形成三角形的(a,b,c)的数目。(3,4,5)和(3,5,4)为两个三角形。
 输入:X Y Z（三个数都在1到10的九次方之间）
 输出数量。输出结果对1000000007取模。
 样例:
 输入：2 3 3
 输出：9