boxxxx

算法

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

/ 注册

全部文章 / 算法（共38篇）

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

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

2020-01-09

1 548

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

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

2020-01-06

0 566

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

UVA1021洛谷P2583 DP

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

2020-01-05

0 345

hdu6570 动态规划 dp

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

2019-11-24

0 415

hdu 6736 dfs

题目链接：hdu6736 这个题目由于题目对于给的图有很严重的限制，就是每个边最多只能处于一个简单的循环中，那么其实对于所有的图，都会是那种有一条链，链上的节点有个简单环，简单环的节点又有一条链如此反复。通过分析其实就可以知道，对于每一个边数为n的环，让他变成树的方案数目是2^n -1;就是拆一...

2019-10-18

0 435

hdu6739 dp

传送门：hdu6739 题目就是有很多种技能，想要用某种技能需要集齐某些含有QWE的组合（无序组合），题目就问给你一个按出技能的一个顺序，叫你最少按几次技能可以按出这些技能，（每集齐一个技能的组合要释放还需要按一次R）；这就是一道动态规划的题目，不要被题目骗了，虽然技能要按出来只需要一个无序组合，...

2019-10-18

0 423

洛谷p4178 点分治+线段树

题目链接：洛谷p4178 这道题目是点分治的题目，与模板题不一样的是，这是要统计小于路径长度为k的点对数。我们分析下与模板题的区别，模板要求的是路径等于k的长度的路径是否存在，然后统计的方法是对于每个重心（跟），求出各点与根的路径，然后重心下面的各个子树中，相同的子树不去统计答案，去计算之前非该子树...

2019-10-14

0 415

洛谷p1006 DP

题目链接：洛谷p1006 题目就是说传两次纸条，一次从左上传到右下，一次从右下传到左上，路径不能重复，其实我们换个角度就是从左上传到右下传两次就可以了。借助洛谷大佬题解的一张图你传两次的路径，每一步两个点的连线一定在一条斜线上，那么，其实对于一个矩阵，也就最多只有n+m条斜线，已确定两点在一条线...

2019-10-13

0 492

hdu6579 线性基

题目链接hdu6579 题目就是给你你个序列，问你任意区间内去取数，要求这些数的异或和最大，还要求可以增加这个序列。从序列里面取数求异或和最大，这个是线性基模板题，但是题目要求的不一样，要的是任意区间。要怎么处理呢？就是我们开一个二维的线性基，f[i][j], i表示的是f[i]这一维的线性基是[...

2019-10-09

0 566