[心之碎片II] - 0901-0908 树上问题和几个树形/状压DP
在线问题常常考虑离线, 可以排序之类的操作然后减少复杂度, 得出答案(差分 / 删除转加入 ...), 能够自己确定一个 "顺序"dp 最先考虑的是阶段, 就是给出一个顺序来解决问题, 转移的时候注意一下有没有漏
在需要枚举子集的 dp 中常常考虑容斥, 允许他们重复, 先弱化题目要求, 如果我们知道集合的交就能知道他们的并
树形的倍增 dp 套路是 i 到 i 的祖先, 挖掉 i 的子树的答案
树形背包的套路需要掌握参数别写错!!! 排序后的东西一次性搞完, 后面的顺序是错的
{:10_243:}{:10_256:}
P4219 大融合
简单题, 用并查集实时维护连通块, 并查集的根是树上最高的节点
P5024 保卫王国
原来已经差不多想好了, 但是倍增数组的设计还是取到了 i , 导致不好转移
倍增数组求答案的时候我们只关系结尾的状态, 所以枚举怎么得出结尾状态即可, 要设置中间量 = 原来的量 + 这次倍增的量, 最后取最大值
ll Solve(int a, int x, int b, int y){
if(dep < dep){
swap(a, b);
swap(x, y);
}
if(pa == b && !x && !y) return -1;
ll ta, tb;
ll ra = {INF, INF}, rb = {INF, INF};
// ra/rb 为结果数组
// ta/tb 为转移中间量
ra = dn;
rb = dn;
int d = dep - dep;
for(int i = 16; i >= 0; i--){
if((d >> i) & 1){
ta = ta = INF;
for(int j = 0; j < 2; j++){
for(int k = 0; k < 2; k++){
ta = min(ta, ra + f);
}
}
ra = ta, ra = ta;
a = pa;
}
}
if(a == b)
return (ra + up);
for(int i = 16; i >= 0; i--){
if(pa == pa) continue;
ta = ta = INF;
tb = tb = INF;
for(int j = 0; j < 2; j++){
for(int k = 0; k < 2; k++){
ta = min(ta, ra + f);
tb = min(tb, rb + f);
}
}
for(int j = 0; j < 2; j++){
ra = ta;
rb = tb;
}
a = pa, b = pa;
}
int l = pa;
ll res = INF;
res = min(res, dn - dn - dn + ra + rb + up);
res = min(res, dn - min(dn, dn) - min(dn, dn) + min(ra, ra) + min(rb, rb) + up);
return res;
}
P5298 Minimax
线段树合并, 公式好推但是没能想出来合并的时候怎么办的
首先发现是对于每个 i 有不同的前后缀, 那么要想到只更新叶子, 然后更新更大的区间
注意需要保存没更新前的值, 到达叶子的时候正好能算出来对应值
// 线段树合并的同时, 到达叶子节点就可以更新它的值了
int Merge(int x, int y, ll px, ll py, ll sx, ll sy, ll p){
if(!x && !y) return 0;
// 到达叶子节点, 正好在路途中就求出了另一个孩子的前缀后缀
if(!y){
t.tag((p * py % P + (1 - p + P) * sy % P) % P);
return x;
}
if(!x){
t.tag((p * px % P + (1 - p + P) * sx % P) % P);
return y;
}
Dn(x), Dn(y);
// 保证都是之前的答案
ll lx = f(lc(x)), rx = f(rc(x)), ly = f(lc(y)), ry = f(rc(y));
// 根据走向更新一下前后缀
lc(x) = Merge(lc(x), lc(y), px, py, (sx + rx) % P, (sy + ry) % P, p);
rc(x) = Merge(rc(x), rc(y), (px + lx) % P, (py + ly) % P, sx, sy, p);
Up(x);
return x;
}
P4563 守卫
想了一个假做法, 预处理 r 能看到的最远连续, 但是不对劲, 发现的性质是 r 必须建一个
区间 dp 想想怎么区分 左 / 右 的 dp 从而更新整个的
// 对于一段区间 r是必须取的, 根据这个来做
for(int r = 1; r <= n; r++){
f = 1;
ans ^= 1;
int p = 0;
for(int l = r - 1; l >= 1; l--){
// 对于每个 r, 能看到的区间是 p1...p2...p3...p4... 等等
// 点点点的那些区间没法被看见, 需要自己解决
// 每次找到 r 能看见的最远点, 没被更新的时候就是...的区间
// 对于...的区间要么在 p 建, 要么在 p - 1 建
if(!p || Insight(l, p, r)) p = l;
f = min(f, f) + f;
ans ^= f;
}
}
P3349 小星星
I - 状压 dp 比较简单, 但是转移复杂度太高, 一个优化是把状态按照 1 的个数分类, 这样能显著提升时间, 值得学习 (90 pts)
for(int i = 1; i < (1 << n); i++){
st.emplace_back(i);
}
II - 正解是容斥, 以后看到这种类似的需要枚举子集的问题 (而且不重叠的) 想容斥, 我们允许算重复, 但是只能根据枚举的状态里面的数来算
根节点是 0 ,注意了
void Assign(int st){
siz = 0;
for(int i = 0; i < n; i++){
if((st >> i) & 1){
c[++siz] = i + 1;
}
}
}
void Calc(){
ll t = 1;
if((n - siz) & 1) t = -1;
for(int i = 1; i <= siz; i++){
ans += t * f];
}
}
void dfs(int u, int p){
for(int i = 1; i <= siz; i++){
f] = 1;
}
for(auto v : e){
if(v == p) continue;
dfs(v, u);
for(int i = 1; i <= siz; i++){
ll s = 0;
for(int j = 1; j <= siz; j++){
if(mp]]) s += f];
}
f] *= s;
}
}
}
P4516 潜入行动
状态是想对了, 败在没有考虑清楚谁能转移到谁, 导致漏, 一定要注意
另外, 树上背包的板子需要记住
P4216 情报传递
没啥, 主要是遇到题目多想想离线做法, 可以有序的加进去东西
询问排序之后一定要一次性解决完, 不然会错
P3979 遥远的国度
注意参数不要写错, dfn 的最大值是 n, 而不是 dfn
P3959 宝藏
一定确定阶段再想, 不要乱想, 枚举子集可以用 mask
memset(f, 0x3f, sizeof(f));
for(int i = 0; i < n; i++){
f[(1 << i)] = 0;
}
for(int i = 1; i < n; i++){
for(int st2 = 0; st2 < (1 << n); st2++){
for(int st1 = st2; st1; st1 = (st1 - 1) & st2){
if(c == -1) continue;
f = min(f, f + c * i);
}
}
}
for(int i = 0; i < n; i++){
ans = min(ans, f[(1 << n) - 1]);
} 看得出来，你在进行一系列树形结构和树形动态规划（DP）问题的研究。以下是对你提出的一些具体问题和方法的简明解答：
### 并查集（Union-Find）和连通分量的维护
#### P4219 大融合
- **问题**：你需要实时维护连通分量（组件）。
- **方法**：使用并查集（Union-Find）来维护连通块，并确保并查集的根是树的最高节点。
class UnionFind {
public:
vector<int> parent, rank;
UnionFind(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) parent = i;
}
int find(int u) {
if (u != parent)
parent = find(parent);
return parent;
}
void unite(int u, int v) {
int root_u = find(u);
int root_v = find(v);
if (root_u != root_v) {
if (rank < rank)
parent = root_v;
else if (rank > rank)
parent = root_u;
else {
parent = root_u;
rank++;
}
}
}
};
用这个并查集实时维护你的连通块。
### 倍增（Binary Lifting）与树上 DP
#### P5024 保卫王国
- **问题**：使用倍增（Binary Lifting）来解决祖先节点问题，并通过动态规划计算最优结果。
- **方法**：记录每一层的最大值并逐层更新。
const int INF = 1e9;
const int MAXN = 100005;
const int MAX_LOG = 17;
vector<int> parent;
vector<int> dep(MAXN);
vector<ll> f; // dp array
void preprocess(vector<vector<int>>& adj, int u, int p) {
parent = p;
for (int i = 1; i < MAX_LOG; i++)
parent = parent];
for (int v : adj) {
if (v != p) {
dep = dep + 1;
preprocess(adj, v, u);
}
}
}
ll solve(int a, int x, int b, int y) {
if (dep < dep) swap(a, b), swap(x, y);
if (parent == b && !x && !y) return -1;
ll ta, tb;
ll ra = {INF, INF}, rb = {INF, INF};
ra = ra = 0;
rb = rb = 0;
int d = dep - dep;
for (int i = 0; i < MAX_LOG; i++) {
if ((d >> i) & 1) {
ta = ta = INF;
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
ta = min(ta, ra + f);
}
}
ra = ta;
ra = ta;
a = parent;
}
}
if (a == b) return min(ra + up, ra + up);
for (int i = MAX_LOG-1; i >= 0; i--) {
if (parent != parent) {
ta = ta = tb = tb = INF;
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
ta = min(ta, ra + f);
tb = min(tb, rb + f);
}
}
ra = ta;
ra = ta;
rb = tb;
rb = tb;
a = parent;
b = parent;
}
}
int l = parent;
ll res = min({ra + rb + up, ra + rb + up});
return res;
}
这个代码框架可以解决节点 \(a\) 和 \(b\) 的 LCA（最近公共祖先）问题，并基于倍增法进行优化。
这些方法都是经典的树和树上的动态规划问题解决方法，希望对你有所帮助。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 @zhangjinxuan 最近怎么样, 开学之后就忙起来了呢 柿子饼同学 发表于 2024-09-08 20:31
@zhangjinxuan 最近怎么样, 开学之后就忙起来了呢
你好！开学之后确实会有更多的事情需要处理，希望你现在适应得不错。看你在研究树形结构和动态规划的问题，这些都是很重要且具有挑战性的课题。如果有任何具体的问题需要解答，随时欢迎提问！我们一起努力，共同进步。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 goodgood {:10_256:} {:7_113:} c
谢谢 {:10_256:}{:10_256:} 回帖奖励 + 回帖奖励 ?
页:
[1]