boxxxx

分类

学习(10) 并查集(1) 数位dp(1) 概率dp(1) 算法(38) 线性dp(1) 题解(3)

/ 注册

全部文章（共55篇）

Codeforces Round #615 (Div. 3) F 运行最快的做法！！

一开始输出是cout，发现就第二了，改printf就直接第一快了。我说下这题我的做法是什么。题目就是给你一棵树，叫你给出三个点，这三个点相连的简单路径的边数最多。样例的图解释的很清楚是什么意思了。怎么做呢？我一开始首先考虑两个点相连的情况，两个点的情况下什么时候会是拥有最长的边数？很明显就是大家都...

2020-01-24

0 411

详解2020 CCPC-Wannafly Winter Camp Day3 Div.1 G火山哥周游世界树dp

https://blog.csdn.net/qq_43804974/article/details/104071065博客链接，求给点关注吧上面是样例2的图，首先我们看到数据范围就一定要明确，肯定不是暴力，然后由于题目说了是n个点n-1条边，这就是一棵树，在这里就要考虑到树dp！！（要是没想到就没了...

动态规划 dp

2020-01-22

2 535

详解2020 CCPC-Wannafly Winter Camp Day3 Div.1 G火山哥周游世界树dp

题目链接上面是样例2的图，首先我们看到数据范围就一定要明确，肯定不是暴力，然后由于题目说了是n个点n-1条边，这就是一棵树，在这里就要考虑到树dp！！（要是没想到就没了）我们来考虑下我们要什么，我们需要知道每个点走过所有目标点的最短路程，一个点怎么走完所有的目标点呢？设当前在i点从点...

2020-01-22

0 432

2019icpc 南昌C And and Pair dp

题目链接大意：给你一个超大数字n的二进制表示，询问有多少组数对（i，j），数对要满足， 0≤j≤i≤n; i & n=i； i & j=0；首先对于我看到其他的什么数位dp，组合数学，我一个没懂。我说下我自己是怎么dp的。对题目分析 i&n = i，那么说明在二进制的...

2020-01-16

0 401

详解吉首大学第九届“新星杯”G芒砀山的神秘数字两种dp

https://blog.csdn.net/qq_43804974/article/details/103905708上面是csdn链接给点访问量吧题目大意就是给一个长的字符串a和一个短的字符串b，询问a里面有多少个序列是大于b的。这里我们分两步来处理，就是我们先算出a中的序列长度和b一样的。因...

组合数动态规划 dp

2020-01-09

1 691

详解吉首大学第九届“新星杯”G芒砀山的神秘数字两种dp

题目链接题目大意就是给一个长的字符串a和一个短的字符串b，询问a里面有多少个序列是大于b的。这里我们分两步来处理，就是我们先算出a中的序列长度和b一样的。因为显然答案是由序列长度一样的数量+序列长度>b的数量。为什么不能直接一起算，因为dp的限制（下面讲）？（1）计算序列长度一样的数...

2020-01-09

1 550

详细讲解康托展开集齐基础例题+模板

单纯讲讲怎么用怎么算，说些人话。预备概念：排列：对于一个数字n的排列就是含有[1,n]所有数字的序列。也就是n取3，那么123,132,213就叫做n的排列，但是112,12,13等等这种就不是排列。什么是康托展开呢？就是把一个n的全排列表示出来并且按照字典序排出来。n取三的全排列有6种，...

2020-01-06

0 571

洛谷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

0 342

UVA1021洛谷P2583 DP

题目传送门这道题是在我还在很小白的时候看见，刘佳汝的书看见的，那时候看见还以为特别难，现在做多了DP看来其实也蛮水了，首先，一般做dp都是看哪个数据范围小一点就可以考虑从哪里开始设计状态。虽然这题都挺小的题目里面出现一个数据就是时间，时间是一个天然的线性序，可以十分简单的利用时间去完成线性转移，...

2020-01-05

0 346

hdu6570 动态规划 dp

题目链接：hdu6570 题目大意（机翻）: Avin正在研究系列。如果满足以下条件，则一个系列称为“波动”： 1）它至少包含两个元素； 2）所有位于奇数位置的元素都相同； 3）偶数位置的所有元素都相同； 4）奇数位置的元素与偶数位置的元素不同。您得到的序列长度为n。 Avin要求您找到最长的“...

2019-11-24

0 417