2/4考试总结

时间安排

8:30–9:00 看题T1是期望,T2是个数据结构T3不太会正解但是有一堆部分分。
9:30–10:00 T1对于 n<=6 可以暴力 dp ,考虑 n<= 100 怎么做一个点是这个排列是肯定不能枚举的于是想到估计要转化成相对大小什么的有个模糊的 dp 敲了一下发现不太对但是 m=1 的时候应该是可以通过的。
10:00–10:13 T3把 n^2 dp 写了。
10:13–11:20 T1,对于 n<=13 可以三进制状压然后把 m=1 写了。看了一眼 T2 ,暴力可以无脑 sort 然后就不会了题目的排列的条件不知道怎么处理然后就卡在 10 分做不下去了。
11:20–12:50 T3对于最大值比较小的可以暴力然后是一堆部分分两个值的可以分讨前缀和偶数为 n 的可以分讨二分数据随机的可以用栈维护最大最小值然后枚举区间做这就有 4 个档了每个档做法都一样中间还吃了趟饭写着写着就结束了。

回顾反思

T1:
依旧是期望的 trick ,
$\sum P(x=i)\cdot i=\sum P(x>=i)$ 。
这个套路是典的更为重要的点是怎么实现转化以及怎么处理的这道题枚举 x 大于等于的一个限制 i , 然后把所有满足限制的看作 1 ,不满足的看作 0 ,那么就只需要对 1 的个数计数然后看最后第 k 个是不是 1 就行了。这种钦定限制后按有无贡献分成两类只考虑 “0/1” 的思想要学习一下。
T2:
部分分没有一点想法很可惜。
对于部分分考虑对排列逆置换之后就可以看作区间内元素大小的一个分布然后可以 hash 处理在线段树上维护 hash 值就好了。感觉对这种数据结构维护的问题敏感度不是很够需要多练一练。
正解非常强是 kmp 。考虑原问题是考虑在维护好 q1,q2,…,qk 之后能否加入 qk+1 结合具体题目发现具有自反性、对称性、传递性是一组等价关系于是任何kmp 的性质和思路都可以套用用kmp的方法维护就行了。
T3
最为关键的是要知道
以最大值为例设 $a_i处于且为最大值的区间为[l_i,r_i]$ 那么枚举 $\sum \min (i-l_i,r_i-i)$ 的复杂度是 $O(n\log n)$的。
dp 时若左边区间更小那么枚举左边 dp 值更新右边的某个区间相当于区间加可以差分若右边区间更小枚举右边的 dp 值受左边某个区间的贡献相当于求区间和可以前缀和维护。
于是复杂度就是 $O(n\log n)$ 的了。