2026年3月23日
20260323紫题训练总结
摘要： A - 吊灯 结论题，场上想到了一个错误的结论，认为不可做，跳了。 题解 思维需要更严谨，的到结论后最好验证一下，或证明祂。 B - 消棋子 看完题就知道大概怎么做，仔细思考后发现挺简单的，但是比较难写，而时间有比较紧，所以没有写代码。 题解 C - 九连环 推出来的递推式，直接写矩阵乘法+\(FF 阅读全文
posted @ 2026-03-23 20:29 Link-Cut_Trees 阅读(2) 评论(0) 推荐(0)
P2351 [SDOI2012] 吊灯
摘要： 考虑对于一个大小 \(x\) 如何判断是否合法。 有结论：子树大小是 \(x\) 的倍数的点的数量一定要是 \(\frac nx\)。 规定：称 “子树大小是 \(x\) 的倍数的点”为 \(A\) 类点。 必要性 首先，如果 \(A\) 类点的数量小于 \(\frac nx\)，那么一定不可能。使 阅读全文
posted @ 2026-03-23 20:16 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
P3341 [ZJOI2014] 消棋子
摘要： 挺简单的一道题目，代码实现比较复杂。 第一问 每一行，每一列用 \(set\) 维护，直接模拟 第二问 考虑贪心，一对点删了一定比没删优，所以可以先枚举那些点对可以直接删除。 然后考虑一对点删除了之后又那些点对可能会从不能删变成能删。 显然，对于删掉的两个点，祂们分别向上，向下，向左，向右碰到的第一 阅读全文
posted @ 2026-03-23 19:49 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
P3341 [ZJOI2014] 消棋子
摘要： 首先要找到一个策略，能用最少步数揭开这个东西。 发现对于任意 \(x\)，第 \(1\) 到 \(x-1\) 个环都不受 \(x\) 的影响。 假设我们要解 \(n\) 个环，可以先把前 \(n-2\) 个环卸下，把第 \(n\) 个环卸下，把前 \(n-2\) 个环装上，把前 \(n-1\) 个环 阅读全文
posted @ 2026-03-23 17:24 Link-Cut_Trees 阅读(6) 评论(0) 推荐(0)
2026年3月21日
20260320紫题训练总结
摘要： A - 领导集团问题 做过，但是因为一些原因没调出来。 题解 一些 \(trick\) 需要记下来，比如这道题处理下穿懒标记的方法。 B - 货物列车 / Freight Train 方向完全错了，在想网络流，一些关键的性质没有挖掘出来。 题解 C - 拓扑 组合数学神题。需要用到子树内拓扑序数量， 阅读全文
posted @ 2026-03-21 15:29 Link-Cut_Trees 阅读(5) 评论(0) 推荐(0)
P14016 [ICPC 2024 Nanjing R] 拓扑
摘要： 首先有结论：\(u\) 的子树内拓扑序的数量为 \(\frac{sz_u!}{\prod_{v\in subtree(u)}sz_v}\)。 设 \(f_{u,i}\) 表示暂时把 \(u\) 子树内的点都删掉，\(u\) 在拓扑序中排第 \(i\) 的方案数。转移： \[\begin{array} 阅读全文
posted @ 2026-03-21 15:01 Link-Cut_Trees 阅读(1) 评论(0) 推荐(0)
2026年3月20日
P14300 [JOI2023 预选赛 R2] 货物列车 / Freight Train
摘要： 容易发现，除了移动距离最近的那一次，剩下的每一次都会把 \(w\) 个货物运会 \(1\) 号点。 考虑 \(dp\) 设 \(f_{i,j,k}\) 表示在后 \(i\) 个中运货物，目前装了 \(j\) 个，移动了 \(k\) 步的最大价值。 转移 \(f_{i,j,k}=\left\{\beg 阅读全文
posted @ 2026-03-20 22:18 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
P4577 [FJOI2018] 领导集团问题
摘要： 容易写出 \(\mathcal O(n^2)\) 的 \(dp\)：设 \(f_{u,i}\) 表示在 \(u\) 的子树内选数，最小的数是 \(i\) 能选最多的个数。转移：\(f_{u,\min(i,j)}=\max(f_{u,i}+f_{v,j})\)。 考虑把 \(u\) 选上 \(f_{u 阅读全文
posted @ 2026-03-20 22:04 Link-Cut_Trees 阅读(7) 评论(0) 推荐(0)
2026年3月18日
20260317紫题训练总结
摘要： A - 传统艺能 题解 考场上没有仔细想，大概思路也是拆贡献，但是是按照操作拆的，方向反了。 B - 体育课 题解 考场上在想势能线段树，对时间复杂度的计算不够准确。 C - 局部极小值 题解 场上在想把数字压起来，没发现最多只有 \(8\) 个局部极小值，对性质的挖掘不够深入。 阅读全文
posted @ 2026-03-18 22:08 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
P3160 [CQOI2012] 局部极小值
摘要： 注意到地图上最多能放 \(8\) 个局部极小值，考虑 \(dfs\) 出所有放置局部极小值的地图，输入中给定的局部极小值的点再这个地图中也一定是局部极小值，其它不管。 在当前地图中，我们定义局部极小值点为这个点在这张地图中必须成为局部极小值。 然后对这个图做 \(dp\)，设 \(f_{i,j}\) 阅读全文
posted @ 2026-03-18 22:03 Link-Cut_Trees 阅读(2) 评论(0) 推荐(0)
下一页