昨晚疯狂掉分的第四题，其实比第三题还简单……
搞不懂cf又不按套路出牌了……先是来一个巨简单的，让每个人都不得不去签到，随后是坑题，然后是压轴题，再然后才是普通题，难题……
题意：
给你一棵树，每次询问3个点，要你求出3个点两两构成的路径中选出两条，使得他们相交的长度最长。
思路：
这道题并不难，先求出LCA，再分类讨论一下即可，但是但是但是但是！！分类的情况会非常非常多，就图而言就有4种，还要考虑各自的位置。
必须得总结一下，不然跟着写会疯掉。
考虑让每个点为两条路径的相交点，分三种情况讨论。
而每种情况中，当两个路径各自的lca相同时，除了该点的所在的路径以外只要求出另外两个点的lca长度 – 三点lca 路径长度即可。
否则，就只剩下第三个点为另外两点的父亲这一情况,所以长度为 根节点到所讨论的结点距离 减去 非父亲结点的另外两个结点的 lca 的距离。
AC Code
#include
比赛时候用c++ 搞了一个小时还没出来，结束后用ruby写了个正则改了两次就过了…… 真的是崩溃…… 题意： ?替代任意好字符，* 替代任意数目的坏字符 思路： 正则瞎搞 AC Code good = gets.to_str.chomp pattern = gets.to_str key = pattern.strip.gsub("?","["+good+"]").gsub("*","[^"+good+"]*") rg = Regexp.new("^"+key+"$") n = gets.to_i n.times do buf = gets.to_str if rg =~ buf puts "YES" else puts "NO"…
虽然可以算得上是道水题，但作为我第一道状压DP，还是把它写入我的博客。
觉得这道题作为入门题是极好的，比网上说的什么矩阵的好理解的多！！
因为几乎只涉及了状压
特别想感慨一句，dp真的是个优美的暴力啊……
题意：
有几门课的作业，分别给出截止时间，完成所需时间，没拖一天扣一分，问最少扣多少分，并输出写作业顺序。
思路：
总的思路是对于每一个状态，都进行课程的枚举，并计算花费时间，拖作业时间，从而进行状态转移，每次状态转移都使拖作业的时间最小即可。
不是暴力？？但是真的很优美！
课程数很小，只有15门，因此状压无压力。
AC Code
#include
遇到的第二道哈夫曼树，这个哈夫曼树有些特别，当你将两个结点组合的时候，你只需要付出权值较小的花费。
简单说，结点权值组合的时候并不会产生新的结点！！
这就可以完全摒弃优先队列，直接用数组实现以求更为高效。
上次意外地发现两个队友都不会哈夫曼树……真是惊了……
题意：
有几堆石头，要你将他们堆成一堆。两堆石头堆成一堆的花费是石头堆较小的石头数量。q个询问，每次询问限制一堆石头，被其他石头合并的次数。
思路：
这道题，若是转化成图来说就是一个k叉哈夫曼树，然而不会产生新结点，也就是说所有结点的权值和位置都已经可以直接求得了。
将他降序排序，每次将同一层的权值乘以他的深度就是该层的花费。
注 : 下表很容易爆 int 自己想想很容易想到……
然而RE了好几发……
AC Code
#include
这是我在比赛中写的第一道尺取，这也算是一道很明显的尺取题，但是看了其他人的题解都说司马stl……
实际上代码还是我短很多……
但是第一次的尺取搞得我WA了7发，其中忘记排序4发……
总的来说还是不熟练吧……
题意：
给你两个序列分别为n,m个，和位置差，要你求出有多少个起始位置，使得从这位置开始后连续的m个元素与第二个序列相同。不要求顺序。
思路：
尺取，用一个map记录第二个序列各个元素的序列，再用一个map在尺取途中记录元素个数，只要小于原map的元素个数就可以继续往后取，最终结果必然是取得数目与m相同，每次取完判断一下即可。
AC Code
#include
老实说有点崩溃，一场训练赛，3道dp都没出，两道还是全世界都A了 毫无疑问，又落后一截…… 实在不明白他们的dp为什么这么6…… 题意： 给你一个序列 ( a_1 a_2 a_3 a_4 …… a_n ) 要你求相邻两个元素在矩阵中的数值和。 矩阵已给定，但是如果序列元素为负数，则可以为任意元素。 思路： 渐渐觉得dp就是暴力…… 四种情况 ary[i-1] < 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i – 1][k] + mat[k][j])ary[i-1] < 0 && ary[i]…
这个倍增算法看得我是真的难受。
其实我觉得这个算法是并不难的，他的倍增原理我最开始在知乎上看到的文章就看懂了。
主要是OI大佬精简的厉害，很多地方真的难以理解。还有基数排序上。
强烈强烈强烈强烈建议在学后缀数组之前先去学一学基数排序，就算没写，但必须看懂他。对基数排序了解越深，倍增算法越好理解。
附上倍增算法详细注释解剖
#include
坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑！！！！！！！！！
套着二分图外套的DP题！！！！
连续栽在这个类型的题上两次！！！！！！！！
一次是上次选拔赛的时候，那时候有两道题，一道是很明显的二分图，另一道稍微隐蔽一点，但是全都栽了，我以为，建了图我就是赢家，特么的根本建不出来！！！
上次就像写一篇来阐述一下某些二分图匹配的DP解法，无奈太懒了，结果今天就又栽在这里了……
题意：
给你一张二分图，要求点权相同的点才能相互匹配，而且每个匹配有且必须要有一个权值不同的匹配与其交叉，问最大匹配数量。
思路：
很容易想去匈牙利了有木有！！！但事实却是，dp求解。 思路如下：
假设我们要考虑的状态是第一行n位置，第二行m位置，且已知之前的所有最佳状态。考虑把，n，m交叉的匹配加入到匹配集合中。那么 如果两点的权值相同则不符合要求，否则，分别向前查找各自的匹配，再与这个状态之前的状态转移即可。
如果你还不懂，那你看一遍代码肯定能懂。
AC Code
#include