zhangxixi的博客

一些高级搜索优化技巧 A* 我们考虑bfs+优先队列优化寻找最短路的过程。 我们有三类点（本质是状态）： 当前已经确定点（1） 队列中的点（2） 还未探索过的点（3） 初始时起始点在1类点，终止点为3类点。当终止点变成1类点时，我们就可以直接结束。 我们考虑会优先把哪个2类点丢到1类点中：假设当前到某个2类点的最优是（已走路径长度） f(i)f(i)f(i)，我们会选择**f(i)f(i)f(i) 最小的点**进行下一步。 以上是我们传统的做法，接下来介绍 A* 我们考虑我们增加一个预测函数 g(i)g(i)g(i)，代表从 iii 号点到终点预估需要的代价是 g(i)g(i)g(...

平衡树全家桶 2 笛卡尔树 仅支持静态，不支持动态 建树过程：单调栈。对于每个新加入的点 xxx 最后pop掉的点 yyy，则 yyy 是 xxx 左子树 最后pop不走的点 zzz，则 xxx 是 zzz 右子树 用于静态区间最大值之类的维护 Size Balanced Tree 树的性质：叔叔比侄子大，即： 1234size(N.left) >= size(N.right.left)size(N.left) >= size(N.right.right)size(N.right) >= size(N.left.left)size(N.right) >= s...

平衡树全家桶 1 Treap Treap = Tree（BST）+ Heap 左旋 右旋 这两个显然，推一推就行 我们对每个节点附一个随机权值，用于维护小根堆/大根堆 每次，先修改（按照二叉搜索树的方式），然后转转转，使其符合堆 FHQ-Treap 无旋Treap 同样有BST和Heap的性质。（只要是Treap，其随机权值就给了其深度为log的保证） 我们有两种操作： spilt(root, val) 按照val划分 如果当前点 <= val，则 split(R, val)，并把得到的其中一棵树连为根节点的新右子树 如果当前点 > val，则 split(L, v...

Haskell Study Note Lesson 5 List Creating Lists Note : type homogeneous [1,2,3] [1..5]、[2,4..10] Accessing List Elements index from 0 !!：list !! index A safe way : 1safeIndex xs i = if i < lenght xs then Just(xs !! i) else Nothing Concatenation & Extension Concatenation : ++ like [1, ...

初等数论入门 · 全课基础练习卷 一、整除与素数（对应第1、2课） 用带余除法计算：−17-17−17 除以 555 的商和余数。 求 gcd⁡(126,84)\gcd(126, 84)gcd(126,84) 和 lcm(126,84)\text{lcm}(126, 84)lcm(126,84)。 使用扩展欧几里得算法，求整数 x,yx, yx,y 使得 48x+18y=gcd⁡(48,18)48x + 18y = \gcd(48, 18)48x+18y=gcd(48,18)。 将 180180180 分解为标准素因数乘积形式。 列举出 303030 以内的所有素数。 二、积性函数与...

初等数论入门 Lesson 10 连分数与佩尔方程 连分数 对于任意一个实数 α\alphaα，我们不断进行如下操作： αn=an+1αn+1\alpha_n=a_n+\dfrac 1 {\alpha_{n+1}} αn​=an​+αn+1​1​ 最终得到的序列：[a0;a1;a2;a3,⋯ ][a_0;a_1;a_2;a_3,\cdots][a0​;a1​;a2​;a3​,⋯] 记为简单连分数 且有理数一定数有限连分数，无理数一定是无限连分数 渐近分数 Convergents 我们对于无限连分数，截断到第 kkk 项，记为第 kkk 个渐近分数。 它们遵循二阶线性递推关系： {pk=a...

初等数论入门 Lesson 9 一次与二次不定方程 一次不定方程 解决：ax+by=cax+by=cax+by=c 其实就是我们之前学过的拓欧，步骤可以简化如下： 贝祖定理判定存在性 扩欧求特解 通解含参 不等式锁参 本原勾股数组 我们要找出满足 x2+y2=z2x^2+y^2=z^2x2+y2=z2 的正整数三元组 (x,y,z)(x,y,z)(x,y,z) 本原的概念（Primitive Pythagorean Triple）：gcd⁡(x,y,z)=1\gcd(x,y,z)=1gcd(x,y,z)=1 我们因此能推出几个性质： 性质一：不能同时为偶数 性质二：不能同时为...

初等数论入门 Lesson 8 二次剩余与二次互反律 二次剩余 Quadratic Residue ppp 为奇素数，且 p∤ap\not\mid ap∣a 给定 x2≡a(modp)x^2\equiv a \pmod p x2≡a(modp) 若 xxx 存在，则称 aaa 是模 ppp 的二次剩余（QR），否则是二次非剩余（QNR） 勒让德符号 Lengendre 符号 定义： (ap)={1,p∤a 且 a 是模 p 的二次剩余−1,p∤a 且 a 是模 p 的二次非剩余0,p∣a\left(\frac{a}{p}\right)= \begin{cases} 1, & ...

初等数论入门 Lesson 7 阶与原根 阶 Order 定义： 对于 gcd⁡(a,m)=1\gcd(a,m)=1gcd(a,m)=1 ord⁡m(a)=min⁡{n∈Z∣an≡1(modm)}\operatorname{ord}_m(a)=\min\{n\in \mathbb Z\mid a^n\equiv 1\pmod m\} ordm​(a)=min{n∈Z∣an≡1(modm)} 即不断计算 a1,a2,…a^1,a^2,\dotsa1,a2,…，第一次出现余数为1，那个指数就是阶。 存在性证明： 由欧拉定理 aφ(m)≡1(modm)a^{\varphi(m)}\equiv...

初等数论入门 Lesson 6 同余方程与中国剩余定理 剩余系 完全剩余系：一组数 a1,a2,…,ama_1,a_2,\dots,a_ma1​,a2​,…,am​ 称为模 mmm 的一个完全剩余系，如果它们分别取自模 mmm 的 mmm 个不同的剩余类。 有以下两种典型的剩余系： 最小非负剩余系：{0,1,2,…,m−1}\{0, 1, 2, \dots, m - 1\}{0,1,2,…,m−1} 绝对最小剩余系：{−⌊m2⌋,…,−1,0,1,…,⌈m2⌉}\left\{ -\left\lfloor \frac{m}{2} \right\rfloor, \dots, -1, 0...