Orac训练记录

我已经做了276


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

Mobile Construction Set 考虑暴力算法,枚举要改动的地方,然后暴力修改,时间复杂度O(n^{3}),不难发现,一旦我们知道了要拿哪棵子树,那么对于其他点的修改操作的结果一定是确定下来的,而被修改的点显然是一条链上的点,那么直接遍历一遍,边做边走即可。时间复杂度O(n^{2})

Bouncy Ball 挺简单的一道题,首先我的思路启发来源于拆数问题以及第k大查询方式,那么我们设计这样的方程,f[i][j]表示和为i,最后一次用的数为j的方案数,这个可以利用前缀和优化转移做到O(n^{2})的时间复杂度,然后为了输出方案,我们肯定要考虑枚举第一位,然后如果不够的话,用k减去这个方案数,继续做。然后考虑第二位,再做一次DP,以此类推。时间复杂度O(n^{3}\times log n)

Super Maria 一开始傻逼很naive地设了个状态结果SB调了两天,后来发现有锅。。。实际上只需要去设f[i][0/1]表示第i个传送器是先向左走还是向右走就行了。转移的时候直接暴力枚举交界点,因为交接点一定在两个传送器之间,那么每个金币只会被枚举一次。调试技巧:发现自己WA了以后,先静态查错,如果还是不对,删掉重写,重新思考思路,找找思路的BUG,不要一直以为是自己傻逼写错,实际上很可能是傻逼想错。边界要想好。

Banarby's farm 考虑单调栈优化建图,对于每一列or行,考虑先从左往右做,每个点加入栈,推掉比他小的,推的时候连边,这样为什么不会错?因为如果之前有比它大的,早就把他推掉了,这样边数可以保证是O(NM)的,然后跑堆优化dijkstra即可。

EastConnex 容易发现,答案一定是只走一条高速公路,为什么?因为如果走两条的话,你完全可以把水平方向平移到另一条,那多一条高速公路只会给答案带来正增量,所以显然只走一条高速公路最优。不难发现计算的公式为\left | A_{y1}-A_{i} \right |+\left | X_{1}-X_{2} \right |\times Cost_{i}+\left | A_{y2}-A_{i} \right |,不妨令y1<y2,那么有三种情况,分别为\left\{\begin{matrix}A_{y1}-A_{i}+\left | X_{1}-X_{2} \right |\times Cost_{i}+A_{y2}-A_{i}\\A_{i}-A_{y1}+\left | X_{1}-X_{2} \right |\times Cost_{i}+A_{y2}-A_{i}\\A_{i}-A_{y1}+\left | X_{1}-X_{2} \right |\times Cost_{i}+A_{i}-A_{y2}\end{matrix}\right.,第二种情况就是比较裸的线段树/ST表,一三两种情况实际上等价于求某一段区间内的所有线段所构成的凸壳,这个我们可以采用凸壳线段树维护。时间复杂度O(Q\log^{2} n)

Organisational Enlightenment 直接可持久化权值线段树就行了,时间复杂度O(q\log n)

White Collar f[i]表示前i幅画的最大收益(第i幅画必买),那么考虑指针ji倒退回去,遇到一个点,看下有哪些守卫的起点在这里,并且右端点覆盖了i,那么就要考虑贿赂,那么这样为什么没有错呢?考虑一个守卫看守第i幅画,如果他的左端点在[j,i],那么显然已经被贿赂过了;如果他的左端点在[1,j),那么不关第i幅画的事,因为f[j-1]已经把这个守卫给贿赂掉了,不然怎么买的第j-1幅画。这样就还剩一个问题,他的贿赂的价钱随着j的左移在变,怎么维护呢?很好维护。考虑维护两个指针,第一个指针扫描按照start排序的守卫数组,第二个指针扫描按照end排序的守卫数组,每次考虑在i之前的守卫,他对bribe的贡献是一个前缀,直接区间减法。考虑因为i的增加而end不能用的守卫,把它加上就行。这样我们就可以用扫描线+线段树来优化这道题了,时间复杂度O(n\log n)

Sushi selection 首先有个很显然的observation就是,至多有一家商店只买一部分寿司,其他全都要么不买要么全买。证明很容易用反证法证明。这样我们就有了一个比较naive的idea,枚举哪家店只用一部分寿司,其他的做背包dp,这样时间复杂度是O(T^{2}M)的,显然会超时。考虑一个稍微不那么暴力的做法,我们不难发现,每次只是把dp的某一层删去了而已,那么,我们可以对前缀做一次dp,后缀做一次,直接合并就好,时间复杂度O(TM+NM),依然不满足要求。那么我们在想,导致多了一个M的原因在哪?在于我们要合并前后缀,那如果只存在一个,是不是就很完美?但是我们遇到了一个问题,每次拿出来,就需要重构整个数组,这样就会使算法变得很慢。我们考虑用分治去解决,记Solve(L,R)表示除了[L,R]以外,所有的商店已经被dp好的答案。显然商店的顺序并不影响答案,所以这样做是OK的。那么每次就先把左边做dp,然后跑Solve(mid+1,R),要么就是反过来。在元节点的时候考虑合并答案。这样做时间复杂度均摊下来一定是O((n+mt)\log t)的,巧妙地利用了分治的思想以及原题性质的“顺序不影响答案”特性,我们这么一道难题就得到了解决。

发表评论