在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

全部文章 / 题解（共7篇）

题解 | #Mondriaan's Dream#

本题讨论的是每一行的矩形的摆放，而一开始因为纠结于将一个矩形用一个二进制表示，但矩形摆放的方式不同每一行的数位也就不同所以思路就此卡住了。。。。。。但我们从矩形的摆放方式将其定义成1和0，并且每一个边长为1的小格都有一个0或1，这样就保证了每一层二进制位数的相同，那么这样写的状态转移方程是什...

C++ 状压dp

2023-10-26

1 348

题解 | #mixup2混乱的奶牛#

本题算是状压dp的一个变形用法，在这里面将二进制位上的数从0变到1其实做得将牛放到末尾的操作，那么可以看到对于某一头牛他只关心前面一头牛是什么，前面牛到底有几种摆放方式和当前的牛无关。这符合动态规划的特性。那么很容易得到状态转移方程为：dp[state|(1<<(i-1))][i...

C++ 动态规划状压dp

2023-10-26

2 285

题解 | #Most Powerful#

本题状压dp的简单应用，用0表示还没有消失或没有被使用的气体，1表示已经使用的气体。每次枚举寻找两个气体，饭后将其中一个变成1就行。 //在这里我们直接使用一维状态的转移，这样在转移的过程中去挑选值为0的两个节点 //那么这两个节点肯定有一个留下来，我们假设删除的节点为j，那么就有 //...

C++ 动态规划状压dp

2023-10-26

1 251

题解 | #简单环#

//动态规划数组依旧是：dp[state][j];i表示状态，j表示在当前状态下的结尾节点。 //但不同的在于这道题要找简单环，而对于找简单环来说定起点和终点是比较重要的。 //因为只有知道了起点和终点，然后又知道起点和终点是否有一条直接的线连接，就证明是不是环。 //如果我们单纯的去执行状态转移方...

C++ 状压dp

2023-10-26

2 377

题解 | #郊区春游#

本题从众多郊区里面选取R个郊区，要求走过一遍之后的中距离最短，那么我们首先就是要得到R个郊区彼此之间的最短距离，然后根据这个最短距离再来安排怎么走合适。那么要求彼此之间的最短距离问题就得用到数据结构里面学到的弗洛伊德算法了，根据弗洛伊德算法将所有的最短距离求出来。那么问题就回归到了经...

C++ 动态规划状压dp 最短路算法弗洛伊德算法

2023-10-25

2 445

题解 | #炮兵阵地#

本题算是[SCOI2005]互不侵犯KING (nowcoder.com)这道题的升级版，在互不侵犯这道题里面除了同一行的限制，上下行的限制仅仅包含一行。而在这道题里面则是包含了两行。那么我们可以像互不侵犯那样将状态转移数组设成dp[i][j]，i表示某一层，j表示当前层的二进制数吗？当然不...

C++ 动态规划状压dp

2023-10-24

2 332

题解 | #[SCOI2005]互不侵犯KING#

本题需要在N*N个棋盘里面摆放上K个国王，国王需要互不侵犯。那么从这个矩阵的角度来看（果断dfs[赞]）（开玩笑的。本题使用状压dp去求解，以每一层作为最外层遍历取走，对于每一层来说哪些格子上放的有国王就是1，没有放国王就是0，所以直接采用二进制去表示每一层的状态。而到某一层为止到底...

C++ 动态规划状压dp

2023-10-24

2 268