Odalys

一棵以 $1$ 为根的树，边权未知，你可以进行三种操作： 询问一个点的 dfn 询问一条路径上边权和 删除所有度数为 $1$ 的点，并重标号 要求在 $142$ 次操作内得到当前树的边权总和。 从这题中，我们得到一个关于 $dfn$ 的小 $trick$ ，就是若你知道一些关键点的 $dfn$ ，那么这些关键点的生成子图边权和等于按 dfn 排序后相邻点距离加最后一个点与第一个点距…

~好像是又咕了一天~ 试考虑这样一类生活中常见的情境： 活力四射的体育课，欢乐的自由活动时间，由老师分配好的 A 班活动场地中却迎来了 “不速之客”–其它班的同学由于羡慕 A 班拥有光照条件更为良好的场地，而不经与 A 班同学商量就擅自在场地中打起了球。由于活动场地本就十分狭小，这一行为更是严重影响了 A 班同学们的正常活动，而若将他们全部加入 A 班的活动…

一棵树，每个点有个颜色，可以合并两个颜色 $(x,y)$，效果为把所有颜色 $y$ 的改为 $x$ ，求最少的合并次数使得存在一个颜色联通块内部无其他颜色。 大概思路是，若一个颜色 $x$ 内部有其它颜色 $y$ ，那连边 $x\to y$ ，代表如果要以 $x$ 为首都必须合并 $y$ 具体的，我们把一个颜色的点按 dfn 排序，然后相邻的点路径上连边可以把这个颜色块的生成子图都覆盖一遍…

JOISC 2017 Day1

由于构造与思维题想出来后编程复杂度接近与 $0$ ，于是开个合集 定义 $f(x)$ 为 $x$ 各数位之和，构造一组 $l, r$ 使得 $\sum\limits_{i=l}^{r} f(i) \equiv 0 \pmod{a}$ ，其中 $a$ 为给定值。 发现 $f(x + 10^{18}) = f(x) + 1$ 令…

求让一张图变成强联通图至少增加多少边并输出边， 每个点只有一个出度。 这种最优化问题不妨先考虑问题的下 / 上界，再寻找有无反例使得下 / 上界不能取到 本题中，由于每个点只有一个出度这个限制，也就是 $n$ 个点 $n$ 条边，不难发现会连出一张基环内向树森林。 考虑答案的下界一定是以环为根时，每棵树的叶子点数。因为这些点的入度为 $0$ ，想让图强连通起码得使它们的…

a+b = (a & b) + (a | b)\\ a+b = (a ^ b) + 2 (a & b)\\ a ^ b = (a | b) - (a & b)\\

一些坐标上的问题可以考虑在每个坐标上取一个点，将其转换为序列问题。 坐标系上维护三种操作：加点，删点，询问一个点右上角最靠左，最下的一点 只会大力 $KDT, CDQ$ 输光了 其实考虑询问以最靠左为第一关键字，那么我们从 $(x_0, y_0)$ 找到一个最小的 $x$ 若这一列存在成立的点，那答案就在这一列找到第一个大于 $y_0$ 的就好 这启发我们每个 $x$ 列保留最…

树上关键点的生成子图等于按 dfn 序后相邻点距离加最后一个点与第一个点距离 一棵树，树边带权，初始每个点都为白色，三种操作：染白，染黑，询问所有黑点的生成子图边权和。 口胡： 考虑加入一个点的贡献，发现是到之前生成子图中某点的距离，然后要使用很复杂的东西来维护，然后就不会做了。 实际上可以考虑全局来看这个问题，发现把黑点的 $dfn$ 放一起排序后相邻点距离加…

数据结构题先想离线做法 $n$ 个人，每个人有地位 $r_i$ 和年龄 $a_i$ 。定义一个小组组长为小组中地位不严格最高，年龄与其他成员差距不超过 $k$ 。$m$ 组询问 $(x,y)$ 表示询问第 $x$ 个人与第 $y$ 个人分到同一组的情况下，这个小组最多能分到多少人。 查 FourteenObsidian 表得到的 DS 好题 一开始一直考虑在直接做，然后胡了个树套树，然后不…