5.10美团笔试

似乎美团笔试成绩不重要，不管了，求捞吧

选择题(30分10道)

选择题6道大模型，完全不会，乱选，还有一道希尔排序，早忘光了，乱选...

编程题(70分3道)

第一道 100%

似乎是每次可以朝着上下左右走a_i步(a_i=0 or 1),求当前位置(x,y)是否能恰好在走完n步后到达(p,q)

EZ，直接判断曼哈顿距离，看是否能走到，只要走到目的地之后还可以走偶数步即可（左右/上下摇摆）

第二道 100%

最多选择一个操作使得区间[l,r] 一起加1，求陡峭程度的最小值？（陡峭程度为）

蛮简单，差分的思想，区间相加对应的是suf[i]++,suf[r+1]--;

对于suf_i 和suf_j有4种情况（><，<>，>>，<<0）只要suf出现了非0元素则可以通过l=1 or r=n的方式解决。

若满足了suf_i<0&&suf_j>0 (j>i)则一个负数++和一个正数--，减免2

第三道 0%

前两道写完还有一个多小时，没想出来，最后打了暴力O(nq)还是0%，麻了

从数组 （长度为 ）中挑选两个非空子序列，这两个子序列元素在原数组中的相对顺序与原数组一致。若这两个子序列都严格单调递增，则称这对子序列满足条件。

现给出 q 组查询，每组查询给出一个区间 [l,r])（基于数组 a 的下标），请判断区间 内是否存在满足条件的两组非空子序列。

如果存在，输出 YES，否则输出 NO。

还以为是简单的最长上升子序列呢（其实也算是？），结果发现无法做

线段树，用到结论：一个序列可以被划分成 k 个严格单调递增子序列，当且仅当它不包含长度为 k+1 的严格单调递减子序列。（Dilworth定理?）

即一个序列可以被划分成两个严格单调递增子序列，当且仅当它不包含长度为 3 的严格单调递减子序列。

---> 判断给定的子区间 a[l...r] 是否包含一个长度为3的严格单调递减子序列

很久没写题了，已经成残废了