Visits: 154

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 赛的题目还是有点难的，但是质量一般，因为，见过一次，就一定会做，没见过就是很难在一个小时之内想出来，所以，我说题目质量差，是因为不能体现每位同学自己思考的水平，只要见过一次类似的题，知道结论，很快就能写对，十分钟/题都没问题，所以不适合作为现场挑战赛。而且事后看出题人的轻浮的样子，估计也没有好好选题和验题。

不过，礼品还是不错的。虽然都是无用玩意。