Day1
争夺圣杯
By YJMWOI,题解 By C_SUNSHINE
算法一
这个复杂度是
算法二
上一个做法太暴力了,可以发现
复杂度
算法三
暴力做法已经没有什么可以优化的地方了,我们把它扔进垃圾桶。
考虑一个元素
找到
设
接着观察这些区间的长度分布,不妨设
当
当
当
注意到这三段都是关于
所以相当于给一个数组加上若干等差数列,只要求最后每个位置的答案。对于这个问题,我们直接在这个数组的一阶和二阶差分上进行修改,最后从前往后扫一遍求出原数组即可。
使用倍增RMQ建出笛卡尔树来计算
算法四
注意到我们并不需要建出笛卡尔树,只要使用两个单调队列从前往后和从后往前分别扫一遍,就能对每个位置求出对应的
时间复杂度
合唱队形
By jiry_2
嗯..slyvia 是一个萌萌哒的妹子。
算法一
所以就相当于有
考虑从看过
那么答案就是
期望得分
算法二
这种情况下总的状态数不超过
考虑每一个点出发的转移,可以发现每一个点能转移到自己或者多一个已完成课程的状态,因此转移是一个套上自环的 DAG,于是就可以按照拓扑序进行 DP,对每一个点解一个一元一次方程就能得到答案了。
期望得分
算法三
令
考虑算
所以可以先
这个也是可以容斥的,我们枚举有多少个特殊数没有被看过,那么就变成了有
容斥的过程中,我们把若干个
将里层的式子拆开,就相当于对很多个真分数
所以在容斥的过程中出现的每一个分数
于是枚举位置容斥的时候把贡献累加起来就好了,时间复杂度
算法四
不难发现算法三的复杂度其实是
考虑当
所以可以令
预处理一下后这一部分的时间复杂度是
均衡两部分的时间复杂度后可以得到一个
果冻运输
By xllend3
算法零
手玩了两个点心力憔悴,我还是让出题人感受我的哲♂学吧。
期望得分
提交记录:http://uoj.ac/submission/84215
算法一
辣鸡出题人居然搞了个这么长的题面我看都懒得看。直接点下提交爽一爽吧。
期望得分
算法二
手玩!
根据手玩技巧和花的时间不等可以获得
算法三
我发现这游戏我玩过http://qrostar.skr.jp/index.cgi?page=jelly&lang=en
看我轻松手玩每个点至少
但是由于部分分给的特别少,而且大多数的点和原游戏有一些细微的差别并不能直接照抄,又因为一旦步数超的太多就
验题组手玩取
考场上单挑
算法四
搜搜搜!根据搜的技巧不同能获得
详细搜法见immortalCO的博客,我就不详细讲了。
为什么checker给源码呢
虽然checker半个多钟头肯定也能写出来了,但是这样的话我就会变成辣鸡模拟题出题人,所以就直接给源码了。我才不会告诉你其实是因为懒得check每个平台下的问题呢,哼
为什么数据和游戏有点不一样呢
其实原来是照抄游戏的,但是由于是NOI膜你赛,VFK要求最高分达到250,于是就把每个点压缩了几列让比较弱的搜索多拿点分,然后删了几个点,最后成功完成控分。
要是这题考场上有人A了就可以全真模拟题题有人A但是没人AK的情况了
Day2
Jakarta Skyscrapers
By qmqmqm
以下复杂度中的
算法一
每次暴力枚举得到消息的两个doge,看他们能不能使一个之前没有得到过消息的doge得到消息,直到不能操作为止。时间复杂度
算法二
对于
否则,我们可以采用类似这种方式:
…………
在
可以通过第二个subtask,期望得分
算法三
对于
否则,我们可以采用辗转相除的方法得到1。每次计算
这样看起来是
可以通过第三个subtask,期望得分
算法四
特判
将算法二和算法三结合,先通过算法二得到
操作次数不超过
可以通过所有数据,期望得分
如果你的做法常数过大,可以通过前四个subtask得到70分。
奇怪的线段树
By jiry_2
算法一
一共有
时间复杂度为
算法二
不难发现无解当且仅当存在一个节点它的孩子中有黑色节点但它自己却是白色的。这样显然是无解的,而只要不存在这样的情况,我们可以直接找出所有是黑色但是孩子都不是黑色的节点,仅对这些节点的区间单独操作,这样就得到了一个可行解,因此这个条件是充分必要的。
于是我们就不用状压全部节点了,只需要考虑所有是黑色但是孩子不是黑色的节点的染色情况就行了,这样状态数就减少到了
时间复杂度为
算法三
命题一:一次覆盖时最终定位的点的区间一定是连续的,而且一定是连续的一段右儿子加上连续的一段左儿子(从左到右)。
证明:考虑反证法,如果存在从左到右连续的左儿子和右儿子,那么它们一定是同一个节点的两个孩子,这时在定位的时候我们取得一定是它们的父亲而不是它们本身,矛盾。
命题二:每一段连续的右儿子加连续的左儿子这样的序列一定可以通过一次定位得到。
证明:首先,我们证明一个引理,就是线段树上的所有右儿子对应的区间的右端点是互不相同的,所有左儿子对应的区间的左端点是互不相同的。
考虑反证法,假设存在,那么这两个右儿子一定是祖先关系,因为他们的区间相交了,令深度较浅的是
通过这个命题,我们得到的信息是,对于一个右儿子,往右和它相邻的右儿子恰好只有一个,因此确定了出发点后不停的走连续的右儿子的路径只有一条,左儿子同理。
因此一个左侧的右儿子和一个右侧的左儿子之间至多只存在一条满足条件的路径。
我们来考虑路径最多有多少条,假设每一个左侧的右儿子都可以和一个右侧的左儿子组成路径,每一个左儿子一定可以和它每一个祖先的左儿子组成路径,每一个右儿子一定可以和它的每一个祖先的右儿子组成路径,这样计算出来的路径条数一定不小于真实的路径条数。
令
考虑归纳法:等于
假设把
因此每一个区间和每一条这样的线段树上的路径都是一一对应的。
于是我们可以把每一次覆盖拆成两部分,分别为连续的一段右儿子和连续的一段左儿子,并在两条链的 LCA 处统计它们。
令
这个算法的时间复杂度非常高,不过
算法四
在算法三中,我们已经发现连续的一段右儿子加连续的一段左儿子的路径与序列中的区间是一一对应的。
考虑把每一个点的后继都连出来,对于每一个右儿子
我们把这张图建出来,不难发现我们得到了一个 DAG,因为我们每走一步所在节点的左端点都是增加的。
同时不难发现这个 DAG 上的每一条路径都是合法的,即都是满足由连续的一段右儿子和连续的一段左儿子组成的。因此这个 DAG 上的每一条路径,我们都可以通过一次操作进行覆盖。
于是就变成了给出一个 DAG,其中有一些点至少经过一次,有一些点不能经过,问最少多少条路径能满足条件。
这是一个裸的下界最小流问题。
点数
算法五
考虑优化连边,连边的瓶颈在于对每一个右儿子都连一条边指向与它相邻的节点,这部分是可以优化的。
我们新建
同时对每一个线段树节点
这样边数就优化到了
在出题的时候我一直觉得这道题是可以线性贪心的,但是因为 ddl 实在太多一时间又有点想不清楚(实际上是不会证明),所以还是放
如果大家想出了贪心的算法欢迎和我讨论。
火车管理
By SkyDec
这是一道十分清真的小清新数据结构题
首先题目可以转化为,有
算法一
我们可以直接用
时间复杂度
空间复杂度
期望得分:
算法二
考虑一种比较简单粗暴的做法
我们以铁路的编号为下标建立一颗线段树。
则对应的操作就是区间压一个数,单点弹一个数,区间求栈顶之和。
我们可以在线段树上用可持久化treap作为标记,压数和弹数就便成了treap的合并与分裂。标记的下传合并也可以在
由于可持久了treap,所以时间复杂度和空间复杂度也相当正确。
时间复杂度
空间复杂度
期望得分:
算法三
我们可以建立一颗可持久化线段树,维护每个铁路每个时间的栈顶的吨位和栈顶火车的入栈时间。
我们再维护一颗线段树用来统计答案。
于是操作就显得很简单了:
区间询问:直接在答案线段树里询问即可。
区间压数:在可持久化线段树上进行区间覆盖,这个是十分基础的数据结构技巧,然后在答案线段树上修改一下。
区间弹数:由于我们记录了入栈时间,所以我们删完后用可持久化线段树查出当前入栈之前的栈顶的信息即可,然后在答案线段树上和可持久化线段树上修改一下。
时间复杂度
空间复杂度
期望得分: