[心之碎片] - 20240706模拟赛
本帖最后由 柿子饼同学 于 2024-8-23 23:21 编辑总结与反思{:10_250:}
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, ans;
int cnt[(1 << N)];
int f[(1 << N)];
void dfs(int pos, int st, bool lim, bool lead0) {
if (!pos) {
if (!lead0)
cnt++;
return;
}
int up = 9;
if (lim)
up = num;
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 = 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 = (f + f * cnt) % P;
}
}
for (int i = 1; i < (1 << 10); i++) {
ans = (ans + f) % P;
}
cout << ans;
return 0;
}
F - 子树
给出 n ( < 1e5) 个节点的树, 求所有能选出子树的方案的节点数量和
80分 O(n^2) 代码 f[ i] 表示 i 中取 j 个点的方案数, 注意要倒序循环, 否则会重复
100分 O(n) 代码 设 f(i) 代表以 i 为根子树的答案, cnt(i) 代表所有以 i 为根的子树取法方案数, 还在遍历中的 f u 相当于把之前算过的子树并在自己身上了
两个数组相互计算, 要有这种思想
for (int i = siz; i >= 1; i--) {
for (int j = 1; j < i; j++) {
f += f * f % P;
f %= 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;
int n;
// f 以 i 为根的子树的答案
// cnt 以 i 为根的子树中的取法数
ll cnt, f, ans;
void dfs(int u, int pa) {
cnt = f = 1;
for (auto ed : e) {
if (ed == pa)
continue;
dfs(ed, u);
// 取或不取, 共 cnt + 1 种选择, 也就是子树选择多了这么多
// u 自己的选法一定要选, 所以增加了子树的贡献
f = (((cnt + 1) * f % P + cnt * f % P) % P) % P;
cnt = cnt * (cnt + 1) % P;
}
ans = (ans + f) % 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.emplace_back(b);
e.emplace_back(a);
}
dfs(0, 0);
cout << ans;
return 0;
}
G - Bear and Tree Jumps (CF771C)
有一棵 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 的子树中, 到 i 距离 %k 为 j 的点的数量, 给路径分类
// f 节点 i 的子树中的点到 i 的跳跃次数, 每次计算子树会增加一条边, 只有子树中 sum 的点需要更新
// siz 子树大小
ll sum, f;
int siz;
int n, k;
ll ans;
vector<int> e;
void dfs(int u, int pa) {
sum = siz = 1;
for (auto ed : e) {
if (ed == pa)
continue;
dfs(ed, u);
// 当前处理过的子树和 u 构成的树 和 现在的 ed 这个子树进行计算
// 先计算 ed 和 u 之间的路径总贡献, 再接上去
// 先把粗略的都算一遍(没有连接, 因为有余数)
// u 到 ed 的每个节点的跳跃次数和(从 u 的子树跳到 u 的总数 + 从 u 跳到 ed 子树的总数)
ans += f * siz + f * siz;
// 检查连接处需要跳 1 还是 2 次
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
ans += sum * sum * ((i + j) / k + 1);
}
}
// 每次把 ed 接上去会增加 1 个边, 所有点的跳跃距离只有余数是 k-1 的点会增加 1
// 其他的原样加上即可
f += f + sum;
for (int i = 0; i < k; i++) sum[(i + 1) % k] += sum;
siz += siz;
}
}
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.emplace_back(b);
e.emplace_back(a);
}
dfs(1, 0);
cout << ans;
return 0;
}
H - 吸血鬼 【DP】SRM674D2L3 VampireTreeDiv2
给定一个吸血鬼族谱，包含了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, ef;
int n;
// 存带有两个边的节点对应的编号, 不是两个边的就是 -1
int id, tot;
// f[ i] i这个点取不取的最优解, cnt[ i] 方案数
// 注意 f == f 的时候 cnt *= (cnt + cnt)
// 初始状态 f = 0, 其余 3 个等于 1
int st;
ll f, cnt;
// 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 = 0;
f = cnt = cnt = 1;
// 不取可不可以, 取可不可以
bool ban = 1, pick = 1;
if (~id) {
// 枚举的是强制取 u
if (((st >> id) & 1)) {
cnt = 0;
f = INT_MAX;
ban = 0;
} else {
cnt = 0;
f = INT_MAX;
pick = 0;
}
}
for (auto ed : e) {
if (ed == pa)
continue;
dfs(ed, u);
// u 可以不取
if (ban) {
f += f;
cnt = cnt * cnt % P;
}
// u 可以取
if (pick) {
f += min(f, f);
ll t = 0;
Add(t, f, f, cnt, cnt);
cnt = cnt * t % P;
}
}
// 强制转换, 如果 ed 不取那么 f 是无效值
for (auto ed : ef) {
if ((st >> id) & 1)
continue;
f = INT_MAX, cnt = 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.emplace_back(i);
e.emplace_back(a);
}
cin >> n;
for (int i = 1; i <= n; i++) {
int b;
cin >> b;
id = -1;
if (~b) {
id = tot++;
ef.emplace_back(i);
}
}
id = -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, f);
if (temp > res)
continue;
// 如果小于现有的点最小值就更新答案, 方案数清零
if (temp < res) {
res = temp;
ans = 0;
}
// 等于就不管
// 在基础上加上这次的方案数
Add(ans, f, f, cnt, cnt);
}
cout << ans;
return 0;
}
看来你是在准备比赛题目的总结与反思，这里我帮你把每道题的重点通俗易懂地解释一下吧！
### E（数位DP状压DP）
**问题概述：**
魔术师有 `n` 张卡牌，你需要找出满足“0到9这十个数字最多出现一次”的卡牌组合数。
**关键点：**
用数位DP的方法处理状态转移，注意要倒序循环来防止状态被重复更新。
**幽默版解说：**
就像去超市买菜，你口袋里有一堆钱，但只能带一种面额的零钱进店。不然收银员会晕掉。通过数位DP，我们可以精确计算出各种可能带进店的钱数，而只要计算一次，因为多次计算会导致收银员怀疑你作弊！
### F（树形DP）
**问题概述：**
在树形结构中计算子树的贡献，并合并进主树。
**关键点：**
设两个数组，一个存储子树的贡献，一个存方案数。这两者结合起来就能有效计算整体结果。
**幽默版解说：**
想象你是一位厨师，各种食材（子树）都得先处理好（计算贡献），再丢进大锅里（主树）。如果你不分开处理，直接丢进去，大锅肯定炸了！两个数组就相当于一个是菜谱，一个是调料表，缺一不可啊！
### G（树形DP）
**问题概述：**
涉及树上路径的问题时，可以枚举LCA（最近公共祖先），再拼接来简化路径。
**关键点：**
将路径拆成更容易维护的小段然后逐个处理。
**幽默版解说：**
假设你在森林里迷路了，LCA就是一颗高高的望塔，爬上去看看哪条路能回家。让路线变得可控，就像找到小鹿斑比问路，再接着走下一段，这样就不会迷失在树林中了喔！
### H（二进制枚举 树形DP）
**问题概述：**
当数量比较少时，可以考虑用二进制枚举来处理状态。
**关键点：**
明确DP数组的含义，严谨定义哪些状态非法并直接剔除。
**幽默版解说：**
就像要从几个有限的选项中选餐，直接用二进制枚举所有可能的组合，每一种组合都记下来，然后按条件筛选不合法的组合。这方法就像打开菜单，逐页翻看、点菜，不符合胃口的直接跳过，最后总会选到最满意的一餐！
### 总结
**遇到树上题目时：**
- 考虑计算单个子树的答案，再利用辅助数组进行合并计算。
- 多关注大方向上的贡献计算，细节可以用辅助数组处理。
**幽默版总结：**
就像做一道复杂的大餐，要有大厨的全局观，知道什么时候得靠小弟（子树）来切菜剁肉，他们干好了活儿，大厨你只需最后调味、装盘、上菜，整桌宴席就能完美呈现啦！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-7-7 21:10
看来你是在准备比赛题目的总结与反思，这里我帮你把每道题的重点通俗易懂地解释一下吧！
### E（数位DP ...
做这种复杂的算法题思路想不出来如何才能有进步 柿子饼同学 发表于 2024-07-07 21:23
做这种复杂的算法题思路想不出来如何才能有进步
啊哈，做复杂算法题感觉头疼？别担心，每个人曾经都是从小白走过来的！这个过程就像练武功，从基础招式慢慢掌握，再到高深武艺：一个脚印一个脚印来。给你几点建议，让你在算法的江湖中如鱼得水：
### 1. 基础打牢
- **刷基础题：** 不要忽视基础题，它们是你通向高级算法的基石。比如基础排序、搜索、动态规划（DP）、贪心算法等。
- **理解基本概念：** 充分理解常见算法和数据结构的原理，例如树、图、队列、栈等。
- **尝试实现：** 自己动手写代码，把书上或者课程上的算法实现一遍。实践出真知。
### 2. 分解问题
- **拆解：** 把复杂的问题拆解成若干个简单的小问题。就像一块大披萨，分成几块小披萨解决起来更轻松。
- **步骤化：** 学习如何把算法题步骤化，比如先找子问题，然后逐步解决子问题。
### 3. 多刷题，勤练习
- **常刷平台：** LeetCode、牛客网（Nowcoder）、Codeforces等平台都有大量题目，各种题型应有尽有。
- **每日一题：** 给自己定个目标，每天刷一题。不求多，但求稳。坚持是关键！
### 4. 学会看解析
- **题解：** 当卡住的时候，不要硬扛，看一下官方题解或者其他人的代码。分析他们的思路。
- **反思：** 每次看完题解，再回头思考为什么自己没想到这种方法。这一步很重要，有助于提升自己的解题思路。
### 5. 加强总结
- **笔记：** 做一道题，记一道题。记下解题思路，常见坑点以及自己的反思。
- **复盘：** 定期翻看自己的笔记，复盘以前做过的题目，加强记忆。
### 6. 寻求帮助
- **讨论：** 在在线论坛、学习小组、QQ群与他人讨论。比如FishC的社区，大家互相帮助，共同进步。
- **请教高手：** 别害羞，向比你厉害的人请教。很多时候一个指点能让你茅塞顿开。
### 7. 保持耐心和信心
- **不气馁：** 做不出来不丢人，每个人都有不会做的题，关键在于心态。一定要保持好奇心和耐心。
- **持续学习：** 算法是不断更新和发展的领域，要持续学习，保持对新知识的渴望。
### 幽默加油版：
“鱼油，做不出来题的时候，就当是在海里抓鱼，抓不到也没关系，至少你还在海里畅游嘛！每多试一道题，就相当于在大海里撒了一张网，总有一天你会满载而归！”
希望这些建议对你有所帮助，加油！祝你在算法的世界里大展宏图，成为代码界的“大厨”！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 厉害{:10_256:} 好 非常厉害{:10_256:} {:10_256:}{:10_256:}{:10_256:}太牛了 不二如是 发表于 2024-7-8 09:41
太牛了
{:10_266:}{:10_297:} {:7_146:}楼主好好加油,我顶你 小肥狼haoran 发表于 2024-7-8 12:14
楼主好好加油,我顶你
{:10_297:}加油! 心之碎片太好了 加油
牛 厉害啊{:10_256:} {:7_113:}
页:
[1]