3.22网易互娱 笔试心路

题目具体是什么样子可以看其他朋友的帖子，这里只说说我个人当时是怎么想的。

第一题，读完以为是股票买卖最佳时机，想了想还是直接贪吧，一顿操作过了样例，提交运行0%，天崩开局，先放着看下一题。

第二题模拟任意大小2048，感觉像是写小游戏，搭了个框架，类似下面这种：

int main(){
  while(输入样例数)
  {
	存数据，存数组；
	for(遍历操作)
	{
	  switch 操作：
		上：moveUp();
		下：moveDown();
		左：moveLeft();
		右：moveRight();
	}
	输出结果；
}

四种操作大差不差，细化到每种操作，以向上操作为例，我用了deque来模拟，向上操作就遍历每列，然后从上到下入队，如果尾部元素和要入队的元素大小一样，那就尾部弹出然后双倍入队。一列完事了再覆盖原有的列，队列空了就补0。

这个思路是有问题的，比如一行是8 8 16 0，我们来模拟左操作，按照样例的意思期望的结果是16 16 0 0 ，但是按照上面那个过程我们会得到：32 0 0 0 ，这是因为队列的操作跟题意不符。

给自己搞蒙了，忘记2048怎么玩的了，到底连续合并对不对？不知道。我把第二组数据分步拆分了一下，感觉题意是合并后的数字不能再参与合并了，于是我在入队条件上又加了一个bool变量，表示能不能合并，这样如果合并过了，再来数字就不可以合并；如果这次没有合并，就把变量打开表示可以继续合并了。

四个操作都是如此，然后就过了。

第三题，先搞四个for，超时5%。想骗分只骗到10%，回头看第一题了。

我感觉第一题的思路是没错的，第一天不能卖，最后一天不能买，买的条件是第二天能获利最多。感觉没必要上dp，于是删了重新想。

当时观察了一下数据，发现第i天的买和第i+1天的卖是对应的。然后我想，为什么要先输出结果然后是步骤？有没有可能直接得到结果？顺着这个思路想，我可以计算每只股票的获利率，如何让这个利率最大化，用最后的利率乘初始资金是不是就是结果了？试了试感觉可行。

每i天与i+1天作比较，找出当天最大获利率的股票，记录获利率和坐标，且利率大于1（不然第二天卖会亏）。最后乘起来所有获利率和初始资金得到结果，然后输出：-1 第i天选的坐标\n 第i天选的坐标 第i+1天选的坐标\n ... 第n-1天选的坐标 -1，样例过了，提交运行也过了，那一刻超爽，有种莫名的喜悦感。

现在就剩第三题了，时间剩半个小时，脑子有点乱，看到内存限制131mb想打表提前记录再查询。但是感觉abcd四个存下来也太慢了。当时脑子抽了，一心想着遍历然后存abcd四个。交卷了看到大家只存cd，然后遍历ab找cd，复杂度直接开平方了。气的吃了一盒炸鸡。还有用扩展欧几里得做的，我是想不出来这点。

最后结果：100% 100% 10%