2022.3.5

第一题

给一个带有重复数字的数组，找出最长的不连续的序列的长度（好像是上升的）。

输入：1,2,3,5,6,7

输出：4，最长为【1,3,5,7】

我的思路：签到题，排序一下，然后一个个找即可。

第二题

给一个数组，你可以将其中某一段翻转，然后求连续子数组的最大和。

输入：-1,3,-5,2,-1,3

输出：7（将数组下标1-2的元素翻转，然后求得3+2+-1+3 = 7，另有别的翻转方法）

我的思路：瞎想了半小时，求两个数组，left[i]保存i左边的连续子数组最大和，right[i]保存右边的，然后相加即可。

估计边界有问题，只过了90%。

第三题

切豆腐，豆腐是正方体，边长n，一共切m刀。

每刀对着x、y、z轴之一垂直切，切的轴上的坐标会告诉你。

输出每刀切完后，剩下的豆腐块中最大的豆腐体积。

输入：

2 3

x y z

1 1 1

输出：

4

2

1

我的思路：设两个对角的顶点，每次根据切的边长靠近一个顶点。

自己想的例子倒是能过，但是始终只有18%。

第四题

给一个数组，长度为n，操作m次。

操作为两种，一种是查询一个区间的和，一种是给一个区间加上一个数。

在操作开始前，你可以对数组重排序，求出所有查询和的最大值。

例子想不起来了，反正不会做。

我的思路：第一眼差分？前缀和？但是复杂度好像没有减少。然后还要根据查询次数多的，把最大的数字放到最频繁的区间里。快结束的时候想起来好像是线段树？

附加题

已经来不及了，就看了下题目。

一个小游戏，随机生成一个四位数，你输入一个答案，会告诉你有几个数对了，然后有几个数在里面但是位置不对。

例如：1234 你输入1203，告诉你2个对了，1个在里面但是位置不对

题目要求：给定m次操作，会输入一些数，告诉你返回结果，让你猜测答案是什么。

我的思路：输出一个1000·9999的随机数，然后交卷。