文章

「雅礼集训 2017 Day7」事情的相似度 注意到 最长公共后缀 其实是 SAM 上的 LCA ，因此原题变成了询问深度最深的 LCA 。 定义一个前缀在 parent 树上对应的点为其” 结束点”。考虑一个树上的点什么时候可能成为答案，注意到如果这个点的子树内有两个以上的 阅读更多…

「雅礼集训 2018 Day1」树 考虑令 $f_{i,j}$ 表示大小为 $i$ 的树，深度为 $j$ 的方案数。 一般的 DP 合并过程：枚举大小为 $a,b$ 的树，然后把 $b$ 的根接到 $a$ 的根下面。但是这样会算重：打个比方，以 $1$ 为根，儿子为 $2,3$ 的树会被算两次。 不 阅读更多…

简要题意：给你三棵树，二元组 $(x,y)$ 的贡献是 $x,y$ 在三棵树上最短路径经过的边边权之和，求贡献最高的二元组 $(x,y)$ 所产生的贡献。 考虑对第一棵树边分治，注意到边分治的好处就是直接将第一棵树上 $(x,y)$ 的贡献由原来连在一起的变成相对 $x ,y$ 独立的了。 按照&# 阅读更多…

题面 CF1479D Odd Mineral Resource 给定一颗有 $n$ 个节点的树，每一个节点有一种颜色 $a_i$。$q$ 次询问，每次询问点 $x$ 到点 $y$ 的最短路径上是否有一种编号在 $[l, r]$ 的颜色，满足其出现次数为奇数。如果有，输出任意一个；否则输出 -1。 数 阅读更多…

考虑边分治。 边分治的时候考虑跨过中心边的点对 $(x,y)$ 的答案。考虑到 $d_x+d_y-d_{lca(x,y)}$ 其实是 $\frac{1}{2}(dix(x,y)+d_x+d_y)$ ，这下就跟 $lca$ 没关系了。 显然在边分治的过程中 $dis(x,y)$ 也可以被拆开，令 $p 阅读更多…

奇怪的难度。 A 当 $b=2$ 的时候再操作，操作次数是一定的。 因此 $b$ 的变化量很小，暴力枚举。 B 考虑哪个数不同，然后不同后可以选择的区间是什么。 会发现中间夹着的区间选两遍，旁边的选一遍。做前缀和好了。 C 简单转化发现一定要满足 $a=k(b+1),k<b$ 。 枚举 $b$ 阅读更多…

2019 年的尾巴在 2021 年的钟声即将敲响之际被解决了！ 我的肯定不是最快的，但一定是很短的。 没看懂其他人在干什么干脆自己瞎推了。 考虑令 $pos$ 表示全局最高点（如果有多个，就选最右边的那个），容易发现 $[1,pos-1]$ 的点都无法移动到 $pos$ 后面，$[pos+1,n]$ 阅读更多…

序列分块，每个块维护一个 $\sqrt{n}\times \sqrt{n}$ 的矩阵表示这个块中颜色与颜色的距离，再维护每个颜色到左右端点的最短距离。 容易发现查询的时候很好查询，问题在于修改操作：要对每一个块进行处理，光是枚举块就要用掉 $O(\sqrt{n})$ 的时间，那就只能在一个块上留下 阅读更多…

最开始的想法是对序列分块，然后每个块维护一个 $\sqrt{n}\times \sqrt{n}$ 的矩阵表示这个块中颜色与颜色的距离，再维护每个颜色到左右端点的最短距离。 容易发现查询的时候很好查询，问题在于修改操作：要对每一个块进行处理，光是枚举块就要用掉 $O(\sqrt{n})$ 的时间，那就 阅读更多…

看不懂其他题解在写什么东西，那么蒟蒻就来写一篇通俗易懂的吧 首先看到题目的形式： $$\sum\limits_{i = 0}^{n – 1} \sum\limits_{j = 0}^{n – 1} A_i B_j c^{i^2 j^3}$$ 很容易想到一个经典的形式： $$\ 阅读更多…