真是哭了，今天多校的图论题，算得上是在比赛的时候的进阶题目，A了这道就能挤开一大片那种……
没A，思路错了……
题意：
给你一棵树，要你将 { 2，3，4……n } 进行划分成 k 个集合，每个集合与{ 1 }相并后 求 最小 斯坦纳树，求和的最大值。
思路：
考虑每条边贡献值，只可能是 k 与 子树结点的最小值，将贡献值与边长相乘累加后便是答案。原因yy即可。
一边dfs得出每个结点的子树结点数，复杂度 O ( n ) 。
AC Code
#include
今天做的不太一样的状压，从去年的专题找的，看到学长并没有写是已经写过了么？ 可能是因为跟图论相关的原因吧。 题意： 给你一个简单图，让你找出简单环的数量。 附 ： 简单环就是没有重边和重点的环。 点数为 19 。 思路： 19个点，一般很容易想到状压和二维……根据数据猜算法？ 事实上我是没有想到二维的 dp[ s ] [ p ] 表示 s 集合 p 为当前位置的边数 ，初始对每个状态 dp [ 1<< i ][ i ] 设置为 1 对于每一个状态，固定的从最小的一位 1 作为起点，从这个起点开始扩散，如果能回到这个起点，就进行计数。 因为对于一个环，枚举起点和终点的话，会存在起点到终点，和以终点为起点的情况。 比如说 1-> 2 -> 3 ->1 和…
前几天刚写了一道状压DP入门题，结果这次就遇到了，在比赛最后一点时间一眼看破，无奈只有想法，写不来……
不过赛后尝试写的时候遇到了一个自己不会的问题，也就是说假如比赛的时候开了这道题，我也会一直卡着。
题意：
给你很多个行李的位置和起点的位置，要你把所有行李搬运到起点，一次只能搬一个或者两个，花费是距离，求最小花费。行李最多24个。
思路
状压dp，对于每一个状态，我们通过dp维护其最优。
因为这里的拿取行李是与顺序无关的，那么，我通过从小到大枚举状态，在保证我当前状态最优的前提下，由我当前状态拓展而来的状态只要通过比较就可以达到最优好暴力
所以我通过枚举，找到第一个它能够搬运的行李，每次都拓展这个状态即可。
AC Code
#include
题解 2-SAT 一眼题，但是很遗憾，我之前刷的专题里面没有输出可行解的题。我不知道怎么输出可行解，我个人以为，只要染色数量等于点数就是可行解。有哪里不对的么？？ 但我至少认可了Yasola巨巨在挑程上说的拓扑排序输出可行解的说法。 传送门 题意 有n个人手中有n张卡，每个人说两句话，有一句必定为真，有一句必定为假。说了2-sat一眼题…… 两句话分别说，我自己手上是几号卡，别人手上是几号卡，保证不存在相同的陈述。 思路： 对于每两个人 i 和 j 的陈述，进行判断，如果产生矛盾，则建边。 产生矛盾是指两个的陈述，主语或者谓语有一个不同就产生了矛盾。 eg 1 号 手中有 2 号卡 < —- > 1 号手中有 3 号卡 1 号 手中有 2 号卡 < —- > 2…
好题！！！！ 这道题我整整想了一个晚上，怎么说呢，应该还是我从一开始就没想复杂，考虑得简单了，然后后面就写的很复杂了…… 其实我在写到一半的时候就突然想到我的状态转移方程是错的，然而还是抱着poj数据弱的侥幸继续写下去……然后错误的地方越写越清晰…… 题意： 一个90后都玩过的空间游戏吧，记得叫 是男人就下一百层 ，题意不是很好描述，可以自己去玩玩。 思路： 先说一下我最开始的想法，不想看的直接往下翻。 这道题我一看，诶，水题！我只要每次移动都保证当前层所花时间最少，类似记忆化搜索，一步一步推过去就能保证我的答案最优…… 首先这个思路的确是对的，但却忽略了一个细节，从我以前走过的层到我当前层，有个位置上的关系。 就是说当我每次得到当前层时间最短的时候，我必须把落下的相应位置给确定下来，否则，若存在重复的最优时间，当前下落位置不同，会影响之后的时间。这是显然的。 而我要想补救我的思路，那我必须记录所有的位置，虽然这个位置数量不会超过2，但这实现起来就很烦。 正解： 其实正解是很简单的，我只要反向思考就可以了。就是记录当前层到底层的最短时间。考虑当前层到中…
多校第一场没有怎么想的题，然而实际上是很简单的……就是题意在理解上有点绕。 题意： 给你两个序列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大，但这样时间和空间复杂度都很高。 一个与优先队列思想相似并且简单的方法就是，我们将旧集合维护有序，在这里为降序，并用一个优先队列存储两集合权值和。 首先将新集合的每个元素与旧集合最大元素(就是首位置)相加并加入队列。每次推出一个最大元素的时候，都将这个最大元素在新集合的原元素与旧集合相应元素的…