塔子哥学算法

分类

未归档(82) 题解(1)

/ 注册

全部文章（共83篇）

知识点:各种求逆元的技术

乘法逆元定义: 若a∗x≡1(mod p) ，且 a 与 b 互质，那么我们就能定义: x 为 a 的逆元，记为 x = a^(-1) 逆元存在条件: 当a与p互素时，a关于模p的乘法逆元有唯一解。如果不互素，则无解。如果p为素数，则从2到p-1的任意数都与f互素，即在2到p-1之间都恰好有一个...

2020-03-26

0 1007

知识点:欧拉图

定义1：通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路定义2：通过图中所有边一次且仅一次行遍所有顶点的回路称作欧拉回路定义3:含欧拉回路的图称为欧拉图，含欧拉通路而不含欧拉回路的图称为半欧拉图无向图中性质1:G是欧拉图当且仅当G是连通图且没有奇度顶点性质2:G是半欧拉图当且仅当G...

2020-03-25

0 855

第一章节笔记

第一节: 程序设计:给出解决特定问题的方法和过程，并以某种程序设计语言为工具，编写出改语言的工具. 程序设计语言：一组规则的集合。(例如说：词法规则,语法规则，语义规则，其他规则) 翻译:将高级程序变为统一的机器语言解释(basic 适合动态语言和交互式环境，重复执行的语句需要重复翻译，效率较低)...

2020-03-24

0 495

好题:3n 块披萨

解法一:区间dp O(n^3) 递推思路: 首先我们需要澄清两点与普通石子合并的差别。第一：他是环状的，需要破环处理。第二：选完以后披萨是会消掉的。但是，分析方法还是不变，考虑最后一步哪三块披萨进行消除。考虑线性情况下，它最后一步有两种情况。第一种就是左边部分和右边部分作为两个独立部...

2020-03-23

0 528

数据结构复习-第五章-树和二叉树

要点层次关系 1.树的定义: 2.树的基本术语:度(子树的个数，而不是离散数学中的度) 祖先层数(规定根节点的层数为1), 宽度一.存储结构 1.双亲表示法顺序表 (有点像并查集的存储方式) 2.孩子表示法链表 n个节点有n个孩子链表 n个头指针又构成一个线性表 3.孩子兄弟表示法(又称...

2020-03-21

0 699

数据结构复习-第七章-查找技术

要点 1.记录关键码主关键码次关键码 2.静动态查找查找结构 3.查找算法的性能: 平均查找长度 (注:很多时候查找成功的概率比查找不成功的概率大得多，几乎可以忽略二分查找判定树二叉排序树以及平衡树: https://www.jianshu.com/p/6b4c5f136e6e B树: ...

2020-03-20

0 443

知识点:格雷码

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。转换方法: 1.递归生成法:(构造法) 这种方法基于格...

2020-03-18

0 1705

点分治入门

问题引入: 静态统计一棵树上符合条件的路径数前置知识: ①分治思想 ②求树的重心重心的定义: 去掉树中任意一个点，可得到多颗子树，设这这些子树的大小为重心就是在树中去掉之后的那个点(又称质点) 重心的一个重要性质:重心的所有子树的性质的证明: ...

2020-03-17

0 512

知识点:康托展开和逆康托展开

康托展开问题解决：求一个n位的全排列按字典序升序排序的位置例如一个n位排列 2 3 4 1,我们用rank来代表他的排位从第一位开始：比2小的且没出现在之前的数有: 1 ,那么他对答案带来的贡献自然是 3! rank += 3! rank = 6; 第二位(注意，这时第一位已经确定是2了)...

2020-03-16

0 530

欧拉函数(一)定义以及性质,求法

定义: 性质: 解释：将φ(n)展开成计算式，a,b没有共同质因子，那么 φ(a)和φ(b)中没有共同的pi,所以得证. gcd(n,i) = 1时,gcd(n,n-i) = 1 反证法:设gcd(n,n-i) = k(k > 1),那么n%k=0且(n-i)%k = 0...

2020-03-15

0 570