大家好，我是南开大学14级软件学院的本科生，2017年有幸先后参加到了北京大学前沿交叉学院和清华大学计算机系的夏令营。总所周知，夏令营都会有机试这个流程，很多同学因为没有acm，ccfcsp相关经历，对机试的准备和考试过程中的注意事项不太了解，在此我以我的经历，为大家做一些该方面的介绍。
首先我先给出2017年北京大学交叉学院的考试题目，共10道题目，时限三个小时，ACM赛制（赛制等问题下文我会讲到），题目基本按照难度递增排序，其中中文题目6道，英文题目四道：
我先简单概括下10道题目，如果有描述不清楚的地方，也请其他同学指出，也可以直接去百炼查看原题http://www.bailian.openjudge.cn/dsj2017xly/。
1.点排序
给出平面上n(n<=1000)个点和一个目标点，先要分别求得n个点到目标点的距离（欧式距离），然后按照n个距离作为第一关键字，n个点的x轴坐标作为第二关键字，n个点的y轴坐标作为第三关键字。给出n个点的排序结果。
2.单词倒排
读入一行英文，英文中只包含字母和空格，单词间以单个空格分隔，将所有单词的顺序倒排并输出，依然以单个空格分隔。
如输入：I am a student则要求输出：student a am I
3.生存游戏
给出一个n*m(n,m<=300)的元胞自动机，可以简单理解为一个n*m的矩阵，里面各个元素的值为0或者1，0表示死亡，1表示存活，然后对于每个细胞（元素），通过他的8个邻居（周围8个元素）的状态来判断下一秒时它的状态（具体看题设），要求给出下一秒的状态。
4.特殊密码锁
有一个一维由0/1组成的密码锁，长度为n（n<30）,每次按动会翻动自己和前后共三个锁，给出一个初始状态和一个终止状态，问至少翻动多少次可以从初始状态达到终止状态。
5.开餐馆
有n(n<=1000)个餐馆，离散在一维数轴上，每个餐馆有一个位置（即是数轴上的一个点）和一个利润值表示在此地开餐馆可以获得的利润，你可以选择任意个上述位置用来开餐馆，但是任意两个餐馆的距离必须大于k，问最大的利润是多少
6.Meteor Shower
一个人在一个二维坐标系的原点，他得到了M（M<1e5）条信息，每个信息告诉他在t (t<1000)时刻，有一颗流星会降落在(x，y)点上（x,y < 300）。
流星降落时会毁坏当前点和上下左右共五个点，使得他们不能到达，该人每个时刻可以选择向上下左右移动一格，问该人达到安全区域的最短时间是多少？（安全区域即是一个不可能被任何流星击中的点的集合）。
7.双队列
有一个系统，我们对这个系统执行q个任务，每次可能包括：
1.让一个优先级为p的客户k进入(p<1e7,k<1e6)
2.找到当前系统中优先级最高的人离开系统，并输出他的id
3.找到当前系统中优先级最低的人离开系统，并输出他的id
注意的是，一个客户可能会被添加多次，每次的优先度可能不同。
8.Silver Cow Party
给出一个有向图，有n个人分别在1,2..n节点上，现在他们都要前往s节点，然后再从s节点返回，假设他们都很聪明，都会选择最短的路线，那么请问他们中路程最长的人走了多远（n<1000）,保证各个点一定可以到达s，以及s一定可以到达各个点。
9.The Balance
给定两种砝码质量为a,b，要求你使用这两种砝码称量出质量为k的物品，要求使用砝码数量的总数最小，问最小数量。（a,b<1e4 k<5e4 且保证a!=b）
10.Computer Basketball Game
等待zjz大神写
大家可以先思考下，更建议要参加夏令营的同学可以实际模拟做做（大部分的题目都可以在poj中找到），在做后再看下文给出的题解：
下面我简要给出10个题目的题解，由于篇幅有限，设计到一些基础的算法，我只能给出对应的名字，大家如果不熟悉可以自己百度学习下~首先感谢BUAA的zlf大神，NKU的zjz大神和DUT的MSN大神对我的帮助和指点。
1.简单排序
由于数据量比较小，可以采用的排序算法比较多，常规的如冒泡排序，选择排序等均可以通过，但是要自己实现，较为麻烦（比赛的时候寸金寸光阴啊）。最好的方法是c++中使用sort函数，注意需要声明对应的cmp函数，或者重载结构体中的<。
2.简单字符串处理
这个题目比较基础，c++的话稍微慢一点，要手动的判断空格，然后将各个单词提出出来，压入stack中，再依次弹出就可以了。本题我用的是java实现的，java中的string提供了split方法，可以直接用空格来分割，然后倒序输出即可，大概只需要5行代码。
3.简单模拟
简单的模拟下就可以，注意各个节点的邻居数量不一定有8个（边界上的点），然后按照题目中所给的条件一次判断各个节点的死活。
4.贪心 or DFS + 剪枝
错误思路：
暴力bfs，用set进行判重，复杂度O(2^n)，超时了。
正确思路：
方法1：先声明一个性质，每个锁最多只会被按下一次，按两个的效果等于不按。然后利用这个性质，先讨论第一个锁按下与否，然后对于每一种情况的第i（i>=2）个锁按下与否都可以确定下来，依次枚举即可。
方法2：dfs，每个锁只有开和不开两种状态，看似复杂度为复杂度O（2^n），加入剪枝条件，在第i个锁按下后，若前i-1个锁的当前状态与目标状态不符，则该方案无解，原因可类比方法1.
5.DP
按照各个餐馆数轴位置，先预处理，prep[i]在1...i-1编号的节点中距离i超过k的最大节点编号。然后进行dp，D[i][j]表示在1-i这i个餐馆中，选择开j个的最大盈利，那么有 :
D[i][j]=max(D[i-1][j]+D[prep[i]][j-1]+w[i])
答案就是D[n][i]中最大的项。
6.BFS
预处理一个N*M的矩阵(可以看做地图)，遍历每个流星，依次更新A[i][j]表示当前点最早的被摧毁时间。然后从原点开始做BFS，直到找到一个没有被毁坏的点为止，每次转移时的条件是当前时间+1小于矩阵上的时间。
7.数据结构
本题正解是平衡树，维护三个数组和一个平衡树，b[i]表示编号为i个客户是否在系统中，big[i]表示i用户在系统中的最大优先级是多少，small[i]表示i用户在系统中的最小优先级是多少。平衡树为tree。
对应每次的三种操作：
1.进入系统操作，如果当前用户k在系统中，并且当前的优先级p在[ small[k] , big[k] ]这个区间内，那么这个进入是没有意义的，直接跳过（因为用户离开的时候，一定不会利用到该优先级）。否则更新small[k]，big[k]的值并删除对应平衡树的节点，然后将该优先级的节点插入。
2.利用平衡树找到并删除最大优先级的客户的全部节点，更新其b[i]的值。
3.利用平衡树找到并删除最大优先级的客户的全部节点，更新其b[i]的值。
三种操作均可以在O（logq）的时间内完成，注意一个性质，按照我们的做法，任意时刻，在平衡树中属于一个用户的节点不会超过两个，这也才保证了我们的操作都可以在O（logq）时间内完成。总时间复杂度为O（qlogq）
然而这个题的q很小（题目都没给具体的值），大部分人都是使用暴力过的，即是用一个数组维护而非平衡树，这样的操作复杂度为O（q^2），个人认为是这个题目的一个漏洞。
8.最短路+反向边
一道非常套路的题目，从s回到各点的最短路使用Dijkstra或者SPFA很容易求得，但是如果求得各点到s点的最短路需要做n次Dijkstra，会超时。所以就把图中所有边反向过来，再从s做一次Dijkstra，把两次dist值相加即可。
这个题也吐槽一下，很多人用玄学的Floyd卡过去了，众所周知，Floyd的复杂度为O（n^3）。在这个范围是肯定超时的，故个人估计数据范围没有那么大，也提醒大家在没有思路的时候可以勇于暴力，或许就能”玄”过去。
9.数论（扩展gcd）
我的解法是扩展欧几里得，这也是经典的数论题目了，运用扩展欧几里得去解a*x+b*y=gcd(a,b)，所要的重量d一定是gcd(a,b)的倍数(否则无解)。通过一组特解x0，y0分别得到|x|和|y|最小的四组解（前后各两组），在这四组解中找到|x|+|y|最小的即是答案。
Zjz大神给出了一种dp的解法（待更新）
10.概率DP
该题目等待zjz大神给出答案
以上是对于2017年北京大学交叉学院的机试题目解析，可以看出部分题目还是有一定难度的。能达到6道题以上的同学可能有需要一定的算法基础。但是其中也不乏一些技巧的运用，我将会在后续的文章中讲解对机试的准备和考场上技巧的运用。
如对此有疑问，欢迎大家联系我：donghexin1996@126.com
