2026年3月18日
P2496 [SDOI2012] 体育课
摘要： 考虑使用分块。 假设有一个修改 \(l,r,t\)，那么所有在 \([l,r]\) 之间的 \(i\),祂的值会变大 \((i-l+1)\times t\)，即 \(i\times t+t-l\times t\)，这个可以拆成 \(i\times t\) 和一个常数。 在同一个块内，考虑两个点 \( 阅读全文
posted @ 2026-03-18 21:53 Link-Cut_Trees 阅读(2) 评论(0) 推荐(0)
P6630 [ZJOI2020] 传统艺能
摘要： 首先，期望总结点个数等于每个点有标记的期望相加，这是期望的可加性。 那么考虑拆贡献，枚举一个点 \(u\)，用矩阵乘法优化 \(DP\) 计算祂的期望。 设状态： \(f_{i,1}\) 表示操作了 \(i\) 次，\(u\) 祖先没有懒标记，\(u\) 没有懒标记的期望。 \(f_{i,2}\) 阅读全文
posted @ 2026-03-18 21:31 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
2026年3月16日
P14265 [ROI 2015 Day1] 企鹅研究
摘要： 把一个长度为 \(x\) 的连续段变成一个数 \(x\)，这样就得到了一个序列，每次可以选择连续的 \(3\) 个数 \(a_i,a_{i+1},a_{i+2}\)（或 \(2\) 个），把祂们合成一个数 \(a_i+a_{i+2}-a_{i-1}\)，代价为 \(a_i\)，可以操作无限次，求最小 阅读全文
posted @ 2026-03-16 17:24 Link-Cut_Trees 阅读(15) 评论(0) 推荐(0)
P14346 [JOISC 2019] 指定城市 / Designated Cities
摘要： 观察数据发现有 \(E_1=1\) 和 \(E_1=2\) 的数据。 那么分类讨论 当选的节点数量为 \(1\) 时： 直接枚举选定的点，然后计算。 当选的节点数量为 \(2\) 时： 设只选 \(u\) 时的答案为 \(z_u\)，则选两个点 \(u_1,u_2\) 的代价为 \(\frac{z_ 阅读全文
posted @ 2026-03-16 17:20 Link-Cut_Trees 阅读(4) 评论(0) 推荐(0)
2026年3月12日
20260312紫题训练总结
摘要： A - 棋盘覆盖 把几道简单题合起来，变成一道神秘题，还卡常。 题解 B - 密室之门 简单题，但是场上无法观察数据范围，而且认为数论题目不可战胜，再加上第一道大码量题目，没有仔细思考。 题解 C - 飞镖 大分讨，细节多，还算简单。 题解 总结 写代码，条代码速度要加快，不要害怕数论。 阅读全文
posted @ 2026-03-12 22:13 Link-Cut_Trees 阅读(5) 评论(0) 推荐(0)
P3277 [SCOI2011] 飞镖
摘要： 大分讨。 首先有结论 \(5k\) 一下的分数除了 \(5k-1\) 都可以用两次凑出来（不打红心） 以下用 \(num\) 代表数字，\(heart\) 代表红心。 \(num\ num\ num\) 前两个至少有一个不是 \(3\) 倍。 把前两个合起来，最有一个只能是偶数，单独算。 前两个都是 阅读全文
posted @ 2026-03-12 22:05 Link-Cut_Trees 阅读(3) 评论(0) 推荐(0)
P2284 [HNOI2003] 密室之门
摘要： 设当前的密室第 \(i\) 个转盘初始为 \(c_i\)。 \(a,n\) 很小但是场上看不到，考虑枚举两个转盘，设他们为 \(i,j\)，考虑判断祂们是否合法。 容易列出方程 \(\begin{cases}x\equiv c_i\pmod {b_i}\\x\equiv c_j\pmod {b_j} 阅读全文
posted @ 2026-03-12 21:41 Link-Cut_Trees 阅读(2) 评论(0) 推荐(0)
P6407 [SDOI2012] 棋盘覆盖
摘要： type A 直接跑二分图匹配。 type B 猜结论：一定能铺满。 考虑分治，每次将矩阵平均分成 \(4\) 份，每一份一样大，考虑放一个块覆盖祂们中的 \(3\) 个格子。只要每次都把空的格子留给已经有障碍的矩形，那么在递归时每个矩形都恰好有一个障碍，当分治到 \(2\times2\) 后就结束 阅读全文
posted @ 2026-03-12 21:18 Link-Cut_Trees 阅读(4) 评论(0) 推荐(0)
2026年3月9日
20260309紫题训练总结
摘要： A - 筹码放置 比较简单的 \(DP\)，由于看错题做了很久。 题解 B - CCD 的赌局 单峰函数这个性质没想到，时间也不够。 题解 C - 颜色 Colors 做前面的题目用时太久了，没看。 题解 总结 做题速度要加快，审题要更仔细。 阅读全文
posted @ 2026-03-09 22:15 Link-Cut_Trees 阅读(12) 评论(0) 推荐(0)
P14532 [RMI 2018] 颜色 / Colors
摘要： 考虑从编号大的数开始完成任务，\(u\) 能将祂的颜色传递到 \(v\)，必须满足祂们之间的某条路径上的点的编号小于等于 \(u\)。 假设目前在完成所有 \(b_i=x\) 的任务，那么可以经过的点 \(u\) 必须满足 \(b_u\le x\le a_u\)，可以看作一个点在 \([b_u,a_ 阅读全文
posted @ 2026-03-09 22:11 Link-Cut_Trees 阅读(2) 评论(0) 推荐(0)