有幸拿到rk1,但由于服务器卡成OI赛制,少A整整一道题。

这里多吐槽一句，连我们学校校内软卓选拔都舍得开一个月600的云服务器(当时我负责的这事儿)。北师大也太勤俭持家了吧,弄两天弹性服务也成啊呜呜呜

感觉凉透了，老师一直在问我rk能保研不(双非低rk的伤)。然后英语问答也没准备好，让介绍家乡，我就憋了三句话(我感觉让我用中文说，也就能说三句话).还是要多准备模板啊！！！

7.14号更新:拿到北师大offer了~北师大yyds啊

将a,b数组对应的存成点对。对第一维度(a)升序排序,那么条件转化为: 当 a [ i ] > a [ i − 1 ] 当a[i] > a[i-1] 当a[i]>a[i−1]时，必须有 b [ i ] ≥ b [ j ] , j ∈ [ 1 , i − 1 ] b[i] \geq b[j],j\in[1,i-1] b[i]≥b[j],j∈[1,i−1].即 b [ i ] ≥ max ⁡ j = 1 i − 1 b [ j ] b[i] \geq \max_{j=1}^{i-1}b[j] b[i]≥maxj=1i−1​b[j].

所以根据我们的条件,对第一维排序，当相等的时候，对第二维升序排序。

这么排完后，我们只需要 O ( n ) O(n) O(n)的 c h e c k check check一遍第二维是否非降即可。

时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)

n ≤ 100 n \leq 100 n≤100

就枚举 a , b , c , d a,b,c,d a,b,c,d,强行解方程完事了，有点无聊的题目。当然，我还被卡常了，打了个表过了。

时间复杂度: O ( n 4 ) O(n^4) O(n4)

经典题目，我tm还能推错转移方程，自撒算了我靠。

不懂怎么做这题的，推荐看我这篇博客的第3题，把状态机思想弄明白

令 d p ( i , j = 0 / 1 / 2 / 3 ) dp(i,j=0/1/2/3) dp(i,j=0/1/2/3) 代表前 i i i个长度,并且当前以状态 j j j结尾的方案数.

j = 0 j=0