当前位置: 首页 > news >正文

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 ,
∑ P ( x = i ) ⋅ i = ∑ P ( x > = i ) \sum P(x=i)\cdot i=\sum P(x>=i) P(x=i)i=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 ] a_i 处于且为最大值的区间为 [l_i,r_i] ai处于且为最大值的区间为[li,ri] ,那么枚举 ∑ min ⁡ ( i − l i , r i − i ) \sum \min(i-l_i,r_i-i) min(ili,rii) 的复杂度是 O ( n log ⁡ n ) O(n\log n) O(nlogn)的。
dp 时,若左边区间更小,那么枚举左边 dp 值更新右边的某个区间,相当于区间加,可以差分;若右边区间更小,枚举右边的 dp 值,受左边某个区间的贡献,相当于求区间和,可以前缀和维护。
于是复杂度就是 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的了。

相关文章:

  • Ta-Lib源码解析(三):蜡烛图指标 (Candlestick Indicator) #(附Python重构代码和示意图)(补充中)
  • 【嵌入式】MDK使用sct文件将代码段放入RAM中执行
  • 《基于Xilinx的时序分析、约束和收敛》目录与传送门
  • Jackson序列化带有注解的字段的原理浅析
  • 第十届“图灵杯”NEUQ-ACM程序设计竞赛题解(A-I)
  • Linux ALSA 之九:ALSA ASOC Codec Driver
  • 一文读懂JVM类加载机制过程及原理
  • 一文带你入门MyBatis Plus
  • java split()方法 toLowerCase() 方法
  • Ubuntu - command checklist
  • 小程序-模板与配置-WXSS模板样式
  • 小程序-模板与配置-WXML模板语法
  • 群晖NAS安装frp实现内网穿透(非Docker)
  • Linux性能学习(2.1):内存_查看系统内存以及Buffer Cached说明
  • Connext DDS开发指南(5)基本QoS策略
  • MoCoViT: Mobile Convolutional Vision Transformer
  • Harbor安装
  • leetcode解题思路分析(一百三十六)1158 - 1169 题
  • @EnableWebMvc注解让swagger-ui.html无法打开404报错问题及其解决方案(史上最全最详细)
  • Java接口:概述、多实现、多继承、JDK8后接口新增方法
  • 电加热油锅炉工作原理_电加热导油
  • 大型电蒸汽锅炉_工业电阻炉
  • 燃气蒸汽锅炉的分类_大连生物质蒸汽锅炉
  • 天津市维修锅炉_锅炉汽化处理方法
  • 蒸汽汽锅炉厂家_延安锅炉厂家
  • 山西热水锅炉厂家_酒店热水 锅炉
  • 蒸汽锅炉生产厂家_燃油蒸汽发生器
  • 燃煤锅炉烧热水_张家口 淘汰取缔燃煤锅炉
  • 生物质锅炉_炉
  • 锅炉天然气_天燃气热风炉