111qqz的小窝

老年咸鱼冲锋!

hdu 3078 Network (LCA)

题目链接 题意: 一棵树,给出点权,问一条树链上第k大的点权,点权可以动态修改。 思路: 暴力即可orz(数据是真的水啊。 求路径上的点的时候需要用到

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

题目链接 题意: 给出一棵树,以及三个点(可能重合),问两两组成的3条路径中,哪2条路径重合部分最长。 思路: LCA还是一下就能想到的,rmq+d

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

题目链接 题意:定义一个函数F.. (1, 4), (4, 7), (9, 12) Its continuous sequences are: * * * * * * erfen . erfen 题目描述得很烂..看例子把..大概就是:如果字符串y在字符串x中出现n

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

hdu 4123 题目链接 题意:一棵树,定义d[i]为点i到树上某点的最大距离。。。给出若干查询,每个查询一个x,问最多能有多少点满足这些点中,最大的d与

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

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

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

hdu2874题目链接 题意:给一个森林,问两点的最短距离,或者输出两点不联通。 思路:最最重要的一点是:添加虚点! 最最重要的一点是:添加虚点!

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

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

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在线求解。 代码部分参考了:参考代码 感觉实现得很巧妙。。。 把

hdu 4122 Alice's mooncake shop(rmq)

hdu2142题目链接 题意:有n个订单和可以在m小时内制作月饼 接下来是n个订单的信息:需要在mon月,d日,year年,h小时交付订单r个月

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

poj 3368 题目链接 题意:给出n个非减的数a[i],求区间[l,r]中出现次数最多的数的出现的次数。 思路:由于数列非减,那么相等的数一定相邻。很容易

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

poj2452题目链接 题意:给你一组数a[n],求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。 思路:大概能想到是rmq,然后想出了一个错

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

lightoj 1081 题目链接 题意:和上一道一样,但是由于size变成了500,如果按照之前的做法会tle + mle… 很容易发现,由于是方阵,长宽是相等的,所以有一维

poj 2019 Cornfields (二维rmq)

poj2019题目链接 题意:给一个方阵,k个查询,每个查询求某个方阵的最大值和最小值之差。 思路:二维rmq.同时用到最大值和最小值的话可以把

hdu 2888 check corners (二维rmq模板题)

hdu2888题目链接 题意:问某个矩阵内的最大值,并且问最大值是否是在四个角中出现。 思路:二维rmq.需要注意数组稍微开大1就会MLE,因为

BZOJ 1636: [Usaco2007 Jan]Balanced Lineup (RMQ模板题)

1636: [Usaco2007 Jan]Balanced Lineup Time Limit: 5 Sec Memory Limit: 64 MB Submit: 680 Solved: 493 [Submit][Status][Discuss] Description For the daily milking, Farmer John's N cows (1 <= N <= 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking