题目链接 题意： 一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。 思路： 暴力即可orz(数据是真的水啊。 求路径上的点的时候需要用到LCA /* *********************************************** Author :111qqz Created Time :2017年07月31日 星期一 01时12分54秒 File Name :3078.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

题目链接 题意： 给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。 思路： LCA还是一下就能想到的，rmq+dfs在线求。 然后我开始分情况讨论，讨论了一年也没讨论完，哭哭 结论是：求出三个lca，并取深度最大的那个，就是我们要的三岔路口K，然后分别求出K到a，b，c三点的路径长度，取最大值+1就是答案。 所以我的问题在于，没有试图往一般性的方向考虑，以为讨论一下就可以了... 这大概就是所谓的猜结论？ 感性的理解的话，LCA越深，意味着另一个点到LCA的距离越远，也就是相交的路径越长 但是我的话，估计还是很难在短短不到一个小时内得出这样一般性的结论orz... 这大概就是数学方面的天赋差距 …

题目链接 题意：定义一个函数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次，那 …

hdu 4123 题目链接 题意：一棵树，定义d[i]为点i到树上某点的最大距离。。。给出若干查询，每个查询一个x,问最多能有多少点满足这些点中，最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。 思路：可以三遍bfs处理出所有点的d... 由于不能排序。。。所以就是尺取+rmq.... 然而神Tm TLE..... 这复杂度还TLe... 结果最后发现是。。。log运算的常数太大被卡。。。 所以做法是先预处理一下。。。嗯。。。。 珍爱生命，远离log! 珍爱生命，远离log! 珍爱生命，远离log! /* *********************************************** Author …

zoj 3195题目链接 题意：求树上三点的最短距离。。。 思路：两两求，和除以2. 因为忘记初始化p=0..WA了将近两个小时。。。？ 妈的智障。 /* *********************************************** Author :111qqz Created Time :2016年05月21日 星期六 14时44分39秒 File Name :code/zoj/3195.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu2874题目链接 题意：给一个森林，问两点的最短距离，或者输出两点不联通。 思路：最最重要的一点是:添加虚点！ 最最重要的一点是:添加虚点！ 最最重要的一点是:添加虚点！ 所谓虚点，就是之前假设某个不存在的点，有点类似做辅助线。 通过添加虚点，我们可以把这个森林转化成一棵树。 这样求两点的距离就可以转化成一棵树上的两点的距离。 用dis[u]+dis[v]-2*dis[LCA(u,v)]来求。 dis[i]表示节点i到新的树根节点的距离。 不联通的话就是LCA 为0的情况（0是添加的虚点，作为新的树的根） 具体添加虚点的方法是：森林中每棵树的根连边到虚点上。权值大小随意，因为最后会抵消（？） 为了知道每棵树的根，需要用到并查 …

题目链接 题意：求树上两点的最短距离？ 思路： dis[i]表示点i到根节点的距离，那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)]. 只需要求出rmq+dfs的在线方法求出lca(u,v)即可。 /* *********************************************** Author :111qqz Created Time :2016年05月20日 星期五 15时36分47秒 File Name :code/poj/1986.cpp ************************************************ */ #include …

hdu 3530题目链接 题意：给出n个数，m,k，问最大的j-i+1,使得【i,j】间的最大值与最小值的差属于[m,k] 思路：rmq+尺取。 2A. /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 16时52分03秒 File Name :code/hdu/3530.cpp ************************************************ */ #include <cstdio> #include <cstring> …

poj1470题目链接 题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。 scanf("%2s",st); 表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。 /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 15时44分12秒 File Name :code/poj/1470.cpp ************************************************ */ #include …

poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。 代码部分参考了：参考代码 感觉实现得很巧妙。。。 把树存成了有向图，dfs遇到的时候一定是第一次遇到，此时更新R. 然后第二次遇到某个点就是在回溯的时候了。 算法学习链接 /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 15时05分31秒 File Name :code/poj/1330.cpp ************************************************ …