建议在右侧的设置按钮中打开阅读器模式阅读 可能是学过的唯一一个紫模板算法吧 虽然基于 Splay，但是并没有 Splay 难调 LCT 简介 LCT 是一种解决动态树问题的算法，就是在树链剖分的基础上可以断开或连接边（当然保证还是一棵树）。 那么对于这种问题，自然就不能用重链剖分来解决，这时便需要一个新的组合——实链剖分+Splay 模板题看这里 实链剖分 对于一个点连向它所有儿子的边，我们自己选择一条边进行剖分，我们称被选择的边为实边，其他边则为虚边。对于实边，我们称它所连接的儿子为实儿子。对于一条由实边组成的链，我们同样称之为实链 —— Oi-Wiki Splay 先放两篇博客

下文中以 ⟨⟩\langle\rangle⟨⟩ 表示矛盾的集合，[][][] 表示题目给定的的集合 定义 2-SAT，简单的说就是给出 nnn 个集合，每个集合有两个元素，已知若干个 ⟨a,b⟩\langle a,b \rangle⟨a,b⟩ ，表示 aaa 与 bbb 矛盾（其中 aaa 与 bbb 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 nnn 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。 ——来自oiwiki 解法 对于 2-sat 问题，我们可以将它抽象成一个图论问题，建图来完成。 建图 首先考虑如何建图，对于两个集合内 [a,b

C,空间算错了，要不然就AK了…… 额……个人认为是普及- simsimsim 普及，过于简单了 A 是水 dp，还是原题（？） 设 dpi,jdp_{i, j}dpi,j​ 为第 iii 个取 jjj，则有 dpi+1,j×k=∑dpi,jdp_{i+1,j \times k}= \sum dp_{i,j}dpi+1,j×k​=∑dpi,j​ 复杂度为 O(n2ln⁡n)\mathcal{O(n^2 \ln n)}O(n2lnn) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2

据说是noip难度，好难…… T1 过了，但是被余老师的神机卡爆了……（fuck,不会用Linux的机子吗）。 好吧，去重测了。 我显然打得不是std的做法。 额……一道sb括号匹配题（这种题都这样）。 就是求每个包括 iii 的合法括号序列数量与 iii 的积之和。 有三种做法，先说std： 对于每一个 iii，找到一个从后面跟它组成合法括号序列的最大串与前面紧贴它的最大串，相乘，再算上从两边包裹它的括号，就可以计算了，复杂度预处理都是 O(n)\mathcal{O(n)}O(n)（卡满 10710^7107 的屑出题人）显然我的做法更优雅。实际实现还是挺复杂的…… 第二种做

又挂分了……

高斯消元 给定一组 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}

数位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 数位dp！！！数位dp！！！ 核心思想：按字典序由高位到低位计算 看图 -43210-656430123456…求 000 到 656436564365