P4219 [BJOI2014]大融合
P4219 [BJOI2014]大融合 题目大意 给定 nnn 点, mmm 个操作如下 加入一条边，保证连边的两点原来不连通 询问有多少条路径通过某条边 1≤n,m≤1051 \leq n,m \leq 10^51≤n,m≤105 分析 网上大多题解都是使用 LCT 来维护, 然而蒟蒻并不会 LCT, 所以这里提供一种仅使用树链剖分的解法. 不难发现某条边路径数为 sizx×(sizr
99_wood's blog
OI常用术语
OI 常用术语 这里会写一些 OI 当中的一些"术语"，想到啥写啥吧。 术语 全称 含义 AC Accept 程序通过所有测试点。 AK ALL KILL 完成了本次题集或比赛的全部题目。 WA Compile Error 程序输出结果与标准答案不符。 TLE Time Limit Exceed 程序运行超时，一般是时间复杂度太高或者死循环。 ML
NFLS集训日志
NFLS 集训日志 5.30 rank: 21/22 score: 100 + 0 + 0 = 100 第一题比较套路, 但是因为 [数据删除] 用了树剖 + 主席树整了 3.9K. 其实可以用树剖 + 树上差分短短几行水过的, 还是经验太少. 但是在写第一题的时候也想到了一个主席树树区间赋值的小 trick, 还是比较有收获的, 不知道有没有用. 第二题动态 DP 没学过, 下午恶补了动态 DP
动态DP学习笔记
动态 DP 学习笔记 很神奇的一个算法, 结合了线段树, 矩阵, 树剖等多个算法, 老缝合怪了. 简介 动态 DP 是一个可以解决带修改的树上问题的利器. 许多小清新的树上问题带上修改的时候就会非常棘手, 使用动态 DP 就可高效地解决了. 另: 本文不讲解全局平衡二叉树, 因为本人也不会. 前置知识 线段树, 基本的矩阵知识(最起码会矩阵乘法), 树剖. 讲解 由于动态 DP 的特殊性, 我们
具体数学5.1 基本恒等式
5.1 基本恒等式 BASIC IDENTITIES (nk)\tbinom{n}{k}(kn) 为二项式系数, 读作"nnn 选取 kkk". 组合解释: 从 nnn 个元素的集合中选取 rrr 个元素的子集的个数. 高中学到的组合数定义为 (nk)=n(n−1)⋯(n−k+1)k(k−1)⋯(1)\begin{equation} \tbinom{n}{k} = \frac
具体数学笔记
具体数学笔记 前言 整了本具体数学读读, 把学到的写下来便于复习. 不会按照书的顺序读, 先读自己想看的, 但会把坑留下慢慢填. 持续更新, 可能会咕. 第1章 递归问题 第2章 和式 第3章 整式函数 第4章 数论 第5章 二项式系数 5.1 基本恒等式 第6章 特殊的数 第7章 生成函数 第8章 离散概率 第9章 渐近式
SXOI2022游记
如果注定要落下, 那就趁现在努力发光. ——SXOI2022 游记 本来不打算写的, 但现在进队了, 还是写了国赛前的最后一个游记吧. 真情实感, 望读者不要以知道结局的态度看故事. 背景 NOIP 通过一系列骚操作和一点实力拿了全省第五, 虽然和前面的四位来说差距不是一点半点. WC 通过河里的时间规划拿了压线 Cu. NOI online 开摆. 山西已经弱出新低了, 省队就 6 个, 去掉