20260709杂题训练

A - 世界树题意给定一棵nnn个结点的树边权均为111。有qqq次询问每次给出mmm个关键点临时议事处。对于树上任意结点选择距离它最近的关键点若距离相同则选择编号较小的关键点。每次询问需要输出这mmm个关键点各自管辖的结点数。数据范围n≤3×105n \le 3\times 10^5n≤3×105q≤3×105q \le 3\times 10^5q≤3×105∑m≤3×105\sum m \le 3\times 10^5∑m≤3×105。先构造出虚树再分讨处理。具体的对于每次虚树上的点先用一次搜索求出到达它最近的临时议事处。接下来相当于给很多条形如链旁边挂上几颗树的求答案贡献显然只有那条主链上的会有影响对于主链上一个点向外挂的子树和这个点所选的临时议事处是一样的。然后还有一个很显然的结论对于一条这样的链它们的临时议事处必然是上面一段下面一段不同的。只有两个不同的答案二分计算即可。用子树大小统计数量贡献。B - Monster-Go题意有505050种怪兽类型编号0∼490 \sim 490∼49NNN个玩家每人有一个恰好包含121212种类型的清单。所有玩家结伴依次访问怪兽巢穴每个巢穴对应一种类型类型可重复访问每次访问时所有玩家都会收集该类型。要求设计NNN个清单使得无论访问顺序如何最终都恰好只有一个人最先集齐自己的清单不会出现平局。输出任意合法方案。数据范围N≤50N \le 50N≤50。相当于要构造nnn大小为121212个集合集合元素小于505050任意两个集合它们并集除去交集是任意一个集合的子集。赛时没有仔细往下面想。首先可以观察到用[0,12][0,12][0,12]分别塞到131313个人当中每个人去除其中一个这样可以满足题意。推广一下121212的因数均可以这样构造。也就是13 个点 13 个人。14 个点 7 个人。16 个点 5 个人。18 个点 3 个人。12 个点 1 个人。然后跑一遍背包求解。但是只有505050个数这并不能把所有都给覆盖。可以继续推广本质上上面这一堆方案都是在给每个人轮流去除 1 段。然而去除k1k1k1段也是可以的。然后就可构造出来了。C - 甲苯先生的滚榜题意有mmm个选手初始每题未通过罚时为000。按顺序发生nnn次 AC 事件每次事件给出选手编号RiaRiaRia和罚时增量RibRibRib表示该选手通过一题其通过题数111总罚时RibRibRib。每次事件后输出当前有多少选手的排名严格高于该选手排名规则题数多者优先题数相同则罚时少者优先完全相同的并列不计算在内。数据由给定随机函数生成保证所有选手总罚时不超过1.5×1061.5\times 10^61.5×106。数据范围T≤15T \le 15T≤15m≤105m \le 10^5m≤105n≤106n \le 10^6n≤106罚时总和≤1.5×106\le 1.5\times 10^6≤1.5×106。直接用平衡树维护。每次删除再添加添加前 FHQ-treap 分裂时统计一下比它前的数量。O(Tnlog⁡m)O(Tn\log m)O(Tnlogm)总结在赛时写出了两道比较板的题T1T3。对于 T2 这种 Ad-hoc一般都是想从特殊性质出发不断观察性质。通过简单的情况不断推广到一般从而解决问题。