Posts

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

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

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

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

poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。

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

poj 3368 题目链接 题意：给出n个非减的数a[i]，求区间[l,r]中出现次数最多的数的出现的次数。

poj2452题目链接 题意：给你一组数a[n]，求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。

hdu3193题目链接 题意：给出n个price 和distance，找到一个集合，集合中的每对在全集中找不到比他price和distance都要小的元素。小于是严格的。

1首先先生成三个程序： 2$ g++ a+b.cpp -o a+b 3$ g++ a+b2.cpp -o a+b2 4$ g++ make.cpp -o make 5然后生成数据 6$ ./make > in.txt 7然后运行两个程序 8$ ./a+b < in.txt > out.txt 9$ ./a+b2 < in.txt > ans.txt 10最后对拍 11$ diff out.txt ans.txt 12输出的结果可以man diff查阅一下相关文档中关于输出含义的内容 13注：上面的$都是命令提示符，复制粘贴时不需要

lightoj 1081 题目链接 题意：和上一道一样，但是由于size变成了500，如果按照之前的做法会tle + mle…

poj2019题目链接 题意：给一个方阵，k个查询，每个查询求某个方阵的最大值和最小值之差。

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

hdu3183题目链接 题意：n位长的数字串（n<=1000)，删掉m个（m<=n），使得剩下的数字串表示的数字最小。 忽略前导0.

1636: [Usaco2007 Jan]Balanced Lineup # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 680 Solved: 493 [Submit][Status][Discuss]

1689: [Usaco2005 Open] Muddy roads 泥泞的路 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 311 Solved: 227 [Submit][Status][Discuss]

题目链接：hdu4513 题意：给出一个n的数的序列，求出一个最长的回文字串，并且满足从[l,mid]单调增（非严格单调，可以相等），[mid,r]单调减（同样是可以相等）

poj 3294 题意：先做个简单替换，然后求替换后的字符串的最长回文串，以及这个最长回文串的开始和结束位置。 思路：manacher。需要注意的是，返回下标的时候如果字符串长度为偶数，那么中间是没有字符的，需要特判一下（我的做法是 left+(ans%2==0)）。

poj3974 题意：求最大长度的回文字串。 思路：manacher裸题，用来练习算法。

题目链接 题意：求一个字符串中的最长回文串。 思路：昨天武大校赛遇到了一个manacher算法的题。。。我竟然听都没听过。。。