Google APAC Test 2017 Round C
早就应该做一下笔试的原题了，也好体会一下题目的难度与区分度，结果一直拖延。。。
前两场也都做了，成绩和这场一样不理想，做出三道，第四道的时候时间还剩一个多小时，正常来讲是应该要想出来的，但是当时特别特别困，还饿，加上本人智商有限，还剩半个小时的时候上床睡觉去了。。。
Problem A. Monster Path
题意是给出R*C的格子，然后给你一个起点，走S步。每个点如果是’A’的话有P概率爆出怪兽，不是的话有Q概率爆出怪兽。一个点最多爆出一个怪兽。
求你走S步之后，最大的怪兽数量期望。
深搜，记录每一个点访问的次数x，每次加上该点爆出怪兽的期望，(1-P)^x*P或者(1-Q)^x*Q。最后记录最大值。
Problem B. Safe Squares
题意是求R*C矩形内，全为0的正方形数量之和。
和上一篇E题一样，DP每一个点作为正方形右下角的最大边长，计算结果的时候加一起。
Problem C. Evaluation
题意是给出变量之间的关系，就像C++语言看一个变量是否被定义。如果是没有参数变量的函数的返回值，那么该变量就是确定的，否则就依赖于其参数是否确定。函数执行的顺序是打乱的。
其实就是拓扑排序嘛，O(n^2)搞一下，没有定义的变量为-1，找到这样的直接out。否则的话就看能不能有确定的拓扑排序。
Problem D. Soldiers
题意是Alice和Bob做游戏，现在有n个士兵，每一个士兵有一个攻击力和一个防御力，要求每一个人选的士兵要么攻击力大于当前被选的所有士兵的攻击力，要么防御力大于当前被选的所有士兵的防御力，选择不到时游戏停止。现在给出n个士兵的攻击力和防御力，Alice先选，要求的是最终Alice选择的士兵要比Bob多。问两者都是最优选择的情况下，是否可行。
给一个链接，说的还是挺明白的，将所有士兵按照攻击力排序，按照防御力排序，如果存在一个士兵特厉害，两个属性都冠绝群雄，那么Alice胜利，因为Bob没得选了。如果不存在，那么Alice一定不会去选攻击力最大的那个或者防御力最大的那个，因为万一选了这两个中的一个，那么Bob选择另一个，数量上是打平的，Alice赢不了。所以这样的数据就可以从可选的集合里面删去了，然后这样不断求解。
这个题也让我学习到了一个新的函数。。。remove_if(a.begin(),a.end(),cmp) cmp里面放入if判别条件，删除容器内符合条件的元素，不符合条件的元素依次往前走，返回结束位置。