首页 > 其他分享 >1.17 CW 模拟赛 T2. 艺术家

1.17 CW 模拟赛 T2. 艺术家

时间:2025-01-17 18:14:11浏览次数:1  
标签:1.17 颜色 复杂度 T2 区间 rm 维护 CW size

前言

更重要的是研究这题的部分分, 赛时居然可以做到 \(1 \ \rm{h}\) 没有拿到任何一个特殊性质

发现以前一直用的大标题很碍眼, 改了, 下课把之前的格式也改一下

思路

暴力

容易模拟, 做到 \(25 \%\)

特殊性质 \(\rm{A}\)

思路

你发现每一个区间都是其后面区间的前缀, 而且每次长度只增加 \(1\)
容易注意到一个特殊性质区间答案单调递增

怎么处理
容易想到类似单指针的做法, 你维护已经有答案的区间前缀, 之后就是对于没有答案的区间的处理

问题在于如果修改到了已经有答案的区间前缀中, 会导致后面的答案出现问题, 如果要维护会导致复杂度出现问题


好吧仔细想一下容易发现, 你记录前缀中出现过的颜色, 然后一般的维护颜色的种类数, 然后你在扩展的时候处理即可
刚刚脑子糊了, 赛时脑子也糊了

没有按照正确顺序思考 + 脑子内存不足导致的

总结

注意这类区间不重问题的常见实现方式, 避免了更高复杂度的枚举

特殊性质 \(\rm{B}\)

思路

容易想到的是每次修改只修改包含他的区间, 问题出在怎么计算每个点被哪些区间包含, 以及如何维护每个区间的合法性?
计算每个点被哪些区间包含是简单的, 复杂度被限制在线性, 约束还是很强的

维护区间合法性显然不能使用上面的方法了, 空间开不下
不过你可以考虑根号分治, 对于 \(size \geq \sqrt{n}\) 的区间记录颜色, 否则直接枚举即可
容易证明这样子做的时空复杂度都符合要求


听了讲发现直接用 \(\rm{map}\) 搞能过, 考虑正确性证明:
考虑长度为 \(size\) 的区间中, 空间复杂度至多为 \(size\) , 至多有 \(\frac{n}{size}\) 个区间, 至多花费 \(\mathcal{O} (n)\) 的空间

考虑一共只有 \(n\) 个区间, \(size [k : n]\) 这样才能卡到上界, 即求

\[\sum_{i = n}^{k} \lfloor\frac{n}{k}\rfloor \leq n \]

对应的最大 \(k\)
发现理论上是过不去的, 随机数据是这样的, 一会去问一下


好像别人不是这个意思, 不管了

哦哦哦, 听懂了, \(\rm{map}\) 没在这用
就当我上面这一坨都没说

总结

思路还是挺好想的, 难的是维护

灵机一动想到了根号分治, 本质上其实是空间复杂度跟个数有关, 时间复杂度跟长度有关联想到的经典应用
时空复杂度也可以用根分处理

特殊性质 \(\rm{C}\)

思路

可以发现一个区间如果在某一时刻区间内部颜色互不相同则之后永远内部颜色互不相同, 而且只要对于一个 \(size\) 的区间, 操作次数达到 \(size - 1\) 就可以保证其内部颜色不相同

怎么用?
考虑线段树维护区间修改次数以及区间最优时间以达到保证其内部颜色不相同
复杂度 \(\mathcal{O} (Q \log n)\)

总结

一类线段树的常见用法

正解

思路

看到包含和不相交其实很容易想到在图上处理
你发现直接丢到图上还不够, 包含关系是有传递性的, 可以搞成一棵树

发现建出树之后, 叶子结点区间之间无交集, 父亲节点一定比其儿子节点后满足要求, 特殊的, 不同树之间显然无交集
发现修改的一个点只会在一个区间之中, 于是我们先考虑怎么判断这个区间是否合法了

方法 \(1\)

发现相当于建出树之后进行单点修改, 子树数颜色, \(\rm{set}\) 搞一下即可, 也可以用 \(\rm{dfs}\) 序和值域树状数组

不研究了

方法 \(2\)

维护每个颜色在原序列上对应的链, 区间内部颜色互不相同就是这一位置上对应的颜色的链的上一位在区间外面
考虑维护, 直接维护 \(lst\) 表示链的上一位, 还是比较简单的

主要问题是对链的维护


然后就是怎么维护树

首先建树怎么建?
疑似可以用栈

其次怎么维护叶子结点?
疑似可以用 \(\rm{set}\) 存编号

标签:1.17,颜色,复杂度,T2,区间,rm,维护,CW,size
From: https://www.cnblogs.com/YzaCsp/p/18677479

相关文章

  • 1.17 刷题
    1思路P1331海战-洛谷|计算机科学教育新生态(luogu.com.cn)本题难点主要是如何分辨哪些穿是相撞而产生无效,哪些是有效很容易想到的是,不论是bfs还是dfs都可以轻松全部搜掉,只需要简单的遍历所有点,然后套板子即可但是这是无法排除无效情况的,也就是相撞的情况推敲一下,发现......
  • MiniMax TTS新模型T2A-01-HD:情感控制10秒克隆限时免费;真人表演+文本命令,Kinetix精准生
      开发者朋友们大家好: 这里是**「RTE开发者日报」**,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(Real-TimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编......
  • AcWing 98. 分形之城 题解
    题面link【题目描述】城市的规划在城市建设中是个大问题。不幸的是,很多城市在开始建设的时候并没有很好的规划,城市规模扩大之后规划不合理的问题就开始显现。而这座名为Fractal的城市设想了这样的一个规划方案,如下图所示:当城区规模扩大之后,Fractal的解决方案是把和原来......
  • 【开源】基于SpringBoot框架毕业设计系统(计算机毕业设计)+万字毕业论文 T200
    系统合集跳转源码获取链接点击主页更能获取海量源码10年计算机开发经验,主营业务:源码获取、项目二开、语音辅导、远程调试、毕业设计、课程设计、毕业论文、BUG修改一、系统环境运行环境:最好是javajdk1.8,我们在这个平台上运行的。其他版本理论上也可以。IDE环境......
  • 【开源】基于SpringBoot框架在线考试系统(计算机毕业设计)+万字毕业论文 T207
    系统合集跳转源码获取链接点击主页更能获取海量源码10年计算机开发经验,主营业务:源码获取、项目二开、语音辅导、远程调试、毕业设计、课程设计、毕业论文、BUG修改一、系统环境运行环境:最好是javajdk1.8,我们在这个平台上运行的。其他版本理论上也可以。IDE环境......
  • AcWing 274. 移动服务 题解
    Tag:线性dp题面link题目描述一个公司有三个移动服务员,最初分别在位置\(1,2,3\)处。如果某个位置(用一个整数表示)有一个请求,那么公司必须指派某名员工赶到那个地方去。某一时刻只有一个员工能移动,且不允许在同样的位置出现两个员工。从\(p\)到\(q\)移动一个员工,需要花费......
  • 文本分割工具Text2Table
    Text2Table是我用VB.NET开发的文本切割工具,基于正则表达式。可以把一个字符串按照指定的分隔符,转换为多行多列。案例1:百家姓分割为4列。原始文本如下:赵、钱、孙、李、周、吴、郑、王、冯、陈、褚、卫、蒋、沈、韩、杨、朱、秦、尤、许、何、吕、施、张、孔、曹、严、华、金、魏......
  • PKUWC2025 Day1 T2
    来抛砖引玉一波。先声明:我的做法基于维护的数据结构不同是\(O(n\log^3{(n+m)}+m\log^2{(n+m)})\)或者\(O(n\sqrt{(n+m)}\log{n}+m\sqrt{(n+m)})\)。我的思路大致就是:按照\(x\)从小到大处理所有询问。记\(p_i\)为当前\(i\)号点的\(x\)级祖先。然后考虑如何维护区间......
  • 1.14 CW 模拟赛 赛时记录
    前言时间很短,注意管理,策略不变读题\(\rm{T1}\)需要找性质,可能不太会,但是要冲一下\(\rm{T2}\)困难串串,不知道能打多少\(\rm{T3}\)数位\(\rm{dp}\),日了\(\rm{T4}\)蒸蒸日上!困难大概是前面的没法马上切就丢掉,然后能拿的都拿,数位\(\rm{dp}\)不擅长,......
  • AcWing算法周赛第6场 | 3735 构造完全图
    学习C++从娃娃抓起!记录下AcWing备赛学习过程中的题目,记录每一个瞬间。附上汇总贴:AcWing算法周赛|汇总【题目描述】给定一个由nnn个点和......