|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 柿子饼同学 于 2024-8-23 23:21 编辑
总结与反思
E (数位DP 状压DP)
对于 DP 的转移顺序, 要看阶段, 也要看什么状态不能被重复更新, 确定正序/倒序
F (树形DP)
树形 DP 中常用的思想就是对于每个子树, 计算它的贡献并且合并进来, 常常设两个数组一个是贡献, 一个是方案数
G (树形DP)
和树上路径相关的一般可以考虑枚举 lca , 拆成好维护的路径再拼接起来
H (二进制枚举 树形DP)
数量比较少的时候考虑二进制枚举, 对于 DP 数组的意义一定要严谨搞清楚, 本题中一些点的取和不取会强制让一些状态不合法, 直接砍掉, 答案相等时方案数记得加起来 总的来说遇到树上让你求 所有 什么什么的贡献就想着求一个子树的答案, 再加一些辅助数组互相计算, 要考虑大一点的贡献, 方便计算
E - Wonderhoy子集
魔术师有 n 张卡牌，编号从 1 到 n (n < 1e9)
小梦每次从中抽出若干张，无论她怎么抽，她抽到的卡牌中 0 到 9 这个十个数字最多出现一次
小梦觉得这魔术非常的 Wonderhoy! 她想知道有多少种卡牌组合是 Wonderhoy 的
只需要用数位dp把小于 n 中的满足条件的数字按照含有的数位 (二进制) 分类求和
dp 的时候刷表, 但是必须注意对于一个状态, 每种数只能用一次, 必须倒序循环, 不然一个数可能把状态更新两次#include <bits/stdc++.h>
using namespace std;
const int N = 10;
const int P = 1e9 + 7;
int n, num[N], ans;
int cnt[(1 << N)];
int f[(1 << N)];
void dfs(int pos, int st, bool lim, bool lead0) {
if (!pos) {
if (!lead0)
cnt[st]++;
return;
}
int up = 9;
if (lim)
up = num[pos];
for (int i = 0; i <= up; i++) {
if ((st >> i) & 1)
continue;
if (!i && lead0)
dfs(pos - 1, st, lim && (i == up), lead0);
else
dfs(pos - 1, st | (1 << i), lim && (i == up), lead0 && !i);
}
}
void work(int x) {
int len = 0;
while (x) {
num[++len] = x % 10;
x /= 10;
}
dfs(len, 0, 1, 1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
work(n);
f[0] = 1;
// i枚举数字, j枚举状态, 阶段是选取这个数字, j倒序循环不会重复计算
for (int i = 1; i < (1 << 10); i++) {
for (int j = (1 << 10) - 1; j >= 0; j--) {
if (i & j)
continue;
f[i | j] = (f[i | j] + f[j] * cnt[i]) % P;
}
}
for (int i = 1; i < (1 << 10); i++) {
ans = (ans + f[i]) % P;
}
cout << ans;
return 0;
}
给出 n ( < 1e5) 个节点的树, 求所有能选出子树的方案的节点数量和
80分 O(n^2) 代码 f[ i][j] 表示 i 中取 j 个点的方案数, 注意要倒序循环, 否则会重复
100分 O(n) 代码 设 f(i) 代表以 i 为根子树的答案, cnt(i) 代表所有以 i 为根的子树取法方案数, 还在遍历中的 f u 相当于把之前算过的子树并在自己身上了
两个数组相互计算, 要有这种思想for (int i = siz[u]; i >= 1; i--) {
for (int j = 1; j < i; j++) {
f[u][i] += f[u][j] * f[ed][i - j] % P;
f[u][i] %= P;
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int P = 1e9 + 7;
vector<int> e[N];
int n;
// f[i] 以 i 为根的子树的答案
// cnt[i] 以 i 为根的子树中的取法数
ll cnt[N], f[N], ans;
void dfs(int u, int pa) {
cnt[u] = f[u] = 1;
for (auto ed : e[u]) {
if (ed == pa)
continue;
dfs(ed, u);
// 取或不取, 共 cnt[ed] + 1 种选择, 也就是子树选择多了这么多
// u 自己的选法一定要选, 所以增加了子树的贡献
f[u] = (((cnt[ed] + 1) * f[u] % P + cnt[u] * f[ed] % P) % P) % P;
cnt[u] = cnt[u] * (cnt[ed] + 1) % P;
}
ans = (ans + f[u]) % P;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
e[a].emplace_back(b);
e[b].emplace_back(a);
}
dfs(0, 0);
cout << ans;
return 0;
}
有一棵 n ( < 2e5) 个节点的树，树上住着一只熊。
若熊在节点 i，熊跳一次可以从 i 跳到离 i 树上距离 <= k ( < 5) 的任意节点 。
求所有路径(i, j) , i < j 跳跃数的总和
k 很小, 想到给路径分类
求所有的路径不好想, 先想着枚举 lca , 然后把两个路径拼起来即可
设 f(u) 表示 u 的子树中所有节点到 u 跳跃次数总和, 考虑转移, 每次新加了一条边, 增加的跳跃数只有 %k 等于 k-1 的点
数组含义要大胆设计, 不要局限于一个点一条边的贡献
好好利用值小的好性质进行转移
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
// sum[i][j] 节点 i 的子树中, 到 i 距离 %k 为 j 的点的数量, 给路径分类
// f[i] 节点 i 的子树中的点到 i 的跳跃次数, 每次计算子树会增加一条边, 只有子树中 sum[i][k - 1] 的点需要更新
// siz[i] 子树大小
ll sum[N][5], f[N];
int siz[N];
int n, k;
ll ans;
vector<int> e[N];
void dfs(int u, int pa) {
sum[u][0] = siz[u] = 1;
for (auto ed : e[u]) {
if (ed == pa)
continue;
dfs(ed, u);
// 当前处理过的子树和 u 构成的树 和 现在的 ed 这个子树进行计算
// 先计算 ed 和 u 之间的路径总贡献, 再接上去
// 先把粗略的都算一遍(没有连接, 因为有余数)
// u 到 ed 的每个节点的跳跃次数和(从 u 的子树跳到 u 的总数 + 从 u 跳到 ed 子树的总数)
ans += f[u] * siz[ed] + f[ed] * siz[u];
// 检查连接处需要跳 1 还是 2 次
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
ans += sum[u][i] * sum[ed][j] * ((i + j) / k + 1);
}
}
// 每次把 ed 接上去会增加 1 个边, 所有点的跳跃距离只有余数是 k-1 的点会增加 1
// 其他的原样加上即可
f[u] += f[ed] + sum[ed][k - 1];
for (int i = 0; i < k; i++) sum[u][(i + 1) % k] += sum[ed][i];
siz[u] += siz[ed];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
e[a].emplace_back(b);
e[b].emplace_back(a);
}
dfs(1, 0);
cout << ans;
return 0;
}
给定一个吸血鬼族谱，包含了A，B两个数组，每个吸血鬼由以下方式生成：
0、0号吸血鬼是吸血鬼始祖。
1、B[ i]=-1表示i号吸血鬼被A[ i]号吸血鬼感染。构成一条关系（i，A[ i]）。
2、B[ i]!=-1表示i号吸血鬼由A[ i]号吸血鬼和B[ i]号吸血鬼生出来。构成两条关系（i，A[ i]）和（i，B[ i]）（这类生成不会超过15个）
现在要求选取最少数目的吸血鬼，使得家谱中给出的所有关系中，至少有一只吸血鬼被选到（即每条边中至少有一点被选中，且选取点数最少）。
问满足如上条件的选取方案数
两个边的点不超过 15 考虑枚举每个点的取/不取情况然后 dp
一定注意在 dp 过程中一个点强制不取, 那另一个路径上的点就必须强制取, 有的状态就不合法需要设极大值了
我做题的时候一直在思考取不取对答案的贡献, 其实不需要, 因为 求一次 dp 的时间复杂度完全够用
不要总考虑局部#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const ll P = 1e9 + 7;
// ef 专门存第二条边, 如果这些边的子节点不取, 那父节点必须取
vector<int> e[N], ef[N];
int n;
// 存带有两个边的节点对应的编号, 不是两个边的就是 -1
int id[N], tot;
// f[ i][0/1] i这个点取不取的最优解, cnt[ i][0/1] 方案数
// 注意 f[ed][0] == f[ed][1] 的时候 cnt[u][1] *= (cnt[ed][0] + cnt[ed][1])
// 初始状态 f[u][0] = 0, 其余 3 个等于 1
int st;
ll f[N][2], cnt[N][2];
// a, b 是 f 值, ac, bc 是 cnt 值
void Add(ll& s, ll a, ll b, ll ac, ll bc) {
if (a == b)
s = (s + ac + bc) % P;
if (a < b)
s = (s + ac) % P;
if (a > b)
s = (s + bc) % P;
}
void dfs(int u, int pa) {
f[u][0] = 0;
f[u][1] = cnt[u][0] = cnt[u][1] = 1;
// 不取可不可以, 取可不可以
bool ban = 1, pick = 1;
if (~id[u]) {
// 枚举的是强制取 u
if (((st >> id[u]) & 1)) {
cnt[u][0] = 0;
f[u][0] = INT_MAX;
ban = 0;
} else {
cnt[u][1] = 0;
f[u][1] = INT_MAX;
pick = 0;
}
}
for (auto ed : e[u]) {
if (ed == pa)
continue;
dfs(ed, u);
// u 可以不取
if (ban) {
f[u][0] += f[ed][1];
cnt[u][0] = cnt[u][0] * cnt[ed][1] % P;
}
// u 可以取
if (pick) {
f[u][1] += min(f[ed][0], f[ed][1]);
ll t = 0;
Add(t, f[ed][0], f[ed][1], cnt[ed][0], cnt[ed][1]);
cnt[u][1] = cnt[u][1] * t % P;
}
}
// 强制转换, 如果 ed 不取那么 f[u][0] 是无效值
for (auto ed : ef[u]) {
if ((st >> id[ed]) & 1)
continue;
f[u][0] = INT_MAX, cnt[u][0] = 0;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
e[a].emplace_back(i);
e[i].emplace_back(a);
}
cin >> n;
for (int i = 1; i <= n; i++) {
int b;
cin >> b;
id[i] = -1;
if (~b) {
id[i] = tot++;
ef[b].emplace_back(i);
}
}
id[0] = -1;
// st 表示每个两条边的点的 取/不取 状态, 0不取 1取
// res 表示取的最少的点数, ans 是这样取的方案数
// 注意如果相等 ans 是要加上这个方案数的
ll res = INT_MAX, ans = 0;
for (st = 0; st < (1 << tot); st++) {
memset(f, 0x3f, sizeof(f));
memset(cnt, 0, sizeof(cnt));
dfs(0, 0);
ll temp = min(f[0][0], f[0][1]);
if (temp > res)
continue;
// 如果小于现有的点最小值就更新答案, 方案数清零
if (temp < res) {
res = temp;
ans = 0;
}
// 等于就不管
// 在基础上加上这次的方案数
Add(ans, f[0][0], f[0][1], cnt[0][0], cnt[0][1]);
}
cout << ans;
return 0;
}
|
评分
-
查看全部评分
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2024-7-7 21:06:01
置顶卡
千斤顶
显身卡
楼主
发表于 2024-7-7 21:45:15
发表于 2024-7-8 09:41:36
楼主好好加油,我顶你