建议在右侧的设置按钮中打开阅读器模式阅读 虽然基于 Splay，但是并没有 Splay 难调 LCT 简介 LCT 是一种解决动态树问题的算法，就是在树链剖分的基础上可以断开或连接边（当然保证还是一棵树）。 那么对于这种问题，自然就不能用重链剖分来解决，这时便需要一个新的组合——实链剖分+Splay 模板题看这里 实链剖分 对于一个点连向它所有儿子的边，我们自己选择一条边进行剖分，我们称被选择的边为实边，其他边则为虚边。对于实边，我们称它所连接的儿子为实儿子。对于一条由实边组成的链，我们同样称之为实链 —— Oi-Wiki Splay 先放两篇博客，毕竟这种被 FHQ 吊打的数据结构不太想写，也只需要会一点点就好了 「学习笔记」平衡树——splay 一 「学习笔记」平衡树——splay 二 算法讲解 思路 对于一棵树，我们将它剖成若干条实链： 如图所示，整棵树被剖分成{1,4,7},{2,6,10},{3},{5},{8},{9}这些实链。 所以我们可以以深度为关键字，对每条连用一棵 Splay 来维护。 但是我们如何对于原树进行维护？可以对每一棵 Splay 的链顶的 ...

闲话 前几天才知道要打 NOIp，还是挺没想到，不过 11.30 的半期考试还有点慌~~ 才开始写，主要是前几天没空…… Day -1 额，没机房可以用，所以全是 ABC 的 F 题的“信心赛”也没打…… 在试机的场子颓颓颓~~~ 帮 @Celestial_cyan 写了一个暴力，希望 CBOI Round 1 能顺利出出来吧。 复习一下 FHQ，还是写了zz错误，无语了……希望考场不要写挂。 Fire 跟我们讲的提前下课也不兑现，sh*t。 Day 0 e……应该会比提高组打的高吧…… T1 属于简单题，一眼秒了（但是看错题面的意思所以一眼了一个半小时）。 T2 一眼了 60pts，但是考虑漏了情况所以又一眼了两个多小时。 T3、T4 打的 5pts 和 8pts……时间来有点不及吧。 自己估分大概是 100 + 60 + 5 + 8 = 173 Day 11.19 乐，输麻了…… 云斗测出来是 100 + 40 + 0 + 0 = 140 洛谷测出来有 100 + 50 + 0 + 0 = 150 输麻了。

前言 数论总是学了就忘，趁着没忘赶紧写出来 扩展中国剩余定理 为什么是扩展呢，因为不扩展的太菜了，从本质上来说，两者的做法有着本质上的区别，CRT 依靠构造，EXCRT 则是合并（由此可见 EXCRT 适用性更广的原因）。而且时间复杂度一样，码量也区别不大，因此可能还是 EXCRT 更好用一点 证明 （注：本文方法和网上的略有不同） {x≡c1(mod m1)x≡c2(mod m2)⋮x≡cn(mod mn)\begin{cases} x\equiv c_1(\rm mod\ m_1)\\ x\equiv c_2(\rm mod\ m_2)\\ \vdots\\ x\equiv c_n(\rm mod\ m_n)\\ \end{cases} ⎩⎨⎧​x≡c1​(mod m1​)x≡c2​(mod m2​)⋮x≡cn​(mod mn​)​ 因为没了 mmm 两两互质的限制，因此只能用合并解决。 首先拿出两个式子： x≡c1(mod m1)x≡c2(mod m2)\begin{aligned} x\equiv c_1(\rm mod\ m_1)\\ x\equiv c_2(\rm mod\ ...

下文中以 ⟨⟩\langle\rangle⟨⟩ 表示矛盾的集合，[][][] 表示题目给定的的集合 定义 2-SAT，简单的说就是给出 nnn 个集合，每个集合有两个元素，已知若干个 ⟨a,b⟩\langle a,b \rangle⟨a,b⟩ ，表示 aaa 与 bbb 矛盾（其中 aaa 与 bbb 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 nnn 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。 ——来自oiwiki 解法 对于 2-sat 问题，我们可以将它抽象成一个图论问题，建图来完成。 建图 首先考虑如何建图，对于两个集合内 [a,b][a,b][a,b]， [c,d][c,d][c,d]，若 a,ca, ca,c 矛盾，则选 aaa 就只能选 ddd，选 ccc 就只能选 bbb。以此为基础，则可以连接 a→da \rightarrow da→d， c→bc \rightarrow bc→b 两条有向边，对于 P4782 【模板】2-SAT 中的四种条件，我们可以以以下方式建边: a, b, true, true a1→b0 ...

闲话 本来早就想写了，但写太早了意义不大，就从今天开始吧…… Day 10.16 好颓，补不动题…… 突然感觉自己还有好多不会，特别是数学……DP 不咋好，很慌…… Day 10.17 和 nk / bz / yc 的打比赛，可是没有新电脑……多了 20 多个蓝屏的机会…… Day 10.18 已经完全停课了，上午学了扫描线，可是二维数点被卡常，无语…… 下午模拟赛为了五分的部分分没开 30 的 floyd，血亏…… A 考了矩阵加速 DP，一点都不会，去学一下，要是考了就萎了 Day 10.19 炸裂，叕 调不出来题了……，无语，今天总不能一上午只做一道题吧 C，我是智障，写矩阵快速幂竟然没有 a=qmi(a,n) …… 发现一道大佬题 P1707 刷题比赛，切掉~~ 吃完饭了还没切掉…… 切掉了，是智障错误…… ddy 来机房搞事情了，菜~~ 看了看 NOI 大纲，突然又自信了，晚上再复习几道版题就差不多了 颓颓颓…… 服了，调不出一道双向广搜…… Day 10.20 最后一天了，加油呀 模拟赛挂了 30 分，（还是普及组），只有 rk3 是不是没救了？壮娃 @songsz ...

高斯消元 给定一组 nnn 个未知数的方程组，有 nnn 个方程 {a1,1x1+...+a1,nxn=b1...a1,1x1+...+an,nxn=bn\left\{\begin{matrix} a_{1,1}x_{1} + ... +a_{1,n}x_{n} = b_{1} \\ ... \\a_{1,1}x_{1} + ... +a_{n,n}x_{n} = b_{n} \end{matrix}\right.⎩⎨⎧​a1,1​x1​+...+a1,n​xn​=b1​...a1,1​x1​+...+an,n​xn​=bn​​ 转化到下面的表格 x1x_{1}x1​ x2x_{2}x2​ ......... xnx_{n}xn​ b1−nb_{1-n}b1−n​ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ <注：下文中 ?≠0? \ne 0?=0 > 唯一解： x1x_{1}x1​ x2x_{2}x2​ ......... xnx_{n}xn​ b1−nb_{1-n}b1−n​ ？ 0 ...

数位DP 引入 给你数字l、r，求l到r之间有多少个数 弱智题？ 方法一 从 lll 开始，暴力枚举到 rrr , 时间 Θ(n)\Theta(n)Θ(n) 方法二 公式， ans=r−l+1ans = r - l + 1ans=r−l+1 方法三 ans=res(r)−res(l−1)ans = res(r) - res(l - 1)ans=res(r)−res(l−1) resresres 如何求？ 数位dp！！！\Huge \text{数位dp！！！}数位dp！！！ 核心思想：按字典序由高位到低位计算 看图 - 4 3 2 1 0 - 6 5 6 4 3 0 1 2 3 4 5 6 … 求 000 到 656436564365643 中有多少个小于 656436564365643 计算第 444 位： - 4 3 2 1 0 - 6 5 6 4 3 0 10410^4104 1 10410^4104 ...