2026年3月9日
P14763 [Opoi 2025] CCD 的赌局
摘要： 考虑枚举 \(k\)，考虑如何计算答案。 对于已经确定的 \(A,B\)，设 \(A=x\),有 \(B=T-x\)。 如果在某个 \(i\) 处，\(A\times a_i\) 更大有 \(x\times a_i\ge (T-x)\times b_i\)，即 \(\frac xT\ge\frac{ 阅读全文
posted @ 2026-03-09 21:55 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
P15129 [ROIR 2026] 筹码放置
摘要： 发现当一个矩阵完全包含另一个时，那个被包含的矩阵的限制是无效的。 考虑将有效的矩阵拉出来，按照宽度排序，从前到后处理。 设 \(f_i\) 表示前 \(i\) 个矩阵，\(i\) 矩阵内是有点的，\(i+1\) 及以后都没有点的方案数。 转移的时候考虑枚举一个 \(j\) 表示上一个放在了 \(j\ 阅读全文
posted @ 2026-03-09 16:25 Link-Cut_Trees 阅读(13) 评论(0) 推荐(0)
2026年3月6日
20260306紫题训练总结
摘要： A - 树 简单题，直接用线段树维护线性基，暴力合并，最后求一下第 \(k\) 小即可。 B - 等这场战争结束之后 \(Ynoi\) 的题目，想了一个 \(LCT\) 做法，然后假了。话说为什么2014年的题目有珂朵莉 题解 C - Magical Set 简单题，感性理解发现只要最后每个数不一样 阅读全文
posted @ 2026-03-06 22:12 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
P5064 [Ynoi Easy Round 2014] 等这场战争结束之后
摘要： 有撤回操作，可持久化数据结构不好维护，考虑使用操作树。具体的，假设当前是第 \(i\) 次操作，如果是一个撤回 2 x，那么从连一条从 \(x\) 到 \(i\) 的边，否则连一条 \(i-1\) 到 \(i\) 的边。然后以 \(0\) 为根，遍历整颗树，然后操作。 那么现在，只需要一种能维护 \ 阅读全文
posted @ 2026-03-06 22:05 Link-Cut_Trees 阅读(9) 评论(0) 推荐(0)
20260305紫题训练总结
摘要： A - 滚榜 状压题目，场上想到了大部分，但没想到贡献提前算，对性质的挖掘不够深入。 题解 B - Two Faced Edges 场上想到了判断条件，但不会求一条边是否是必经边，对经典 \(trick\) 不了解。 题解 C - 图函数 没看懂，所以没思考。 题解 总结 有些题目前面都能想到，但最 阅读全文
posted @ 2026-03-06 21:37 Link-Cut_Trees 阅读(4) 评论(0) 推荐(0)
P7516 [省选联考 2021 A/B 卷] 图函数
摘要： 先考虑不删边的情况。 考虑对于 \(f(u,G)\)，能做贡献的点符合那些条件。 假设有两个点 \(i,j\) 满足 \(i<j\)，如果 \(j\) 能做贡献，且 \(i\) 能到 \(j\) 或 \(j\) 能到 \(i\)，那么 \(i\) 也一定能做贡献，所以已经被删了。枚举到 \(u\) 阅读全文
posted @ 2026-03-06 21:35 Link-Cut_Trees 阅读(5) 评论(0) 推荐(0)
ARC092F - Two Faced Edges
摘要： 考虑反转一条边 \(u\rightarrow v\) 后强连通分量数量变化的条件。 如果 \(v\) 能到 \(u\) 且 \(u\) 到 \(v\) 必须经过这条边，那么翻转后强连通分量数量会减少。 如果 \(v\) 不能到 \(u\) 且 \(u\) 到 \(v\) 可以不经过这条边，那么翻转后 阅读全文
posted @ 2026-03-06 21:03 Link-Cut_Trees 阅读(5) 评论(0) 推荐(0)
P7519 [省选联考 2021 A/B 卷] 滚榜
摘要： 考虑按照顺序分配 \(b\)，如果分配的 \(b\) 之和不足 \(m\) ，可以把剩下的题目全部给最后一个人，所以对于一个排列，只用考虑祂 \(b\) 之和最小的分配方案。 先考虑一个暴力，设 \(f_{s,i,j,k}\) 表示已分配 \(b\) 的集合为 \(s\) 上一个分配的人为 \(j\ 阅读全文
posted @ 2026-03-06 20:42 Link-Cut_Trees 阅读(4) 评论(0) 推荐(0)
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)