美团9.23笔试题解

1.问i>=2有几次小于之前最小/大于之前最大：遍历，维护min和max
坑点：维护min和max的时候不要每次都重新求，重新求的时候又要on复杂度
2.给初始时间，加时间减时间，求最终时间：mod=24*60模拟
坑点：因为有减法，推荐每次都是ans=ans-res+mod%mod，来避免ans小于零
坑点：输出的是00:00而不是0:0
3.求数列121321432154321的前n项和，n=1e13：数学，等差数列
首先进行一个简单的分组1 21 321 4321 54321，这样增长的速度是n2，也就是说根号复杂度是可以遍历前面多少组的
所以只需要遍历往前模拟第几组，记录ans是当前答案，now代表当前位置，step代表步长（也可以代表组数什么的），到n的时候如果被中断了，就加上多出来的不完整的一组（因为是连续所以也可以等差数列）。推荐自己画一下
4.求最长子序列，使bi=bi-2：维护下标
别人给出了dp的思路，应该比我这个好理解（而且我也不会算我的复杂度）
首先有两种可能，要么子序列全相同，要么子序列由x和y组成
全相同直接就是取max长度。如果是x和y组成的话，需要维护出每个数字的下标。然后直接枚举x和y（同时固定先后顺序），同时再来两个指针去遍历下标，每次都去贪心的选最小的能满足当前条件的下标（也就是要大于另一个数组的当前下标，同时保证自己选的尽可能少）
这样子选出来就是贪心最优的情况
5.给定数组，多组询问[l,r]第一个乘x不是完全平方数的数：预处理平方数，维护相同连续数字，重排询问（或者二分查询）
首先简化一下题目，如果原数组中存在因子为平方数，那就直接约去
如果询问的x存在因子为平方数，也可以直接约去
对于[l,r]的询问，只有全都为a[i]=x的情况下可能为-1，如果存在连续相同的值，那就每组只需要看第一个值（因为要选最前面的）
然后我们再去维护一个表示相同连续的数组，通过[l,r]的形式记录下来
例如1 6 6 3 3就能被记录成[[1,1],[2,3],[4,5]]
例如当我要访问区间[3,4]的时候，发现在组2和组3里，那就只需要去判断组2和组3的值是否为x即可
可以选择二分查找，去定位到底在哪个组（因为是有序的）
也可以选择通过重排询问关键词为l，然后挨个遍历过去看到了那一组（因为不是强制在线询问），然后再输出答案