网易游戏3.22笔试

1.买卖股票问题，给定天数N和M支股票N天内每天的价格，和初始资金K，求最后一天的最大资金。买卖股票数量可以为小数，每天都可以同时进行买和卖两种操作。

考虑贪心：

• 买某只股票，一定是用当前所有的资金去买；
• 卖某支股票，也一定是全部卖出。
• 我只需要每天赚的最多（每天都选能赚最多的那一只股票，第二天卖出），就可以保证最终赚的最多。

所以也不会存在同时持有多只股票的情况。

做法是计算一个一维的path数组（类似路径的概念）保存每天买哪只股票。在第i天准备购入的股票，应当是第i+1天的价格相比于第i天的价格的增长率，在所有股票中是最高的。当然，如果所有股票在第i+1天价格都变低了，可以将path[i]置为-1，表示这一天不必操作。

预处理得到path数组后，遍历一遍path就可以重放一遍所有操作，并得到最终资金。

2.“2048”问题，给定矩阵和一系列上下左右移动的操作，输出最终矩阵。

我有段时间还是挺喜欢玩2048的。

考虑到对于左右移动操作，合并操作是以每一行为单位进行的；上下移动操作，合并也是以列为单位进行。所以我可以将一个一维的vector作为输入，构造一个merge函数，函数的输出应该是合并之后的vector。

merge函数里，可以用双指针或者单指针，实现忽略多余0并合并相邻项的功能。比如对于向量4 0 4 2 0 2，合并之后应当是8 4 0 0 0。

该如何调用这个merge函数呢？考虑到对于move_left，只需要取出原矩阵每一行，分别执行一遍这个merge就可以。对于move_right，在move_left的基础上对vector做两次reverse；上下移动的话就需要构造一个column列作为横向的vector了，后续实现类似。

3.四元方程组求解问题。A*x+B*y+C*z+D*w=N。ABCDN都是给定的，且xyzw需要位于[0,2500]，问是否存在解，并输出字典序最小的解。

2500的数据规模的话，O(n2)是可以实现的。

vector<int,pair<int,int>> sum1_map;

可以想到在给定A B的情况下，可以暴力枚举x和y，得到n方大小的一个map，map中key是A*x+B*y的值sum，value放pair对用于保存x和y（因为x和y是先枚举的x再枚举的y，所以当某个sum首次被添加到哈希表时，此时的x和y组合字典序一定是最小的，不需要考虑后续的值覆盖情况）。

同理能得到关于z和w能构成的所有值的一个map。我还用set分别保存了一下所有的sum，到这里的思路上感觉没太大问题，但是一提交就内存超限哈哈哈（似乎时间也超限）。通过率一次是15%，一次是35%

所以一开始做了很多剪枝，比如A*x+B*y的值sum大于N时就break，但是都不在点子上。算了一下数据规模，2500的方再乘约10B的话，要到60多MB去了。所以似乎不能用两个哈希表。

后面想到只需要对z和w做一个哈希表sum2_map就可以，有了这个哈希表之后我去两层for枚举x和y，判断target-sum1在不在sum2_map里面，当成立时就输出。这样我先保证了z和w的字典序最小，又保证了x和y的字典序最小，终于ac。