状态压缩

Leetcode.2397 被列覆盖的最多行数

题目链接 Leetcode.2397 被列覆盖的最多行数 Rating ： 1719 题目描述给你一个下标从 0 开始的 m x n二进制矩阵 mat和一个整数 cols，表示你需要选出的列数。如果一行中，所有的 1 都被你选中的列所覆盖，那么我们称这一行被覆盖…

智力题——5L的桶和3L的桶如何装4L的水

文章目录智力题——5L的桶和3L的桶如何装4L的水问题描述直观分析问题建模问题解决智力题——5L的桶和3L的桶如何装4L的水问题描述有一个5L的桶A和一个3L的桶B以及无限量的水，如何让5L的桶装4L的水。支持操作：加水，倒水，A倒入…

C++深度优先搜索(DFS)算法的应用：树中可以形成回文的路径数

本文涉及知识点深度优先搜索(DFS) 状态压缩题目给你一棵树（即，一个连通、无向且无环的图），根节点为 0 ，由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示&#…

Leetcode.1542 找出最长的超赞子字符串

题目链接 Leetcode.1542 找出最长的超赞子字符串 hard 题目描述给你一个字符串 s s s 。请返回 s s s 中最长的超赞子字符串的长度。「超赞子字符串」需满足满足下述两个条件： 该字符串是 s s s 的一个非空子字符串进行任意次数的字符交换后，该…

【动态规划】【记忆化搜索】【状态压缩】1681. 最小不兼容性

作者推荐【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字本文涉及知识点动态规划汇总状态压缩记忆化搜索 1681. 最小不兼容性给你一个整数数组 nums 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中，使得同一…

【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

作者推荐视频算法专题本文涉及知识点动态规划汇总广度优先搜索状态压缩 LeetCode847 访问所有节点的最短路径存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。给你一个数组 graph 表示这个图。其中，graph[i] 是一个列…

牛客周赛 Round 32（A,B,C,D,E,F）

比赛链接官方视频讲解这场D是用dfs跑图的一个树上dp，E是裸状压，F是状压DP，会状压的话其实难度不是特别大。B题出乎意料的卡了我一会，实际上如果推理出来一个小性质写起来就很简单了。 A 小红的 01 背包思路： V的…

Kuangbin专题 - 简单搜索 - D - Fliptile

关灯问题需要注意的一点是：单调不能完成的任务是一定不能完成的，没有反复开关灯的操作…单调向下枚举… 这里我观察到了(i-1,j)点为1时是必须开一次灯的。枚举第一行是否开灯即可（因为没有作为是否参考的第零行）。很巧妙的是…

POJ3254，Corn Fields（状压DP）

题意:农夫有一块地，被划分为m行n列大小相等的格子，其中一些格子是可以种植作物的（用1标记），其他格子则不能种植（用0标记），并且要求相邻格子不能同时都有种植作物。现在输入数据给出这…

【图论】【状态压缩】【树】【深度优先搜索】1617. 统计子树中城市之间最大距离

作者推荐【动态规划】【字符串】【行程码】1531. 压缩字符串本文涉及的知识点图论深度优先搜索状态压缩树 LeetCode1617. 统计子树中城市之间最大距离给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] …

【GDOI2017模拟9.9】[IOI2007]偶环

Description 给定一个n个点m条边的无向带权图，你需要删除若干条边，使得这个图中没有长度为偶数的简单环。有一些边不能删除，保证不能删除的边构成原图的一个生成树。 n<1000,m<5000,每个点的度数<10 Solution 首先我们把那些本…

【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

作者推荐视频算法专题本文涉及知识点动态规划汇总 LeetCode:1012. 至少有 1 位重复的数字给定正整数 n，返回在 [1, n] 范围内具有至少 1 位重复数字的正整数的个数。示例 1： 输入：n 20 输出：1 解释：具有至…

Codeforces Round 926 (Div. 2)（A,B,C,D,E,F）

这场还是很有含金量的，B题开始就有难度了，B是个推结论的题，C要推结论然后递推，D题是有点难的树上DP（主要是状态转移方程不好写），E题是个二进制预处理然后状压DP，F题是个数论&#xf…

算法竞赛备赛进阶之状态压缩训练

状态压缩状态压缩DP是一种暴力的算法，它需要遍历每个状态，而每个状态是多个事件的集合。这种算法通常用于小规模问题的求解，因为它的复杂度是指数级别的。状态压缩DP的两个基本特征包括问题的数据规模特别小，可以通过2的阶乘次…

Codeforces Round #454 (Div. 2, based on Technocup 2018 Elimination Round 4) E - Party

状态压缩dp 如果本来就在关系网之内，最小步是0，上一个状态是-1(不存在) 如果通过新的关系到达的步骤小于之前的步骤，就更新。 #include <iostream> #include <cstring> using namespace std; const int init-1; int minstep[1…

Codeforces #488div.2 - 994E - Careful Maneuvering(状态压缩+暴力枚举)

唉！！读错题了！(0,0)也可以。话说我是怎么读成要挖去原点的… 首先讲一下状态压缩的方法：每一位代表一架大飞船，那么长度为6060的位串就代表了一组大飞船。其次我们考虑何时飞船能被击毁：很明显当大飞船和…