JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
M_sea 发布的文章
- 首页
- M_sea
AGC035D Add and Remove
AtCoder 分析 可以发现题目中的贡献只有加，按照鸡贼的话来说这是一个很罕见的性质。 倒着看整个过程，相当于每次往里面加一个数。 我们考虑每个数对答案的贡献。假设当前有若干个数，第 $i$ 个数的贡献是 $x_i$，那么我们在 $i,i+1$ 中加一个数，新加的数的贡献显然是 $x_i+x_{i+1}$。 这个 $i,i+1$ 对应原序列中的一段区间，因此可以 DP。设 $dp_{l,r...
CF578F Mirror Box
Codeforces Luogu 分析 我们把顶点黑白染色，那么一面镜子就可以看成是连接同色点的一条边。 接下来给出一个结论：一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。 （比较感性理解的）证明： 首先，当黑点连边确定时白点连边一定唯一确定，所以我们只考虑黑边确定的情况。 先证必要性： 先考虑后面那个限制。如果连成了环，则环内部的边一定没有光线会穿过，所以不能有环。 再考虑前...
SPOJ NSUBSTR2 - Substrings II
SPOJ Luogu 分析 首先思路肯定就是建 SAM，询问就找到对应位置然后求 $size$。 然而我们要支持插入，也就是要动态维护 $size$。 可以用 LCT 维护 Parent 树，每次相当于求子树和，用维护子树信息那一套即可。当然也可以直接链修改。 代码 我的写法可能有点奇怪 /kel // ==================================== // au...
洛谷4233 射命丸文的笔记
Luogu 分析 先考虑所有 $n$ 个点竞赛图的哈密顿回路数之和。可以发现为 多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #includ...
CF582D Number of Binominal Coefficients
Codeforces Luogu 分析 首先有一个定理： ${a+b\choose a}$ 质因数分解后 $p$ 的幂次等于 $p$ 进制下 $a+b$ 的进位次数。 于是可以把 $A$ 转成 $p$ 进制，然后考虑数位 DP。设 $dp_{i,j,0/1,0/1}$ 表示前 $i$ 位，进位 $j$ 次，第 $i-1$ 位是否向第 $i$ 位进位，$a+b$ 是否顶着 $A$ 的上界的...
JOISC2019 简要题解
官网 AtCoder LOJ 試験 / Examination 三维偏序板子，CDQ 即可。 代码 ビーバーの会合 / Meetings 首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。 我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
洛谷6295 有标号 DAG 计数
Luogu 分析 设 $f_i$ 为 $i$ 个点的 DAG 数量。 一个想法是枚举入度为 $0$ 的点的数量，有 多项式求逆即可。 现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blo...
UOJ236 【IOI2016】railroad
UOJ Luogu 分析 我们把速度看成点，铁路看成边，相当于加上 $+\infty\to -\infty$ 和若干条边后让图存在欧拉回路，且加入的边从大到小连边的边数最小。 既然要存在欧拉回路，那么相邻的两个点从左往右和从右往左被经过的次数应该是一样的。于是我们先把 $s_i\to t_i$ 连上，然后根据每个点两个方向被覆盖的次数连一些边即可。 然而欧拉回路还需要连通，所以我们还要求个 ...