2026年1月14日
20260114紫题训练总结
摘要： A - Pastiri 简单贪心，切了。 B - holiday 假期 感性理解一下发现有决策单调性,用主席树维护即可。因为各种神秘原因，我做了一个多小时，\(T3\) 直接没时间思考了T_T C - Mousetrap 考虑求出每个点，把老鼠从这里开始，赶到某个叶子，再赶回来的最小代价，最后二分一 阅读全文
posted @ 2026-01-14 22:23 Link-Cut_Trees 阅读(16) 评论(0) 推荐(0)
20260113紫题训练总结
摘要： A - 小凸玩密室 神秘题，切了 题解 B - 苹果树 考虑计算每一条边的贡献。具体的，枚举边的一端的子树大小和父亲，用一些奇怪的式子去计算。 C - 潜入行动 简单的树形背包，切了。 总结 做题速度要加快，准确率要提高，数学要提高。 阅读全文
posted @ 2026-01-14 22:03 Link-Cut_Trees 阅读(6) 评论(0) 推荐(0)
P4253 [SCOI2015] 小凸玩密室
摘要： 将状态刻画为 \(f_{i,j}\) 表示点亮完 \(i\) 的子树，然后去到 \(j\) 的最小代价。转移是好做的。每个点再点亮完祂的子树后只有可能去到祂的祖先或祖先的儿子，因为给出的树是完全二叉树，所以状态数是 \(n\log(n)\)。 但是题目有一个很耐受的条件：可以任选一个点开始。考虑枚举 阅读全文
posted @ 2026-01-14 21:57 Link-Cut_Trees 阅读(10) 评论(0) 推荐(0)
2026年1月12日
20260112紫题训练总结
摘要： A - 独特的树叶 树哈希板子，切了。 B - Binary Code 字典树和前缀和优化建图，没调完T_T。 C - Antifibonacci Cut 神仙题，做不了一点。题解 阅读全文
posted @ 2026-01-12 21:44 Link-Cut_Trees 阅读(7) 评论(0) 推荐(0)
CF1743G Antifibonacci Cut
摘要： 空间限制非常小。考虑对于每一个点 \(i\)，找到所有 \(j\) 满足 \([i...j]\) 为斐波那契字符串的前缀。 斐波那契字符串的第 \(i\) 为是可以计算的，代码如下（fbnqsl 表示斐波那契数列） int js(int w){for(int i=31;i>1;i--) if(w>f 阅读全文
posted @ 2026-01-12 21:44 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
P3515 [POI 2011] Lightning Conductor
摘要： 考虑正着做一遍，反着做一遍，绝对值就被拆开了。下面只讨论正着做。 \(f(x)=\sqrt{x+1}-\sqrt x\) 是单调递减的，所以对于 \(j_1<j_2\)，一定能找到一个 \(w\) 使得对于任意 \(i\ge w\)，都有 \(h_{j_2}+\sqrt{i-j_2}\ge h_{j 阅读全文
posted @ 2026-01-12 21:26 Link-Cut_Trees 阅读(8) 评论(0) 推荐(0)
20260111紫题训练总结
摘要： A - Dynamic Diameter 场上一直在想 \(LCT\) 和 \(DDP\)，发现虚子树非常难维护，\(reverse\) 还会出现一些奇奇怪怪的问题，\(DDP\) 根本不会。 题解 B - Sjeckanje 场上一直在想 \(DDP\)，发现不会。 需要差分，将问题转化，然后用线 阅读全文
posted @ 2026-01-12 21:26 Link-Cut_Trees 阅读(4) 评论(0) 推荐(0)
P6845 [CEOI 2019] Dynamic Diameter
摘要： 钦定一个根，考虑用数据结构维护维护节点深度，这是好做的。再用一颗线段树维护直径，对于修改，把跟节点到修改区间上的点全部 \(push\_up\) 一次就可以了。 代码 #include<bits/stdc++.h> using namespace std; namespace IO{ templat 阅读全文
posted @ 2026-01-12 21:12 Link-Cut_Trees 阅读(7) 评论(0) 推荐(0)
2026年1月9日
20260109紫题训练总结
摘要： A - 小 N 的独立集 洛谷 - P8352 简单树形 \(dp\)，考虑设 \(f_{u,i,j}\) 表示以 \(u\) 为根的子树不选 \(u\) 最大权独立集为权值和为 \(i\)，可选可不选 \(u\) 最大权独立集为权值和为 \(i+j\)。转移是简单的。 但是，本题卡常，转移前判断一 阅读全文
posted @ 2026-01-09 21:31 Link-Cut_Trees 阅读(10) 评论(0) 推荐(0)
20260107紫题训练总结
摘要： A - DYN-Dynamite 洛谷 - P3523 神秘题，没场切。 题解 B - 高速公路现代化 Highway modernization 洛谷 - P3596 枚举割边，最小值的割边一定在直径上，计算出两颗树的直径，然后就可以随便做了。 考虑求分裂后的两棵树的直径。可以先从原树直径的两个端 阅读全文
posted @ 2026-01-09 21:20 Link-Cut_Trees 阅读(6) 评论(0) 推荐(0)