2026年3月2日
20260302紫题训练总结
摘要： A - Secret Message 考虑把前 \(n-1\) 小的边拿出来，如果不联通，直接输出，否则去枚举每一条非树边，计算把这一条边加上后的答案。 具体的，当前枚举到的非树边的两个定点在树上的路径中的边是不能删除的，把这些边长度临时减去 \(inf\)，然后求最所有树边的最小值。这个可以用树剖 阅读全文
posted @ 2026-03-02 18:54 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
P14990 马赛克
摘要： 发现不美观的四个点中行相同或列相同的两个点颜色不同，所以修改的时候把一行或一列全部变成一样的最优，这样相当于这一行（列）无法做任何贡献，即把这一行（列）删掉。考虑枚举那些列删掉，然后把他们真的删掉，暴力统计总方案，然后设 \(f_s\) 表示把集合 \(s\) 内的行留下来的不美观度，转移直接 \( 阅读全文
posted @ 2026-03-02 17:21 Link-Cut_Trees 阅读(21) 评论(0) 推荐(0)
2026年2月27日
20260206动态树LCT
摘要： A - 动态树（LCT） 模板题。 B - Tree II 模板题，要写一堆懒标记，细节很多。 C - 弹飞绵羊 简单题。 D - 洞穴勘测 简单题。 E - 染色 简单题，可以不用 \(LCT\)。 F - 航线规划 简单题。 G - 魔法森林 \(LCT\) 维护最小生成树板子题。 H - 由乃 阅读全文
posted @ 2026-02-27 08:07 Link-Cut_Trees 阅读(5) 评论(0) 推荐(0)
2026年2月24日
20260204线段树&树链剖分&平衡树
摘要： A - 窗口的星星 简单题。 B - 楼房重建 简单题，维护斜率即可。 C - 排序 简单题，二分+平衡树。 D - BZOJ4695 最假女选手 吉司机线段树模板题，要注意区间的最大值等于最小值的情况。 E - 线段树 3（区间最值操作、区间历史最值） 吉司机线段树模板题。 F - 文艺平衡树 平 阅读全文
posted @ 2026-02-24 11:53 Link-Cut_Trees 阅读(8) 评论(0) 推荐(0)
2026年2月7日
20260201决策单调性专题作业
摘要： A - 玩具装箱 板子。 B - 诗人小G 板子，答案有可能过大，要用 \(long\ double\)。 C - Lightning Conductor 考虑正着做一遍，反着做一遍，把绝对值拆开。发现有决策单调性，然后就做完了。 D - 柠檬 发现为了让答案尽可能大，选择的区间左端点和右端点的颜色 阅读全文
posted @ 2026-02-07 19:57 Link-Cut_Trees 阅读(4) 评论(0) 推荐(0)
20260131状压dp
摘要： A - PRZ 简单题，没做。 B - 炮兵阵地 简单题，没做。 C - 学校食堂 设 \(f_{i,j,k}\) 表示前 \(i-1\) 个人全部打完饭了，\(i\) 到 \(i+7\) 的打饭状态为 \(j\) 目前最后一个打饭的人是 \(i+k\) 的最小代价。要开长长。 D - 宝藏 设 \ 阅读全文
posted @ 2026-02-07 19:47 Link-Cut_Trees 阅读(7) 评论(0) 推荐(0)
P3226 [HNOI2012] 集合选数
摘要： 神仙题。 发现不是 \(2\) 的倍数和不是 \(3\) 的倍数的数之间没有限制，可以分开考虑。 以 \(1\) 为例。 构造一个矩阵，左上角为 \(1\)，每个数右边是祂乘 \(3\),下面是祂乘 \(2\)，原问题为求在这个矩阵里选数，不能选相邻的数的方案数，用状压 \(dp\) 随便做，最后把 阅读全文
posted @ 2026-02-07 19:36 Link-Cut_Trees 阅读(6) 评论(0) 推荐(0)
20260130树形dp
摘要： A - 潜入行动 简单题，之前做过。 B - 树上染色 简单题，设 \(f_{i,j,0/1}\) 表示以 \(i\) 为跟的子树，放了 \(j\) 个黑点 \(i\) 放的是黑点/白点的答案，转移的时候贡献提前算一下即可。 C - 最佳团体 简单题，分数规划一下就行了。 D - Riv 河流 设 阅读全文
posted @ 2026-02-07 19:22 Link-Cut_Trees 阅读(6) 评论(0) 推荐(0)
2026年1月16日
20260115紫题训练总结
摘要： A - 荣誉称号 场上想到了转换成完全二叉树，但没有发现大量点同余这一性质…… 题解 B - training 训练路径 经过转换，问题变成求没有偶欢的最大生成仙人掌，必须包含原树边，有因为每个点再原树上只有 \(10\) 个边，所以可以状压，然后就做完了。 C - 氪金手游 设 \(f_{i,j} 阅读全文
posted @ 2026-01-16 22:39 Link-Cut_Trees 阅读(9) 评论(0) 推荐(0)
P4620 [SDOI2018] 荣誉称号
摘要： 看到有很多除以 \(2\)，容易想到把原问题转化成二叉树上的问题。 考虑令 \(x\) 的父亲为 \(\lfloor\frac{x}{2}\rfloor\)，问题就变成了对于每个点，它包括自己，向下延伸 \(k+1\) 个点（如果有的话）的点权和模 \(m\) 等于 \(0\)。 先讨论 \(k=2 阅读全文
posted @ 2026-01-16 22:28 Link-Cut_Trees 阅读(20) 评论(0) 推荐(0)