![2024年1月2日模拟赛](/img/20240102214347.webp)
2024年1月2日模拟赛
![](https://picx.zhimg.com/v2-9e83e1fd23eccdb98450679841a3a4bc_xll.jpg)
总结
啊哈!这是 2024 年的第一篇博客!我们现在已经坐落在 nfls!这里好多人,好多人好厉害!(语气怎么这么奇怪)然后今天是模拟赛,还是很有难度的。第一道题目爆零了!原因是开了很多个 deque。长记性了。呜啊。很好的题目!非常兴奋!今天是冬月廿一!癸卯年就要结束了,接下来是一个新的甲辰年!
题解
还是想在这个地方写一些东西。感觉我的博客好不严肃啊。算了,管他的。主要是太严肃太无聊了。所以要有趣一点!
T1
我感觉题解比我讲得好。如果我只有前面这一句的话,那么我说的很对。因为我相当于什么都没有讲。
但是我觉得我讲了前面这一句话也是成立的。
哦对了,这道题是原题。那我更不想讲了。CF 上面的一道题。Andryusha and Nervous Barriers。
算了还是简单讲一下。就是状态很少,所以可以合并。然后也很少。然后尝试暴力转移。也就是要找到所有有用的,不能做无用功。就在线段树上记录一下最小的 h 值就行。很棒的小技巧!
T2
原神启动!
这道题目的题目背景很有趣,建议仔细研读。
你说的对,但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「提瓦特」的幻想世界,在这里,被神选中的人将被授予「神之眼」,导引元素之力。你将扮演一位名为「旅行者」的神秘角色,在自由的旅行中邂逅性格各异、能力独特的同伴们,和他们一起击败强敌,找回失散的亲人——同时,逐步发掘「原神」的真相。
好好好。但是这是校外的题目。放链接看不了题目我突然发现。我想我应该把题面复制到某一个地方。不是很道德……但是我觉得我的博客应该没有人看。所以嘻嘻……
题意(题面):
给定一颗
有
,表示先将树上 之间路径上的所有点都加上一个棋子,然后把树根调整为 。 ,表示将 的子树内的所有点都加上一个棋子(注意此时的树根),然后把树根调整为 。
每次操作后,输出此局面的 SG 值。
对于
做法是树链剖分,当然你可以使用静态 top tree全局平衡二叉树做到一个
容易发现一个简单性质,题解有一个和直径中心的性质,我没有看懂。但是有大佬提出了更好的做法!就先把根为 1 的搞出来,发现每次只是转变一条链上的,而且大多数是链上的,不在链上的只有
T3
首先发现后一坨是 0,就只有前一坨。
用 set
维护连续段,用线段树套可删堆维护区间内所有集合中都没有出现的数, 就是从
线段树维护的信息与 subtask 4 类似,还需要维护子树内可删堆的最小值,下放标记时需要判断最小值是否等于当前点可删堆的最小值或儿子节点子树内的最小值,对儿子节点进行整体加或者最小值加。
还没改完。待做ing……
后记
今天就结束了!以后要加快速度!提高效率!新的时代要开始啦!我们要坚定理想,不忘初心,活出自己的精彩!
- 标题: 2024年1月2日模拟赛
- 作者: 混氏新子
- 创建于 : 2024-01-02 21:34:04
- 更新于 : 2024-01-02 21:49:29
- 链接: https://blog.huasushis.cn/2024/2024年1月2日模拟赛/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。