Orac训练记录

我已经做了213


Growing Trees 我一开始傻逼了写了一大坨splay,然后发现实际上你把他们一开始sort好,那么会影响这个有序表的有序性的只可能是相等的数字的一部分被加了,那么不妨把被加的部分挪到后面去,这样就可以了。用线段树维护这个表,查询在树上走,时间复杂度O((n+T)\log n)

Jewel Heist 考虑y=1的情况,很容易发现选取的一定是一个区间,那么y不等于1咋做呢?枚举上限呗,想象一条扫描线从下往上,经过的点都必须要选,那么这又是一个区间,问题是,怎么求出这个区间?考虑本题最特殊的性质,不包含全部的颜色。那么只需要考虑任意一种颜色,把它剔除掉即可,用set维护前驱后继。

Shopping Malls 方案数=不考虑障碍点方案-包含任意数量(不能为0)障碍点的方案数,后者可以利用容斥原理计算

Handing Writing 由于S非常小,所以我们可以DFS出每个手势的所有可能字母,然后对手势再在Trie树上进行走即可。

Bungling 考虑到这是一张有向图,我们把它缩点,由于每个点都只有一个出边,显然可以把整张图缩成基环树森林,那么问题就是取k条点不相交的链,使得他们的长度之和最大。我们考虑两个环合并在一起需要2的代价,三个则需要3的代价,所以跑一次树DP,记录每个点为根的情况下他的子树内最深的点是啥。维护一个堆,每次把堆顶提出来和之前的环相连(在我们脑海里,不用实际去做),然后暴力删掉,每个被删掉的点扩展其他儿子进堆即可。每个点只会出现一次,所以时间复杂度O(n\log n),事实上那个\log可以用桶替代掉但我懒得搞了QAQ

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注