- 博客(64)
- 收藏
- 关注
RSS订阅原创 CF383C 树状数组+dfs序
改变一下标dfs序的顺序就可以变成裸题了。这是老的dfs序但是这样子不方便修改。我们标dfs序的时候隔层标，变成这样隔层标的好处是对于题目而言的每一个修改操作，操作符相同的几个点的dfs序是连续的，这样我们就可以分两次改变两个连续区间，就是变成一道裸体了。举个例子比如我改变1的值，那么[2,3]区间是+val, [4,5]区间是-val,这就可以完成题目的要求。关于如何这个连续区间是多少，从哪里开始，你在写个简单dp维护一下就可以了int N,M;ll c[max_];il int lowb
2020-12-01 19:45:12
240
原创 洛谷P3667 [USACO17OPEN]Bovine Genomics G 动态规划
在这里，我们不二分，也不哈希，纯dp。但是复杂度真不行可以知道，什么时候一个连续区间可以作为答案呢？前N个串称之为A集合，后N 个串称集合B。假设这个连续区间是[L,R],长度是len，只有对于任意一个A中的串，在L位置与B中所有的串一一去比对，最长的相同的部分的的长度最多只能达到len - 1.上面一段话是最重要也是我们dp的基础，为什么最长只能达到len - 1,如果最长相等部分达到len也就是[L,R]整个都一样，那么根据题意来说这是一个非法的连续区间，不能够作为答案。设f[i][j][z]
2020-11-24 19:26:26
161
原创 洛谷P4043 费用流
这题的建图方式可以类比洛谷P1251我是由那个题才想到这么建的，由于每条边至少经过一次，我们又不清楚需要跑多少次，把边看成点，点与汇点相连，可是我们又不知道最大流应该是多少，直接这么连会发生错误。利用那道题的思想，每条边最少需要一次，那么就每条边看做两个点，点1和点2，点1有1的流量流向汇点，点2接受源点的1的流量，这是一个补流的过程。利用补流的过程和把边拆成两个点，我们就可以跑出来最大流是边数的最小费用。#include<iostream>#include<cstdio>#
2020-07-24 10:16:55
197
1
原创 字符串科技总结之KMP详解
定义一个东西Border的定义说人话就是对于一个字符串，前后缀相等的长度的字符串，比如BAAB，Border的有效取值是1，2的字符串，因为B=B,BA = BA，注意这里前后缀等的长度是可以让前后缀相等的地方重叠的，比如AAA，Border的可供选择的数字是1,2的字符串，但是不能取到3，Border长度必须严格小于字符串总长。KMP的next[i]数组的含义就是字符串[1,i]的最大Bborder.首先关于next[i]也就是next[i-1]延伸过来的。要找到[1,i]的字符串的最大前后缀相
2020-07-20 17:44:24
212
原创 洛谷P2255 动态规划
一种dp的解法首先对于每一个节目都是看与不看的问题，可以选择对开始时间排序后，按顺序考虑每一个节目，排序后优秀的地方在于，你考虑一个节目的时候，最优解的选取方法里，在你当前节目之前会选取到的节目都是在这个顺序之前会出现，这样就让一个无序的节目强行有序了起来。先对时间去离散化，由于数据范围是在太小，所以很暴力的可以设计dp的转移方程F[i][j][z]代表当前判断到第i个节目，第一台机子的下一次可录制时间为j，第二台机子的下一次可录制时间为z。方程有了后我们考虑转移，当前的节目可以选或者不选，如果不选那
2020-07-09 21:58:31
199
原创 CF960F CDQ分治
首先，这不是正解，甚至歪的很过分，你还要吸氧，但是我就是要发。根据题意我们可以知道首先要求转移的路径编号的转移必须是从小到大转移的权值必须从小到大一条边的终点转移到另一条边的起点，起点终点需要相同我的思路是什么呢，这是三个要求，而且头两个要求很二维偏序对不对，那么第三个要求我们可以稍稍强行转移一下然后上CDQ分支路径编号是连续的已经是由于数据顺序的问题处理掉了，我们在处理某一条路径的时候可以先把前面所有线段先处理完...
2020-06-13 06:47:06
232
原创 CF346B kmp+dp
这道题应该是比较典型的利用kmp去dp的题目。我们思考题意他要求我们的子序列不能够和virus串完全匹配，那么我们就可以在原先求最长公共子序列的基础上在加一个维度。就是f[i][j][z]，第一个串枚举到i，第二个串枚举到j，然后他们与virus串匹配的长度是z。接下来思考转移。第一个串当做A数组，第二个串当做B数组即当(A[i] == B[j])的时候可以在原先已经有的子序列基础上加上字符A[i],这个时候与virus匹配到的长度是z。那么这个长度z是由谁转移来的？这个地方需要kmp去预处理。
2020-06-06 10:25:08
268
原创 CF547E 二分+sa+主席树
这提供一个sa+主席树的做法，这个用做法就你顺势可以在敲掉基本一样的洛谷P4084题意询问的是k串在[L,R]的串里面出现了多少次，不同位置算多次。对于一个串在SA里的位置以及和他最像的位置必然是连续的（字典序的原因）,然后对于每一个串就都可以二分出一个区间，这个区间内的串都有和当前串相同的前缀。那么我们知道这个区间后，怎么知道询问要求的区间有多少个是落在能够使用的区间呢？这就是可以利用主席树。我们让rk为权值去建立主席树，然后按字符串长度的顺序去插入，然后询问的时候我们就可以直接询问主席树上某个区
2020-06-05 09:14:26
163
原创 CF229D 动态规划dp
因为我菜所以只能想到消耗空间大，时间复杂度差的做法但是我就是要发！！首先这种题需要知道他是个dp（看不出来就GG），然后思考下怎么做，首先他是会进行区间合并，并且可以进行连续的合并，也就是把这个过程看做是一个连续区间合并的过程例：123456[1,2] [3,4,5] [6]可以将一个序列分解为若干个区间（区间长度可以为0），但是区间必须是连续的，不能说你1和3去合并在一起，这是不允许的。知道他是这样一个过程后要干嘛呢，我们可以设计dp转态设 f[i][j] 表示[1,i]的序列都合法后，第
2020-06-01 21:53:26
248
原创 洛谷p5555 PAM回文树
其实我是看题解都是建两颗PAM和BFS感觉没必要就来发个题解，首先我们知道PAM上的节点就是一个回文串对不对，然后题目要求的是两个串都出现过的回文串。那么我们完全可以这么做，在PAM的时候记录当前节点的回文串出现的次数，在一个串中这个次数只能出现一次，最后我们遍历PAM所有节点，去记录所有的出现次数为两次的节点，这个节点就是代表的一个回文串，然后PAM路上我们又已经知道了所有节点的LEN，那么就只需要记录最长的LEN就是答案。然后我们遍历所有PAM上节点的时候就可以算出每种长度的串的数量。其实就是PAM
2020-05-25 20:13:07
167
原创 洛谷p2569 二进制优化多重背包 dp
看题解都是单调队列，其实那个单调队列优化的过程，就是在一个单调队列优化多重背包的过程。因为我们第i天是可以买一定数量的股票，或者卖一定数量。但是直接枚举一个一个股票的加是复杂度爆炸。f[i][j]，表示第i天拥有j个股票的最大收益，在这个地方其实看着就很多重背包好吗！！！！！板子，大板子！！！所以就在买多少/卖多少股票的部分可以用二进制去优化多重背包，这样子就变成log的时间，其他题解的单调队列实...
2020-04-28 21:20:05
247
原创 牛客每日一题 4.7 树 树dp+组合数学
昨天的牛客鸽了，我不会数学首先第一步要理解题意就是要把树分成多个联通块，每个联通块的颜色都要不一样，求方案数。为什么每个联通块的颜色都不一样，因为如果有同样的颜色在不同的联通块上的话就无法满足题意，这两个点之间的路径的所有点就不会是都是同一种色。用f[i][j]代表的是以i为根的子树分成j个联通块的的方案数。由于我没想到大佬说的分成j个联通块就是删掉j-1条边，所以就硬算去合并每个子树的答案...
2020-04-06 16:06:16
156
原创 牛客每日一题4.3 Shortest Path 树dp
首先这个数据范围，看着就是O(N)或者O（Nlogn）的东西，考虑树dp。先贪心的考虑。一个点怎么找到另一个点？肯定是他能接触到的最短的那个点，如果与他最短的那个点被用过了呢？找其他第二近的点，以此类推。对于一个点，是只有当找不到人了才会继续走上去找其他人匹配，不然不管多大的权值都是会跟那个人走的。因为对于一条权值很大的边，边连着的两个点如果深度深的点在往下匹配不到人，就必须走上匹配，最少需要...
2020-04-02 15:03:44
123
原创 牛客每日一题4.2 月月查华华的手机 二分查找
问题就是询问某一个串是不是初始串的子序列。那么序列都是小写字母，就对存入每一个字母在初始串的位置。然后对目标串的字母一个个查询，如果存在一个最接近并且比上一个字母远的位置，则这个当前字母是存在序列中的，不断的遍历完整个目标串就可以了。开个vector，upper_bound真香char node[max_],temp[max_];vector<int> ind[30];sign...
2020-04-01 11:26:46
128
原创 牛客每日一题4.1 Rinne Loves Edges 树dp
首先理解题意后可以转化为以S为根的树，用最少的权值去删除边，使得所有的叶子与S不相连。如果可以得出上面的题意那这题就是个树dp简单题了。那么设f[i] 为以i为根的子树，他的所有叶子都达不到i节点的最少权值花费。显然方程就是f[i] = sum( min ( f [to], i与to相连的权) )这个方程就是对于i的每一个儿子，你有两种选择，第一种是砍掉i与to相连的边，这样所有叶子都不...
2020-03-31 14:50:12
128
原创 牛客每日一题3.31 城市网络 树上倍增
首先要理解好题意，他是走的路上如果有大于当前最大的权值就必须拿，而不是寻找最长的子序列。他是可以拿就必拿。他题目的询问保证了起点now 和终点to 和顶点1必然在同一条链上！！！我们可以采取倍增的方式。dp[i][j]表示节点i往上2^j个节点，这些节点中最大的权值是谁。所以可以从起点开始往上跳，跳到第一个大于当前最大权值的点。然后更新最大权值，接着往上跳，跳到超出范围了为止。也就是你现在要...
2020-03-30 12:18:22
115
原创 牛客每日一题3.30 滑动窗口 单调队列
这道题由于空间限制的很死，所以原本用线段树之类O(nlogn)的算法都会MLE，唯一的做法就是O（N）的单调队列。对于每一个滑动窗口的元素，都是从上一个窗口的基础上，增加一个新的元素，减掉一个最后的元素。就利用单调双端队列去处理问题，对于一个新的窗口就push进去，然后不断pop直到出现第一个合法的元素，那个元素就是我们要的这个窗口内的最值的答案，不合法的元素是什么意思呢，就是你这个元素所在的...
2020-03-29 12:26:50
123
原创 牛客竞赛每日一题3.27 数学考试 动态规划
虽然说是动态规划实则就是在暴力找答案。我们答案要求的是两个区间，所以我们只要选取一个区间，然后枚举这个区间往前的所有区间能提供的最大答案就好了。我们需要什么呢value[i] , 区间的最后位置是i，这个区间的权值总和.这个value可以用前缀和轻松算。下一个就是fmax[i],代表的是[1,i]这些位置能构成的最大区间权值然后答案明显就是ans = max(ans, value[i] ...
2020-03-26 12:08:18
160
原创 牛客每日一题3.26 合并回文子串 动态规划
首先这种题肯定是动态规划！！！！！不要往其他地方想。要怎么做呢先从单个串要怎么判断区间最长回文来说。单个串如果要判断任意一个区间[L,R]是不是回文可以去写区间dp，对于一个串长度大于2的回文串，如果要在此基础上在延长串的长度必然是在头尾加两个，所以对于一个串的就可以写出方程 f[L][R] |= F[L+1][R-1],(当a[L]==a[R]时)；现在到了两个串，其实思路差不多，两个串要拼出...
2020-03-25 20:12:59
139
原创 牛客每日一题3.25 tokitsukaze and Soldier 权值线段树
考虑我们可以怎么获得答案，如果某一个人选了他，那么答案人数的集合就必定小于等于s[i], 对于答案需要的人的集合的人数为num,那么集合里面所有的s[i]的最小值必然是小于等于num。明确了上述最关键的点后就是可以知道，我们如果答案的人数是2人，则s[i]>=2的全部人数取前2个就是答案，s[i] < 2的被我们排除了。那么解题步骤就是设目标人数是num人，取s[i] >= n...
2020-03-24 20:04:50
373
原创 Codeforces Global Round 7 cf 1326D 马拉车
题意是叫你找最长的回文串，然后这个回文串可以由原本的串的前驱+后继拼起来。由于前驱和后继是必须选的对不对（可能有一个为空）。那么我们第一步就是吧原本的串倒置，把正的和反的去找出最长的相同的，这样就满足了前驱+后继的限制。下一步是什么？假设原本的长度是[1,len]，我们上面找到的最长相同的长度是3，那么就是接下来剩下的串就是[1 + 3 - 1 , len - 3],剩下的这一段我们只需要找...
2020-03-20 11:13:18
173
原创 cf721 C DP
题目大意：给你个有向无环图，询问从1到n的路径里面，时间小于T的，但是路过点数是最多的路径。求点数n，m只有5000，所以大胆一点，n^2的算法就冲上去。题目要什么我们的dp就设计什么。设f[i][j]有两个权值v1,fa;意义是从1走到i走过了j个点的最小权值。走到i点的前一个点是fa。那么只要做一次拓扑排序，拓扑排序后就可以做一个线性的dp。不做拓扑会可能发现某个点还没被更新但是你就在...
2020-03-18 17:58:10
155
原创 cf776 D 并查集
题目大意就是有n个门，m个机关，机关对应的是k个门，点击机关m则k个门的状态全部反转。询问是否存在一种方式让所有门都变为1；每个门都是只有两个机关可影响到他。分析一下问题可以知道，对于门初始为1，则这个门对应的两个机关只能一起选，或者都不选，也就是这两个机关是被绑定着的。对于门初始为0，则这个们对应的两个机关只能选一个，选了A就不能选B，选B,就不能选A；考虑机关只有选与不选对不对。我们这么...
2020-03-18 17:50:05
159
原创 牛客练习赛59 E 石子搬运 dp+三分法
有n堆石子，第i堆石子的石子数量是ai{a_{i}}ai，作为牛客网的一头领头牛，牛牛决定把这些石子搬回牛客。如果牛牛一次搬运的石子数量是k{k}k，那么这堆石子将对牛牛产生k2{k^{2}}k2的负担值。牛牛最多只能搬运m{m}m次，每次搬运可以从一堆石子中选出一些石子搬回牛客，每次搬运不能同时从两堆石子中选取石子，每次只能搬运整数个石子。牛牛是一只聪明的牛，他想出了一种搬运计划可以最小化他搬...
2020-03-14 13:53:49
326
原创 洛谷p1831 数位dp
补充点在其他题解里面没有的其他东西。首先是之所以可以数位dp并且不会算错的原因是，对于每一个数字，如果这个数字是杠杆数，那么他的支点有且只有一个，如果一个数字有多个支点，那么数位dp去枚举支点就会算重复，算多。另外全部人都是在说数位dp然后枚举支点，对R和L-1分别做一次dp，但是可以有个小优化就是，我们要明确一个东西，dp数组存的是那些没有被限制的的有用数字是数量，也就是对于任意数都适用。...
2020-02-27 12:24:44
195
原创 洛谷p2059 概率dp
首先仔细读题目按顺时针从庄家位置数第X个人将被处决即退出游戏，x为1的时候被处决的就是庄家，千万不要理解错位庄家的位置+x就是被处决人的位置，我一开始就是这么理解然后调完发现怎么加起来答案是1但是和样例长的不一样我们思考下怎么做，对于如此小的数据范围，肯定是可以枚举每一次游戏某一个人获得胜利的概率，如果比如数据范围偏大，那就dp的设计就要去想一次dp得全部答案的方法，要有这个设计方程前的理性...
2020-02-25 17:24:11
309
原创 洛谷p2018 树DP
首先，本做法和其他的O(N^2logn)做法是完全不一样的，那种做法比较好理解，我说一下我的做法，感jio是O(Nlogn)，不太会算首先思考如何获得每一点要如何知道由当前点出发的答案是什么？对于绝大部分点，都有父亲节点和儿子节点，那么对于每一个点都是这么抉择走的。这里先不看now点，看节点1，如果第一个人从节点1开始要怎么走呢？就是花4次时间， 分别走4跳荧光笔的路径对吧，然后就没节点1什...
2020-02-16 07:47:45
127
原创 洛谷p1773 dp
其实， 这个dp还是蛮简单的，dp做多了后就会觉得方程不难出了，其实我的思路和大家都差不多，但是大部分都用了O(N^2)去预处理出这个区间内的值取模后是多少，其实这是完全没有必要的。听我来给你吹f[i][j] = v：前i个字符各种操作后的数字为j，使用的最少的乘法个数为v，最后一个字符必须要落在i后面！！！！为什么我们要强行让他最后一个乘法字符在i后面，因为如果不这么做，我们就无法知道他最...
2020-02-14 22:05:38
82
原创 洛谷2285 dp
很水的dp，用于在你蓝题dp做疯了的时候来提高下信心。首先那个距离就是曼哈顿距离，所以小于等于1的格子就是当前格子的上下左右，还包含自身。其实唯一的问题就是如何计算贡献的时候不要算重复了，那么分情况考虑就可以不算重复，f[i][j][0]代表到达ij点的走法是从上面走下来，f[i][j][1]代表到达ij点的走法是从左边走过来。那么到达ij点后，有向下走和向右走，当你画出了图，就什么都知道了...
2020-02-11 11:10:07
109
原创 洛谷p2964 其中一种常见的博弈论的dp方法
题目链接在之前，我写dp看见题目说两个人都足够聪明，然后他们进行一些操作，求某些人的最大利益，我完全不知道怎么去设计dp的方法，然后我接触了一道题，看了题解洛谷p2734这道题的dp方法和现在这道题其实在设计思路上面是一样。我不知道现在是谁在取数字，但是我就是要为现在这个取数字的人谋取最大利益这个思想在博弈论的dp是很关键的。回到原题，一开始的玩家可以取k个币，下一个人只能取小于等于k*...
2020-01-30 11:42:35
591
原创 Codeforces Round #615 (Div. 3) F 运行最快的做法！！
一开始输出是cout，发现就第二了，改printf就直接第一快了。我说下这题我的做法是什么。题目就是给你一棵树，叫你给出三个点，这三个点相连的简单路径的边数最多。样例的图解释的很清楚是什么意思了。怎么做呢？我一开始首先考虑两个点相连的情况，两个点的情况下什么时候会是拥有最长的边数？很明显就是大家都知道的两个点是树直径的端点时候，树直径大家都会，随便找一点bfs/dfs出最远的一个点，这个点就是...
2020-01-24 15:41:53
1844
原创 详解2020 CCPC-Wannafly Winter Camp Day3 Div.1 G火山哥周游世界 树dp
题目链接上面是样例2的图，首先我们看到数据范围就一定要明确，肯定不是暴力，然后由于题目说了是n个点n-1条边，这就是一棵树，在这里就要考虑到树dp！！（要是没想到就没了）我们来考虑下我们要什么，我们需要知道每个点走过所有目标点的最短路程，一个点怎么走完所有的目标点呢？设当前在i点从点i向上走，走完上面所有目标点后回到i，在从i往下走，走到到达最后一个目标点就停止从点i向下走，走完下面所有...
2020-01-22 17:21:03
1779
原创 2019icpc 南昌C And and Pair dp
题目链接大意：给你一个超大数字n的二进制表示，询问有多少组数对（i，j），数对要满足，0≤j≤i≤n;i & n=i；i & j=0；首先对于我看到其他的什么数位dp，组合数学，我一个没懂。我说下 我自己是怎么dp的。对题目分析i&n = i，那么说明在二进制的情况下，相同的某一位数，n是1，那么i可以是1，也可以是0.（1&1 = 1， 1 &...
2020-01-16 11:30:41
623
原创 详解吉首大学第九届“新星杯”G芒砀山的神秘数字 两种dp
题目链接题目大意就是给一个长的字符串a和一个短的字符串b，询问a里面有多少个序列是大于b的。这里我们分两步来处理，就是我们先算出a中的序列长度和b一样的。因为显然答案是由序列长度一样的数量+序列长度>b的数量。为什么不能直接一起算，因为dp的限制（下面讲）？（1）计算序列长度一样的数量。我们这么考虑由于序列长度是一样的，我们就可以枚举位数的时候有一个比较值。我们类比一下数位dp，数位d...
2020-01-09 13:06:20
256
原创 详细讲解康托展开集齐基础例题+模板
单纯讲讲怎么用怎么算，说些人话。预备概念：排列：对于一个数字n的排列就是含有[1,n]所有数字的序列。也就是n取3，那么123,132,213就叫做n的排列，但是112,12,13等等这种就不是排列。什么是康托展开呢？就是把一个n的全排列表示出来并且按照字典序排出来。n取三的全排列有6种，那么就对着6种按字典序小的顺序去排比如123的序号就是1,132的序号就是2.首先我们来讲怎么根据给出...
2020-01-06 21:12:44
567
原创 洛谷p1769 DP（线段树思想）
这题乍一看很吓人，实则当你去手画一下比赛过程的时候就可以知道了，假设总人数有8人，1， 2 ， 3 ， 4 ， 5 ， 6 ，7 ，8.题目说了每一轮都是按编号顺序从小到大去比赛的那么第一轮就是(1,2),(3,4),(5,6),(7,8).这么个比赛顺序，第二轮就是(1,2)的胜利者去比(3,4)的胜利者（另外两个同理）。这个比赛的过程在我刚刚接触这个题的时候我想的是线段树的过程，但是是一个十...
2020-01-06 09:44:07
220
原创 UVA1021洛谷P2583 DP
题目传送门这道题是在我还在很小白的时候看见，刘佳汝的书看见的，那时候看见还以为特别难，现在做多了DP看来其实也蛮水了，首先，一般做dp都是看哪个数据范围小一点就可以考虑从哪里开始设计状态。虽然这题都挺小的题目里面出现一个数据就是时间，时间是一个天然的线性序，可以十分简单的利用时间去完成线性转移，我们再来看一看他要要求的什么，T时间后在车站n的最少等待时间，在普通的DP（不是那种特别骚气的要搞你...
2020-01-05 10:25:06
177
原创 hdu6570 动态规划 dp
题目链接：hdu6570题目大意（机翻）:Avin正在研究系列。 如果满足以下条件，则一个系列称为“波动”：1）它至少包含两个元素；2）所有位于奇数位置的元素都相同；3）偶数位置的所有元素都相同；4）奇数位置的元素与偶数位置的元素不同。您得到的序列长度为n。 Avin要求您找到最长的“波浪”子系列。 子系列是系列的子序列。第一眼看见，我就觉得他是个dp（看题解才知道暴力也行）；我...
2019-11-24 10:51:30
185
原创 hdu 6736 dfs
题目链接：hdu6736这个题目由于题目对于给的图有很严重的限制，就是每个边最多只能处于一个简单的循环中，那么其实对于所有的图，都会是那种有一条链，链上的节点有个简单环，简单环的节点又有一条链如此反复。通过分析其实就可以知道，对于每一个边数为n的环，让他变成树的方案数目是2^n -1;就是拆一条的方案+拆2条+。。。。+拆n条。对于每一条单独的链，让他变成树的方案数是2^n ，因为链的话可以...
2019-10-18 20:09:39
145
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人