首页 > 其他分享 >12月集训游记(day1-day3)

12月集训游记(day1-day3)

时间:2023-12-15 22:11:39浏览次数:27  
标签:12 140 笔刷 线段 day3 day1 这道题 数组 节点

Day 1   好好好,今天没有爆零,这真是一个良好的开局,接下来的集训我一定会学有所得的哈哈哈哈哈哈哈哈哈…   总结一下今天的题目   T1 反正是个动态规划   首先,怎么看出来这是个动态规划的……因为计数问题不是组合数就是dp,而显然,如果这道题存在组合数做法我更不会   显然,有解的一个必要条件是 n∣h,因为一个位置恰好被涂一次,一次涂 n 个位置。 如果把一个 bi +1=bi+1 的连续段称作一个块,那么所有块的大小必须相等(显然),如果不相等后面就会出现冲突。   当块大小 >1>1 的时候,那么间距都要是块大小的倍数。因此,我们可以直接将整个状态“缩小”。我们设 F(h,n) 表示块大小 >1 的答案,G(h,n)是块大小 =1 的答案,于是得到:   F(h,n)=sum k|n,k>1 (G(h/k,h/n))   那么接下来考虑 G(h,n) 该如何计算   我们把一支笔刷的{dn-1}数组最前面添加一个0,再做前缀和,得到数组{pn},将每次选择的数组{}的第一个元素bi构成递增序列{at},其中 n*t = h。   一支笔刷合法当且仅当 pi+qj 互不相同且覆盖[0, h],容易发现对于合法的笔刷,{qt}存在且唯一。   于是我们可以考虑一个这样的双射:当我们交换p,q,这对应了一支nl =t的合法笔刷。   在块大小为1的时候,首先 p1=q1=0,而p2 > p1+1=1,由于pi+qj覆盖[0,h],从而q2=1。   也就是说,当我们交换p,q之后,恰好对应一支n'=t且块大小>1的笔刷,于是可以得到转移 G(h,n)=F(h,h/n)   题解中说到了记忆化即可,但是由于平时用来写记忆化的都是线性转移,这种多维的dp想要记忆化就要用一个map+pair去维护   考试的时候因为没有理清头猪所以最后就打了一个基础的暴力,拿了点部分分,我认为这种做法是积极的、合理的,因为等到我真正到赛场上很有可能再次因为脑抽就没想到正解,这个时候能够沉稳的把部分分尽可能地拿到是非常重要的,正如向老师所说,得分是第一位的   T2 是个恶心的数据结构   在考试的时候我的思路完全错了,而且后来还没调出来   首先这道题的想法很朴素,就是建立一棵线段树用来求带修RMQ问题,对于每次插入“观察者”就是在区间内的节点上打上一个标签用来记录该观察者插入后该节点范围内的历史最大值   很显然一个节点上的“观察者”标签记录的值,按照打标签的时刻来排序,这些值应该是不严格单调递减的,那么我们就可以想到我们只需要维护某个节点的最后一个值,如果这个值在某次修改后大于了前面的值,那就把前面的值弹出,保持这个序列是不严格单调递减的   然后查询的时候就是在对应的节点上用 lowerbound,原理显然就不赘述了   我在考试的时候把这个问题想的太复杂了,因为我没想到线段树的每个节点上可以再额外开一个数组维护很多信息,因为这种做法用传统静态数组是无法实现的,大多数节点上的数组空间实际上是用不到的,这就会造成大量的空间浪费;但是使用vector动态数组就可以有效避免空间浪费,虽说常数大了一点,但是并不影响,这题的复杂度很充裕   我在考场上打了一波动态开点的主席树,然后对主席树的时间戳分了块,每一块上建了一棵线段树,外套了一个线段树求和,然后就非常愉快地 MLE 了   T3 字符串工业科技     什么叫做字符串工业科技呢,首先字符串不用解释,科技指的是十级算法,工业指的是复杂的码量……所以我还没学会SAM啊可恶,附上题解开头的第一句话       添加图片注释,不超过 140 字(可选)     最后说说今天模拟赛的启示吧    首先,省选题都是很恶心的,代码都比较长,如果没有较强的代码能力是绝对不会有很大的提升的   其次,今天的 T1T2 都有点意思,我很早的时候就想过用map储存一些用数组无法储存但是我有很需要快速查改的东西,比如用 map+pair 判断重边,再比如就是今天用到的记忆化,T2中用 vector 扩展了线段树储存信息的极限这个也是我之前就有类似想法的,但是当时不喜欢用 vector。这两个不知道算不算常见的 trick,但是同样是想到了这些奇怪的主意,别人立刻将它实现了并且出了题,而我却只是想过实现却没有真正的实施,正如向总说过的,如果有什么想法,一定要把它用代码实现一下,这样代码能力才能增强,事实也确实如此   关于动态规划的问题,我请教了同学,也算是有点收获吧,获得了一些建议,回头都可以安排上   感觉上我现在的水平场切题目难度是很高的,但不意味着不能拿分,甚至如果对问题的分析还比较到位的话,一题正解都不会也未必不能拿高分   最后数据结构题挺混沌邪恶的   Day 2   今天又没有爆零,可喜可贺   T1 依然是动态规划   看得出来,动态规划真挺常见的   这道题我和正解的分叉是从题解的第二句话开始的   首先一次操作至少删去一半点,所以m ≤ log n。事实上,m <10时答案才可能不为0。   进一步发现一次操作相当于删去当前笛卡尔树上所有儿子数 <2 的点……   先来说说什么是笛卡尔树   笛卡尔树的每个节点有两个参数,就暂且表示为(a,b)   笛卡尔树满足对于a来说构成二叉搜索树的性质,对于b来说构成二叉堆的性质,具体的见这幅图       添加图片注释,不超过 140 字(可选)     至于如何建树,暂时还不重要,这道题主要运用的是这个思想,我们可以发现一次操作相当于删去当前笛卡尔树上所有儿子数 <2 的点(特别的,对于下标最小 / 最大的点,其不存在儿子才会被删去) 因为我在写题解的时候我的文本编辑器寄掉了,而我又懒得把好不容易讲清楚的东西再打一遍,所以我就直接附上这篇不知所云的题解     添加图片注释,不超过 140 字(可选)     添加图片注释,不超过 140 字(可选) 被恶心到了不想多说了  

标签:12,140,笔刷,线段,day3,day1,这道题,数组,节点
From: https://www.cnblogs.com/qj-Network-Box/p/17904258.html

相关文章

  • 2023.12.15——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.c#明日计划:学习......
  • 12.15
    最后20分钟写个闲话今天没啥,调一道题调了一晚上......
  • 12月集训游记
    Day1好好好,今天没有爆零,这真是一个良好的开局,接下来的集训我一定会学有所得的哈哈哈哈哈哈哈哈哈…总结一下今天的题目T1反正是个动态规划首先,怎么看出来这是个动态规划的……因为计数问题不是组合数就是dp,而显然,如果这道题存在组合数做法我更不会显然......
  • 闲话12.15
    今天打了一场模拟赛,垫底了。T1找了两个小时的性质,没找到性质,寄。也没一点暴力分,有了性质基本就是100pts了,矩阵加速比较裸。T2T3已经没时间看了,就摆了,打了15pts就跑了。最终得分15pts,rk70多吧。越来越拉了呢。下午花了一个半小时改T4,有半个小时都是因为没开ll在调......
  • 12.15 闲话
    今天特别水基本没有学术昨天忘更闲话了学校奇怪规定,本地的可以回家但是外地不行幸好我是秦皇岛的不然就能回去了,哦哦原来我家长来了我又能走了推歌世末歌者蝉时雨化成淡墨渲染暮色渗透着勾勒出足迹与车辙欢笑声与漂浮的水汽饱和隔着窗同城市一并模糊了拨弄着旧吉......
  • 从嘉手札<2023-12-15>
    荒原 朔方2023.12.15人生实属是很愁的时间愁到听不见一点雪花飘落的声音愁到连随便写点文章都算得上拼尽全力萧瑟的北风吹散了为数不多的倔强漫天的雪花飞舞埋葬的是那么多年走过的春秋时光的幻象影影绰绰将就地留下一滴泪水在无边无际的茫茫大雪中我仿佛看到素白的......
  • 每日总结20231215
    代码时间(包括上课)5h代码量(行):100行博客数量(篇):1篇相关事项:1、今天是周五,今天上午的时候必然是多睡懒觉了呀,然后起床之后收拾完去借了一副手套,因为要去扫雪。2、今天中午的时候吃完饭就去扫雪了,那个雪看上去很好扫,结果都是冰,还挺费力的,也可能是好长时间没有锻炼了。3、今天晚......
  • 代码随想录算法训练营Day3 | 203.移除链表元素、707.设计链表、206.翻转链表
    这三道题都不涉及什么难以理解的算法,是对链表基础知识的一个复习巩固对于有数据结构基础的同学来说这个没有什么难度但是,写代码的过程中,我明显感觉到,我需要更加完善和统一的代码风格,作为一个前OIer,我的c和cpp混用的情况在基础数据结构的封装层面造成了不小的混乱!我需要去补充c......
  • 12.15每日总结
    分布式文件系统的特点如下:hdfs的主从结构: hdfs的分块存储:  hdfs的副本机制:为了保证数据安全,把数据放到其他机器上 hadoop文件系统操作:hadoopfs  这个Hadoop配置了默认访问为hdfs文件系统。hdfs常用shell命令:   本地文件系统即客户端所在机器,假如你在n......
  • 产学研三界顶级大咖分享:RISC-V场景Show暨开源生态高级别论坛定档12/19
    12月19日,RISC-V场景Show暨开源生态高级别论坛即将开幕。本次论坛将邀请来自中科院计算技术研究所副所长包云岗、嘉楠科技AI软件总监张晓晶、阿里巴巴达摩院生态总监陈炜、清华大学长聘副教授陈渝和中科院软件研究所高级工程师于佳耕出席,现场为大家分享新一轮处理器技术突破、RISC-V......