老实说，这题我在现场赛大概写不出来。 感觉还是比较需要脑洞。 题意： 一排不同重量的蚂蚁按重量排成一排玩饥饿游戏，每只蚂蚁最开始选择一个方向，左或者右，大蚂蚁吃小蚂蚁，并且使自己增加小蚂蚁的重量，如果重量相同，左吃右。 问 n 只蚂蚁，第 k 只活到最后的方案数。 思路： 直接切入正解。 首先第k只蚂蚁必须选择左边，不然只能被吃。( $n \neq k $ ) 如果想要第 k 只蚂蚁获胜，必须满足以下两个条件 1. $ weight[ max(p_1), k ] > weight[ 0, max(p_1) ) $ 2. $ weight[ 1, min(p_2) ] <= weight( min(p_2), n…
/doge薛昊老是偷我题做，最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有，这个区间DP的套路我还真没碰到过。 这是一个大区间推小区间的套路。 题意： 小明要在某层楼的各个老师那里交一大堆作业，但是小明来早了，老师还没上班，他站在这层楼的最左边，告诉你每个老师的上班时间，最后要在某个给定位置下楼，问最少时间。 思路： shit，完全是看博客，看代码敲的。 一个比较困难的点在于给定离开地点，算了，不装了，就算取消这个条件我也写不来…… 明确可以用dp求解，首先按照位置优先开门顺序次优的顺序排序，设三维数组 $dp[l][r][k]$。 当 $k=0$ 时，表示只有 $(l,r] $ 区间内的作业没有交。 而 $k=1$ 时，表示只有 $[l,r) $ 区间内的作业没有交。 而我们的其实状态$dp[1][n][0/1]…
前几天的上分场的树形DP 我敢说思路和我当时想得已经一模一样了，还有半个多小时的时候，gou bi 带鱼说把题目给他看一下，然后立马得出，树形DP解不了，肯定是树分治！ 当时我在一个子问题上走不出来，于是就信了，然后开始划水…… md 题意： 给你一棵树，要你给树上的每一个节点赋值，赋值存在范围，再给你一个特殊值，除开特殊值意外的数值赋值次数不限，但是特殊值的相邻节点的值不能是特殊值，也不能是比特殊值大的值。 问方案数。 思路： 首先值得注意的是，特殊值赋值次数不超过10，这是一个重要突破口，这使得树形DP的解法存在可能性。 简单说就是在每个节点都保存当前节点为根节点的子树分别含有 [ 0, 10 ] 个特殊值的方案数。 但这还不好决策转移，我们还需要对当前值的范围作为状态进行判断。 我在比赛中只用了，当前值为特殊值，和不是特殊值两个状态，但是现在看了其他人的代码，发现三个状态更容易。 当前节点赋值小于特殊值，大于特殊值，等于特殊值。这样就很好转移，不细说，看代码都能秒懂。 我在比赛时候被卡的子问题是这样的，对于计算当前子树的特殊值数量为 n 的时候…
大概是第5次写矩阵快速幂…… 这道题在DP还是矩阵上都是属于简单范畴……，但没想到用DP就很烦…… 感觉矩阵加速还是挺有必要学一下的…… 顺带学了一下什么叫分数取模用逆元 题意： 让你抛 k 次 硬币，求上面朝上的次数为偶数的概率。 单次正面朝上的概率为 ( \dfrac {q} {p} ) 思路： 令 dp [ n ] [ 0 ] 表示抛了 n 次后，朝上次数为偶数的概率，dp[ n ] [ 1 ] 则表示奇数的概率。 得转移方程 $ dp[n][0] = \dfrac {p-q} {p} \times dp[n-1][0] + \dfrac {q} {p} \times dp[n-1][1] $ $ dp[n][1] = \dfrac…
一道二分图性质的应用 + 树形DP ？ 看博客里都说是树形DP，但我觉得应该是树上前缀和更加合适一些 题意： 给你一个图，让你删除一条边，使得剩下的图是二分图。 输出可删边数并顺序输出边的序号。 思路： 首先你必须知道判定二分图的充要条件 —— 不存在奇环。 如果只是让你判定二分图的话，倒是随便搜一遍就可以解决的问题。 但是这里必须让你删掉一条边…… 写不来……感觉不好写，最后无奈去看题解了…… 先整理一下判断思路： 1. 如果不存在奇环，那么原图本来就是一张二分图，每一条边都满足条件 2. 覆盖了所有的奇环，并且不能覆盖偶环的所有边 为什么同时不能覆盖偶环，这个我还真没想到，但是在纸上画一画就是很显然的了，同时覆盖奇环和偶环的边删去后，两个环会变成一个新的环，偶数+奇数 还是奇数。所以不能覆盖偶环。 因此得出如下具体实现，随便生成一棵生成树，用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。 如果奇环数量大于 1 ，那么非树边必定不可能是满足条件的，因为非树边最多只能覆盖一个环，两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的…
AC自动机+带权字符串DP
题目本身不是很难，但在处理上有点繁琐。
题意：
给你很多模式串，每个模式串都有一个权值，再给你一个限制长度，要你在限制长度内找出最短的字符串，使得权值和最大。若有多个结果，输出字典序最小的。
思路：
连AC自动机上的最短路都有了，加个权值也不是什么奇怪的事情。
这个加了权值有点像…………背包？？不是么？？
想象不到的话将背包的物品替换成一个字符试试。
但是实际上都是我瞎猜罢了，我并没有按照背包的写法去写，还是很常规的按照节点和状态添加字符，到下一节点的下一状态。
稍微繁琐一点的就是要输出字符串，但所幸数据比较小，三维空间存的下。
#include
AC自动机+spfa最短路
啊啊，明明AC自动机还有最后一题，今晚怕是写不完了，今天写的还有两道没写题解。
最后一道AC自动机与这一题有相似之处，是这一题的强力加强版本。
先把这题给解决了
题意：
给你很多碱基串，不同碱基串在前后缀相同的条件下可以重叠，要你求出最短的碱基串，包含所有给定串。
思路：
AC自动机上状压SPFA，也可考虑TSP的模型。
还是属于比较基础的，连我都可以不看题解写出来的题目。
#include
AC自动机 + 变进制状压DP
看题目的 discuss 都说会卡数据，但我还是 1500ms A了。虽然变进制的思路并不是我的……
最近有点懒得写博客了呀
题意：
还是基因碱基对背景。
给你几个模式串，再给你一个匹配串，允许你对匹配串重新排列，要求重新排列后跟模式串匹配的最大数量。
思路：
如果再加个权值，那就是DP套DP了，（误……
本质上还是一个计数DP，考虑状压，但是给定的匹配串长度上限为 40 ，如果开一个状态+节点的 5维数组，会炸内存。
考虑到将节点的 4 维压缩，因为 40 的实际状态数最多是 4 个碱基数量相同的时候。
也就是( 10 \times 10 \times 10 \times 10 )，内存与复杂度均可以承受。
AC Code
#include