111qqz的小窝

老年咸鱼冲锋!

hdu 3078 Network (LCA)

题目链接

题意:

一棵树,给出点权,问一条树链上第k大的点权,点权可以动态修改。

思路:

暴力即可orz(数据是真的水啊。

求路径上的点的时候需要用到LCA

 

 

codeforces #425 D. Misha, Grisha and Underground (dfs+rmq在线求LCA,讨论了一年)

题目链接

题意:

给出一棵树,以及三个点(可能重合),问两两组成的3条路径中,哪2条路径重合部分最长。

思路:

LCA还是一下就能想到的,rmq+dfs在线求。

然后我开始分情况讨论,讨论了一年也没讨论完,哭哭

结论是:求出三个lca,并取深度最大的那个,就是我们要的三岔路口K,然后分别求出K到a,b,c三点的路径长度,取最大值+1就是答案。

所以我的问题在于,没有试图往一般性的方向考虑,以为讨论一下就可以了…

这大概就是所谓的猜结论?

感性的理解的话,LCA越深,意味着另一个点到LCA的距离越远,也就是相交的路径越长

但是我的话,估计还是很难在短短不到一个小时内得出这样一般性的结论orz…

这大概就是数学方面的天赋差距把…T T

 

 

codeforces 123 D. String (后缀数组+两次二分得到区间+rmq)

题目链接

题意:定义一个函数F..

For exampe: F(babbabbababbab, babb) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are:

  • (1, 4)

  • (4, 7)

  • (9, 12)

  • (1, 4), (4, 7)

  • (4, 7), (9, 12)

  • (1, 4), (4, 7), (9, 12)

    erfen


erfen
题目描述得很烂..看例子把..大概就是:如果字符串y在字符串x中出现n次,那么F(x,y)=n*(n+1)/2

现在给一个字符串,求所有的F(s,x)的和,x为字符串的所有不相同的子串.

 

思路:由于刚刚写了一个求一个字符串所有不同子串个数的题目...于是就想到了后缀数组...

写完之后观察height[i].如果把height[i]看成底在x轴上的第i个矩形的高的话,n就是一段连续的矩形的长度.

 

然后...暴力会tle 48

题解说单调栈...但是单调栈之后还要线段树or并查集? (by 羊神)

...不会啊orz

最后用了二分+rmp过掉的

大概就是两次二分得到一个矩形的区间,和whust2016 #1的那道题有点像.

hdu 4123 Bob’s Race (树的直径+尺取+rmq)(珍爱生命,远离log)

hdu 4123 题目链接

 

题意:一棵树,定义d[i]为点i到树上某点的最大距离。。。给出若干查询,每个查询一个x,问最多能有多少点满足这些点中,最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。

思路:可以三遍bfs处理出所有点的d…

由于不能排序。。。所以就是尺取+rmq….

然而神Tm TLE…..

这复杂度还TLe…

结果最后发现是。。。log运算的常数太大被卡。。。

2016-07-17 23-19-46 的屏幕截图 2016-07-17 23-26-58 的屏幕截图

 

所以做法是先预处理一下。。。嗯。。。。

 

珍爱生命,远离log!

珍爱生命,远离log!

珍爱生命,远离log!

 

 

 

zoj 3195 Design the city (lca,dfs+rmq)

zoj 3195题目链接
题意:求树上三点的最短距离。。。
思路:两两求,和除以2.
因为忘记初始化p=0..WA了将近两个小时。。。?
妈的智障。

hdu 2874 Connections between cities (添加虚点,并查集+LCA(rmq+dfs))

hdu2874题目链接

题意:给一个森林,问两点的最短距离,或者输出两点不联通。

思路:最最重要的一点是:添加虚点!

最最重要的一点是:添加虚点!

最最重要的一点是:添加虚点!

所谓虚点,就是之前假设某个不存在的点,有点类似做辅助线。

通过添加虚点,我们可以把这个森林转化成一棵树。

这样求两点的距离就可以转化成一棵树上的两点的距离。

用dis[u]+dis[v]-2*dis[LCA(u,v)]来求。 dis[i]表示节点i到新的树根节点的距离。

不联通的话就是LCA 为0的情况(0是添加的虚点,作为新的树的根)

具体添加虚点的方法是:森林中每棵树的根连边到虚点上。权值大小随意,因为最后会抵消(?) 为了知道每棵树的根,需要用到并查集(其实根是随便定义的,但是森林中每棵树只能一个点和虚点相连不然就出现环了,所以需要用到并查集)

以及了解了(?)并查集的非递归的路径压缩写法。。。?

缺点是速度更慢,优点是不会爆栈。。。

还有需要学习一下按rank合并和按size合并的进阶并查集。。。?

以及:RE了好多次是因为。。。添加了虚点0,所以各种下标都应该是从0开始,初始化清空的时候忘了(从0开始)清vector…导致多组数据一直往edge[0]里面添加边。。。然后就炸了(手动微笑)

 

 

 

 

poj 1986 Distance Queries (lca,在线做法dfs+rmq)

题目链接
题意:求树上两点的最短距离?
思路: dis[i]表示点i到根节点的距离,那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)].
只需要求出rmq+dfs的在线方法求出lca(u,v)即可。

 

 

hdu 3530 Subsequence (尺取+rmq)

hdu 3530题目链接

题意:给出n个数,m,k,问最大的j-i+1,使得【i,j】间的最大值与最小值的差属于[m,k]
思路:rmq+尺取。 2A.

poj 1470 Closest Common Ancestors (lca,rmq+dfs,读入技巧)

poj1470题目链接

题意:求两点的lca.
思路:dfs+rmq. 读入技巧。
读入比较坑爹。。。
学会了一种新的读入技巧。

scanf(“%2s”,st);

表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。

 

 

 

 

poj 1330 Nearest Common Ancestors (lca,用dfs+rmq在线求解)

poj1330题目链接

题意:给出一棵树,求两点的lca.
思路:将lca转化成rmq在线求解。

代码部分参考了:参考代码

感觉实现得很巧妙。。。
把树存成了有向图,dfs遇到的时候一定是第一次遇到,此时更新R.
然后第二次遇到某个点就是在回溯的时候了。

算法学习链接

hdu 4122 Alice’s mooncake shop(rmq)

hdu2142题目链接
题意:有n个订单和可以在m小时内制作月饼
接下来是n个订单的信息:需要在mon月,d日,year年,h小时交付订单r个月饼
接下来一行t,s表示制作的月饼可以保质t天,每保质一天需要花费s的价值
接下来m行表示从第0小时开始在该时间制作月饼的花费的价值
求完成所有订单消耗的最小价值

思路:一开始毫无头绪。。因为读错题了。。。之后发现做月饼只能在整点做,即使是提前,也只能提前整数个小时做。 然后发现冰箱的容量是没有限制的,所以每个订单单独考虑即可。

那么对于每一个订单,我们要找到订单当天以及之前T天,这T+1天中做月饼花费最少的那天做月饼。

但是如果对于每个订单,如果每次都更新相应的价值,找一次最小值,复杂度会炸。

这里我卡了一下。。。然后发现,可以只初始化一次。虽然在不同时间做月饼的花费会因为订单时间的不同而不同,但是每相邻的两个小时之间做月饼花费的差是固定的,也就是花费的相对大小是固定的。

因此对于每个订单,我在相应的区间内找到花费最小的时间的下标,然后恢复成实际的花费(因为花费是一个等差数列,很好恢复)

由于之后给的花费是开始后的第i小时。。。那么订单不妨也转化成小时的形式。。。

注意判断闰年。。

2A,开心。

 

poj 3368 Frequent values (暴力+rmq,分类讨论)

poj 3368 题目链接

题意:给出n个非减的数a[i],求区间[l,r]中出现次数最多的数的出现的次数。

思路:由于数列非减,那么相等的数一定相邻。很容易系哪个到构造另一个数组f[i],表示从当前位置向左边延伸最多延伸几个相等的数。

f[i] = f[i-1] + 1 (iff a[i]==a[i-1])

然后查询的时候。

如果直接用ST算法查询rmq的话。。。

可能产生错误结果,原因是f[i]是从左边1到i这段连续区间里当前数出现的次数。

但是查询区间不一定是从1开始,所以查询区间内的第一段连续相等的数可能不完整。。。想了半天。。最后看了题解,发现是这部分暴力来搞。但是如果所有数列中所有数都相等,这样的复杂度就达到了o(1E10)?。。。2s应该过不了吧。。。但是所有题解都是这么写的。。。不是很懂。。。所谓的面向数据编程?

 

不过还是有启示的:分类讨论的思想。一道题未必用一种算法解。如果因为一小部分导致某算法不能用的话,不妨暴力搞之然后再用这个算法。

 

 

 

 

poj 2452 Sticks Problem (rmq+二分,需要返回最值位置)

poj2452题目链接

题意:给你一组数a[n],求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。

思路:大概能想到是rmq,然后想出了一个错误复杂度的错误思路,还直到对拍才发现==

转载一篇题解:poj2452解题报告

 

收获最大的是:

对于最大值和最小值返回val还是位置的转化竟然可以这样容易!

对于最大值和最小值返回val还是位置的转化竟然可以这样容易!

对于最大值和最小值返回val还是位置的转化竟然可以这样容易!

只要

这样一个函数就可以实现完美转化。。。

 

 

 

lightoj 1081 Square Queries (二维rmq,降维)

lightoj 108