
3 月 12 日晚上去交大闵行校区参加了 VMWare 的沙龙,后面有一个现场 Coding 挑战赛,1 个小时,3 道题,我一题都没做出来,或者更明确的说法是,我都知道考什么知识点、也都写了,但是由于各种各样的问题,每道题都只通过了部分 Case 拿了部分分,没有任何一题是成功 AC 的。

博弈论。
思路完全错误了。
后来知道正解是,只要是偶数就一定是后手胜利,因为后手可以完全仿照先手的做法。
对于奇数,如果先手能够成功处理木头的分隔到不可拆分,那么先手胜利,因为那么剩下是偶数根木头,而先手已经成为后手。
特别要注意长度为质数,而最短分隔 k = 1 的情况。

显然贪心不成立。
动态规划。
没写出来。
后来知道正解是,A 的策略是最大化 A – B 的差值,B 的策略是最小化 A – B 的差值。
计算 f[L, R] 表示在一个区间之内考虑,分别对 A 和 B 选取最佳策略,令 Fa[L, R] 取 max, Fb[L, R] 取 min。

维护每个点的入度,入度为零,删掉,并删除相连的边和点,如此遍历,直到所有点被删除,得到唯一的答案。
需要注意维护的过程,小心不要超时,例如不能暴力枚举。
然后我做的时候,没有超时这个问题,反而是内存超过限制,不知道是不是开了太大的数组,或者是我用的语言是 Java 的缘故。

VMWare 这场沙龙的 Coding 赛的题目还是有点难的,但是质量一般,因为,见过一次,就一定会做,没见过就是很难在一个小时之内想出来,所以,我说题目质量差,是因为不能体现每位同学自己思考的水平,只要见过一次类似的题,知道结论,很快就能写对,十分钟/题都没问题,所以不适合作为现场挑战赛。而且事后看出题人的轻浮的样子,估计也没有好好选题和验题。
不过,礼品还是不错的。虽然都是无用玩意。