多校第一场没有怎么想的题，然而实际上是很简单的……就是题意在理解上有点绕。 题意： 给你两个序列a和b，每个序列中的每个元素各不相同，且分别为 [0,num) 要你求满足如下函数的数量。( f ( i ) = b_{ f(a_i) } ) 思路： 一般人一眼就可以看出是一个递归的函数过程。 每次当我们知道了 ( f(i) ) ,我们就可以很顺利地得出 ( f(a_i) ) ，知道了 ( f(a_i) ) ,我们就可以很顺利的知道 ( f( a_{a_i} ) ) 又因为序列的特性，则对于这个函数，在a序列上必定会存在一个环。 而相应的，在a序列上的一个环与b序列上的元素相对应起来，只有在b序列上存在a序列环的因子才能成立。这个真的只要随便意淫一下就可以了，你要我证明我想还真有点烦 因此只要求出两个序列的环，对于每一对a序列的环与b序列的环，如果b序列环是a序列环的因子，则加上b序列环长度，因为对于a序列上的一个固定点，每一个b序列环上的点都可以对应与a序列固定点，且对应关系必不相同。 AC…
多校第一场的恶心题……因为前几天补题数量太多，博客一直没写，现在补上……
这道题我整整写了一个下午+晚上，mmp，一方面是题目本身恶心，另一方面也反映了我的脑子问题。
题意：
给你指定数量的小写字符串，让你把字母，转化成数字，也就是说 a-z 各自对应 0-25。要求所得数字和最大。
同时转化出的数字不能出现前导零。
思路：
将每个字符的贡献转化成一个25进制的数，用一个 26× 1e5 的数组存储，将其进行排升序。
再是考虑前导零的情况，反向遍历找到第一个不存在前导零的数字标记一下即可。
AC Code
#include
多校第一场的小锅，因为就算给我时间我也写不出来的题……算是小锅吧，还有三个大锅在背上。 开头先说一声，薛昊这个坑比，woc，跟我说这里的k小生成树是就是先取一个最小的，连上每一条边…… 然后我在用优先队列的时候我就真的先推小的…… md debug好久才发现……醉了。 题意： 给你一个仙人掌图，要你求出前k小的生成树。将之与k相乘求和 mod 2 ^ 32 思路： 如果是一个一般图，那问题将非常困难，但他是一个仙人掌图，对于一个生成树来说，整张图的桥必定不能删掉，所以必须从每一个环中删掉一条边，而我们删掉的边要求前k大。 将每一个环的边作为集合，多个集合合并，求出前k大，这是一个经典问题。 方法是对每两个集合两两合并，将两个集合的边各自相连，用优先队列推出前k大，但这样时间和空间复杂度都很高。 一个与优先队列思想相似并且简单的方法就是，我们将旧集合维护有序，在这里为降序，并用一个优先队列存储两集合权值和。 首先将新集合的每个元素与旧集合最大元素(就是首位置)相加并加入队列。每次推出一个最大元素的时候，都将这个最大元素在新集合的原元素与旧集合相应元素的…
昨晚疯狂掉分的第四题，其实比第三题还简单……
搞不懂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