搜索结果
查询Tags标签： 状压，共有 29条记录-
CF1391D-505 （思维结论 + 暴力 + 状压dp）
题目要求每一个长度为偶数的正方形里，1的个数都是奇数。 于是我们发现，一旦n >= 4同时 m >= 4那么一定是-1，奇+奇+奇+奇=偶 之后就剩下了三种可能性，n=1，n=2，n=3于是考虑状压dp。#include <bits/stdc++.h> using namespace std; typedef long long ll;…
2021/8/25 23:06:51 人评论 次浏览 -
CF1391D-505 （思维结论 + 暴力 + 状压dp）
题目要求每一个长度为偶数的正方形里，1的个数都是奇数。 于是我们发现，一旦n >= 4同时 m >= 4那么一定是-1，奇+奇+奇+奇=偶 之后就剩下了三种可能性，n=1，n=2，n=3于是考虑状压dp。#include <bits/stdc++.h> using namespace std; typedef long long ll;…
2021/8/25 23:06:51 人评论 次浏览 -
Valley Numer II 题解(状压dp)
题目链接 题目大意 给定一张 N 个点 M 条边的无向图，其中有 K 个点被标记为高点，剩下的 (N-K) 个点是低点。图中的山谷 定义为三元组 <X,Y,Z>，满足X和Y之间有边，Y与 Z之间也有边，同时X和Z是高点，Y是低点。问这个图中 最多有几个山谷（一个点只能出现在一个山谷…
2021/8/23 23:36:20 人评论 次浏览 -
Valley Numer II 题解(状压dp)
题目链接 题目大意 给定一张 N 个点 M 条边的无向图，其中有 K 个点被标记为高点，剩下的 (N-K) 个点是低点。图中的山谷 定义为三元组 <X,Y,Z>，满足X和Y之间有边，Y与 Z之间也有边，同时X和Z是高点，Y是低点。问这个图中 最多有几个山谷（一个点只能出现在一个山谷…
2021/8/23 23:36:20 人评论 次浏览 -
Mondriaan's Dream 题解(棋盘状压问题)
题目链接 题目大意 现在有一个 nm 的方格棋盘，和无限的 12 的骨牌。 问有多少种方法可以用骨牌铺满棋盘。1 ≤ n,m ≤ 11 题目思路 这种算是状压dp的模板题目 主要是思考上一行和这一行的转移即可 需要两个连续的空位，并且上一行的这两个位置也得已经被覆盖。 如果竖着：…
2021/8/23 23:09:15 人评论 次浏览 -
Mondriaan's Dream 题解(棋盘状压问题)
题目链接 题目大意 现在有一个 nm 的方格棋盘，和无限的 12 的骨牌。 问有多少种方法可以用骨牌铺满棋盘。1 ≤ n,m ≤ 11 题目思路 这种算是状压dp的模板题目 主要是思考上一行和这一行的转移即可 需要两个连续的空位，并且上一行的这两个位置也得已经被覆盖。 如果竖着：…
2021/8/23 23:09:15 人评论 次浏览 -
Pieces 题解(状压dp+$3^n$枚举子集)
题目链接 题目大意 有一个长度不超过 16 的字符串。每次你可以从中删除一个子序列，但是要求这个子序列是回 文的。问最少删除几次可以把这个字符串删光。 题目思路 这个数据很小 很明显是状压\(dp\) 设\(dp[i]\)表示删除\(i\)的最小操作数 那么答案显然为\(dp[(1<<…
2021/8/23 23:08:58 人评论 次浏览 -
Pieces 题解(状压dp+$3^n$枚举子集)
题目链接 题目大意 有一个长度不超过 16 的字符串。每次你可以从中删除一个子序列，但是要求这个子序列是回 文的。问最少删除几次可以把这个字符串删光。 题目思路 这个数据很小 很明显是状压\(dp\) 设\(dp[i]\)表示删除\(i\)的最小操作数 那么答案显然为\(dp[(1<<…
2021/8/23 23:08:58 人评论 次浏览 -
OI卷题记录
2021.8.2LG3386匈牙利算法 二分图LG1377笛卡尔树 题解2021.8.3LG2962\(\text{Meet in middle}\)LG3389高斯消元 高斯-约旦消元2021.8.4SPOJ ABCDEF暴力+优化 题解LG5691暴力+优化 题解2021.8.5LG3067暴力+优化 题解LG4799暴力+优化2021.8.6LG2602数位DPUVA1640数位DP 注:本…
2021/8/14 6:35:45 人评论 次浏览 -
OI卷题记录
2021.8.2LG3386匈牙利算法 二分图LG1377笛卡尔树 题解2021.8.3LG2962\(\text{Meet in middle}\)LG3389高斯消元 高斯-约旦消元2021.8.4SPOJ ABCDEF暴力+优化 题解LG5691暴力+优化 题解2021.8.5LG3067暴力+优化 题解LG4799暴力+优化2021.8.6LG2602数位DPUVA1640数位DP 注:本…
2021/8/14 6:35:45 人评论 次浏览 -
[做题笔记] 浅谈状压dp在图计数问题上的应用
无向图计数 题目描述 点此看题 有一个 \(n\) 个点 \(m\) 条边的无向图，对于每个 \(k\) 求出有多少种保留边的方案使得 \(1\) 能到 \(k\) \(n\leq 17,m\leq {n\choose 2}\) 解法 设 \(dp[s]\) 表示 \(1\) 能到集合 \(s\)，只考虑集合 \(s\) 中的边的方案数，转移考虑总方案…
2021/8/9 23:07:10 人评论 次浏览 -
[做题笔记] 浅谈状压dp在图计数问题上的应用
无向图计数 题目描述 点此看题 有一个 \(n\) 个点 \(m\) 条边的无向图，对于每个 \(k\) 求出有多少种保留边的方案使得 \(1\) 能到 \(k\) \(n\leq 17,m\leq {n\choose 2}\) 解法 设 \(dp[s]\) 表示 \(1\) 能到集合 \(s\)，只考虑集合 \(s\) 中的边的方案数，转移考虑总方案…
2021/8/9 23:07:10 人评论 次浏览 -
各种dp分类整理
各种dp分类整理 数位dp 因为比较重要，单独写一篇 见 这篇 状压dp 某篇学术垃圾 中指出，我们可以说，所有的dp都会有一个“状压”。只不过普通的dp压缩的比较浅显，而使用二进制的状压dp压的比较复杂，才叫它“状压dp”所以这里特指“状压dp”为“使用二进制压缩状态的dp…
2021/8/4 23:06:34 人评论 次浏览 -
各种dp分类整理
各种dp分类整理 数位dp 因为比较重要，单独写一篇 见 这篇 状压dp 某篇学术垃圾 中指出，我们可以说，所有的dp都会有一个“状压”。只不过普通的dp压缩的比较浅显，而使用二进制的状压dp压的比较复杂，才叫它“状压dp”所以这里特指“状压dp”为“使用二进制压缩状态的dp…
2021/8/4 23:06:34 人评论 次浏览
