2017年4月15日的网易游戏实习生校招题目，3道题，2小时，对于没有经过ACM训练的人来说时间挺紧，最后没做完。但是毕竟猪场挑高手，自己技不如人，还需要多多努力。回头自己整理了下自己做得题目。可能有错误，可以给我留言。
解题思路：
拿到题目，感觉有点像背包问题，考虑使用DP来做，再考虑一下，我们根据结束时间进行任务分类，并得到最大结束时间，然后建立一个时间数组time[t]，数组大小就是之前统计的任务的最大的结束时间t，然后从time[0……]开始依次遍历，进行动态规划。具体过程为：
（1）找到上一个时间点的任务数量time[k-1]；
（2）找到所有的结束时间为 t 的任务，然后遍历这些任务，对每一个任务（比如某任务是持续时间为 s 到 t），那么我们计算time[s] + 1; 这样全部计算一遍，找到所有任务里面time[s]+1的最大值；
（3） 取 （1），（2）中的大的值更新time [t] 值；
其实算法导论里面有这道题，在贪心那一块.........代码比较简单，我就不上了.......
第二题：求淘汰赛可能最小Depth——大概意思就是求最小比赛轮数
解题思路：我们可以让胜者作为败者的父节点。已知每个人只被一个人打败，那么每个节点的父节点只有一个，构造出来就是一棵树。如题目里面的构造出来为3->1<-2<-4<-5。然后我们进行循环，每一轮去掉树中的子节点，并更新当前的子节点。这样直到找得到1节点，输出循环的轮数即可。具体过程如下：
1. 读入数据，建立两个数组，一个数组保存父节点(被打败者)，另外一个数组统计子节点数量(打败的人的数量)。
2. 从第二个数组里面找到值为0的节点，即为叶子结点(也就是没有打败任何人的节点)，保存在一个叶子结点数组里面。接下来进行循环(3,4):
3. 删除叶子节点数组的元素，存在一个例外就是，如果存在几个叶子节点有相同的父亲，则只能删掉一个，因为一轮父亲只能打败一个孩子。
4.添加新的叶子节点，每次删除一个叶子节点之后，让其父亲节点的孩子节点数量-1(第二个数组)。如果这个父亲节点孩子数为0，则加入到叶子节点数组。
5.重复3.4直到1节点被添加到叶子结点数组。此时输出循环的轮数，就是淘汰赛可能最小Depth。
代码如下，Visual studio 2013可运行：
#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;
//3个数组：p——存对应的父节点，rc——存孩子节点个数 c——存当前轮的叶子结点
int windepth(vector<int>& p, vector<int>& rc){
vector<int> c;
int res = 0;
for (int i = 2; i < p.size(); i++){
if (rc[i] == 0) c.push_back(i);
}
int id = c.size();
while (c[0] != 1){
++res;
int s = 0;
vector<bool> ct(p.size());
for (int i = 0; i < id; i++){
if (ct[p[c[i]]]) c[s++] = c[i];
else if (!(--rc[p[c[i]]])) c[s++] = p[c[i]];
ct[p[c[i]]] = true;
}
id = s;
}
return res;
}
int _tmain(int argc, _TCHAR* argv[])
{
int n;
cin >> n;
vector<int> p(n+1), rc(n+1);
for (int i = 2; i <= n; i++){
cin >> p[i];
++rc[p[i]];
}
cout<<windepth(p,rc)<<endl;
return 0;
}
第三题：祖玛游戏
解题思路：一看限制时间5秒，估计是个回溯，没跑了……大概两个递归，一个是碰撞位置的递归，一个是消除的递归。
先扔个代码：
#include "stdafx.h"
#include <iostream>
#include <string>
#include "time.h"
using namespace std;
string destory(string s, int indx, bool begin){
if (s.size() >= 3) {
if (begin && indx == -1 || indx == s.size()) return s;
int i = indx + 1, j = indx + 1;
while (j<s.size() && s[j] == s[indx + 1]) j++;
while (i>=0 && s[i] == s[indx + 1]) i--;
if (j - i > 3) return destory(s.substr(0, i + 1) + s.substr(j), i, true);
}
return s;
}
bool dfs(string s, string t){
if (s.size() == 0) return true;
if (t.size() == 0) return false;
if (dfs(s, t.substr(1))) return true;
for (int i = 0; i < s.size()-1; i++){
if (s[i] != s[i + 1]){
if (dfs(destory(s.substr(0, i + 1) + t[0] + s.substr(i + 1), i, false), t.substr(1)))
return true;
}
}
if (dfs(destory(t[0] + s, -1, false), t.substr(1))) return true;
if (dfs(destory(s + t[0], s.size() - 1, false), t.substr(1))) return true;
return false;
}
int _tmain(int argc, _TCHAR* argv[]){
int n;
string s, t;
cin >> n;
for (int i = 0; i < n; i++){
cin >> s >> t;
string f = s.substr(s.size());
clock_t start, finish;
start = clock();
if (dfs(s, t)) cout<<"true"<<endl;
else cout <<"false"<< endl;
finish = clock();
printf("共耗时%.3lf秒", ((double)finish - start) / 1000);
}
return 0;
}
晚上我在更新....