HDU 1394 Minimum Inversion Number

题意

求环形数组的最小逆序数。

思路

如何求逆序对请参考hdu 1394 求循环串的最小逆序数 暴力法 线段树 归并排序3种方法(hnust_xiehonghao)

本题使用暴力方法也可以通过,但前提是需要知道一个结论:如果是0到n的排列,那么如果把第一个数放到最后,对于这个数列,逆序数是减少a[i],而增加n-1-a[i]的

代码(线段树优化方法)

 

HDU 1698 Just a Hook

题意

给出一个数列,每次操作更新一段的值使它们全部为给定值,问你历经N次操作之后,数列所有数加和是多少。

思路

典型的线段树加上懒惰标记来实现区间更新。因为好久没写线段树,拿这个题重温一下。

懒惰标记的工作原理可以参照:ZOJ 3686 A Simple Tree Problem

代码

 

ZOJ 3686 A Simple Tree Problem

被这道题玩得相当惨。。。这道题是一个DFS+线段树的题。

首先这个题是在一棵传统树上面进行大规模的区间读写操作,这是线段树的玩法,但是怎么玩呢?
这个时候DFS就派上用场了,我们通过DFS得到DLR遍历,把dfs时进入一个节点是时间记下来,出去一个节点的时间记下来,就可以得到这个节点的子树在DLR遍历中的区间的开始与结束标号,这样就相当于把2维的树降到一维了。
之后得到了一个一维的数组,就可以开线段树,这里涉及区间更新,还要加开懒惰标记。
这种把树压成线然后再搞是一种很常用很好的姿势!

其实这道题卡死我的就是懒惰标记这里。我原来一直在用zkw线段树,但是因为是自下向上操作没有递归,所以我就根本不知道怎么下手写懒惰标记了,鼓捣2天未果,orz各路大神的适配zkw线段树的懒惰标记是给rmq准备的,不适合这个题,没办法研究递归版本了。

递归版本的话,实现懒惰标记的思路就是:
1.更新时,如果发生了目标区间与当前区间相交的情况,首先把当前节点的懒惰标记下传给下一层,然后再去更新下一层,更新完下一层后,用更新好的下一层更新自身。如果目标区间完全包括当前区间,这个时候就不用往下走了,首先更新自己的值,然后更新自己位置的懒惰标记。
2.查询时,如果目标区间和当前区间相交,这时候需要下传当前节点的懒惰标记,然后进入下一层接着查询,如果目标区间完全包括当前区间,直接更新答案。
3.下传时,我们只操作当前节点的子节点,不可以操作当前节点(否则就重复操作啦),注意我们只下传了一层,所以不仅要操作下面一层的值,还要操作下面一层的懒惰标记,同时清空当前节点的懒惰标记。

POJ 2828 Buy Tickets

这个是灵活使用线段树了,把线段树当作路径,一边整理有多少个空位,一边按着这些数据快速地插入节点。

注意这个题正难则反的思想,反着来看这个请求序列,是可以做的,正着处理就坏事了,所以当卡题的时候不妨试一试把当前的思考/阅读方向反过来,也许会有灵感。

我已经很尽力地优化了,1600跑过,只能说那些几百跑过的大神真是强,无法比肩。

HDU 1166 敌兵布阵

题意

求区间和,单点修改。

思路

典型的线段树问题,线段树的实现原理这里不再赘述。

代码

这份代码使用了zkw的非递归堆存储自底向上式线段树,实现难度较低。

 

HDU 1556 Color the ball

基于zkw线段树自己改造了一个,其实可以爆过去,时间还更少,真是邪乎。

HDU 1754 I Hate It

数组开的比较大,清数组会消耗很多时间所以跑了1000多。

基于zkw版线段树实现。

HDU 1710 Binary Tree Traversals

这道题是已知DLR和LDR,求LRD。

DLR(先序)具有的特点是根节点一定在它连接的子树的左边,子树的根节点一定在子树的子树的左边,LDR的特点是投影,就是下面这个图:34fae6cd7b899e518e0d6d3640a7d933c8950d14

 

 

接下来就拿样例举例子 :

C57-1005-1

这个的DLR是1 2 4 7 3 5 8 9 6
这个可以分段看,首先是 1/247/35869,然后可以发现1是root,247又可以分成2/47/~三段(~表示没有节点),在这里2是这个子树的根,35896又可以分为3/589/6在这里3是右边子树的根,589是左半部分,6是右半部分,就这样一直分下去就可以发现DLR的特点了,而这种特点正是因为DLR是DFS生成的。

然后看LDR,4 7 2 1 8 5 9 3 6
这个也是分段,首先472/1/85936,你会发现如果知道根的话,那么这个根左边有什么右边有什么都是可以从LDR里看出来的。

所以我们这个题就可以先找到总根(DLR第一位),然后在LDR里找到根的位置,想办法确定左右肢的元素个数,然后回到DLR里找到左右肢的根,分别把它们当作总根递归下去,这样我们就能还原出树的全貌了,而这个题更简单一点,你只要以DRL的顺序这么递归,把每一次找到的根都压入stack里,最后再逐个弹出输出,正好就是LRD了。

如果已知LRD和LDR,是可以求出DLR的,方法和这个差不太多。但是如果知道DLR喝LRD,想求LDR做不到,LDR不止一个解。

Scroll to top