hdu 3790 题目链接

题意：给出n个点m条无向边，每条边有一个距离和一个花费。给出s,t。问从s到t的最短距离以及最短距离时的最小花费。当有多个距离最短的方案时，选取花费最少的。

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

/* ***********************************************
Author :111qqz
Created Time :2016年05月21日 星期六 14时44分39秒
File Name :code/zoj/3195.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3 …

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. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。

scanf("%2s",st);

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

poj1330题目链接

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

代码部分参考了：参考代码

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

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

poj 3368 题目链接

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

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

poj2452题目链接

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

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