【算法漫笔002】浅谈字符串HASH 字符串Hash 将字符串映射为一个固定范围的整数（也就是哈希值），该映射是单向的，即从字符串计算哈希值很容易，但从哈希值反推原字符串在计算上不可行。 构造哈希函数 哈希函数，即将字符串映射为哈希值的函数。理论上只要是能将字符串转化为哈希值的函数都可以被称为哈希函数。 首先给一个极其容易想到的哈希函数，我们将字符串中的每一个字符的 ASCII 码值相加得到哈希值，如下： 但是这样的哈希函数会有一个严重的问题：哈希冲突。 哈希冲突 首先我们要知道，字符串 Hash 的意义是什么、作用又是什么。普通的字符串操作多数为 O(N)O(N)O(N) 级别的（此处及后文中的 NNN 为字符串的长度），而整数的操作大多为 O(1)O(1)O(1)。 拿一个直观的例子，给你一个长串 SSS，反复询问 Sl1…r1S_{l1 \dots r1}Sl1…r1 和 Sl2…r2S_{l2 \dots r2}Sl2…r2 是否一样。如果是直接截取子串并逐字符比较的话，每一次计算的时间复杂度自然为子串长度。而如果使用哈希去预处理，其预处理后每次比较的时间复杂度为常数级。 但这不代表字符串Hash是万能的，如果两个不同字符串的哈希值相同，程序自然会认为两个字符串相等，在很多情况下就会出现错误，我们称这样的问题为哈希冲突。上文中提到的哈希函数的冲突率极高，仅就长度为 555 的小写字母字符串而言，可能的哈希值只有约 126126126 种，而字符串总数约为 265=118826^5=1188265=1188 万种，冲突率显然十分高。 进制哈希 一种常见的避免哈希冲突的方式是使用 Base Hash，即进制哈希（又称滚动哈希）。其核心思想是：将字符串看作一个 BBB 进制数，每一位字符的 ASCII 码作为该位上的数字，然后对这个 BBB 进制数取模，得到最终的哈希值。BBB 的值通常为 131,1331131,1331131,1331[1] 等。 相比于简单的 ASCII 码求和，进制哈希保留了字符的位置信息，哈希冲突概率大幅降低。 双模数优化 即使是用进制哈希，其哈希结果的数量也取决于 MODMODMOD 的大小，如果题目当中给出的 NNN 很大，就算使用进制哈希，冲突的概率也并不低。所以说，我们做两个进制哈希函数，其 BASEBASEBASE 值和 MODMODMOD 值都不同，程序在检查两个字符串是否相同时会同时调用这两个函数，如果两个哈希函数返回的值都相同，那么程序才认为两个字符串是相同的，冲突概率再次大大降低[2]。 前缀哈希 显然，这样的哈希函数时间复杂度为 O(N)O(N)O(N)，并不高效。然而在大多数题目中，我们需要频繁查询的是同一个字符串的不同子串。此时我们可以通过前缀哈希来预处理，实现 O(1)O(1)O(1) 获取任意子串的哈希值。下文就是一个典型的 进制哈希+前缀哈希+双模数优化 的模板。 哈希可解决的问题 哈希几乎可以解决任何字符串问题。例如： * 字符串匹配问题，计算模式串的哈希值，在原串中滑动窗口比较，O(N)O(N)O(N) 完成匹配（KMP 的另一种实现方式） * 最长回文子串问题，正反各算一遍哈希，配合二分，O(Nlog⁡N)O(N \log N)O(NlogN) 求解，虽然马拉车可以在 O(N)O(N)O(N) 时间复杂度下解决，之后可能会讲到。 * 最长公共前缀（LCP）：二分 + 哈希，O(log⁡N)O(\log N)O(logN) 查询两个后缀的 LCP，exKMP 也能够实现 * 字符串去重：将所有字符串映射为哈希值存入 unordered_set 中实现去重。 致谢&注释 感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 这些值均为质数，经验表明冲突率较低。 ↩︎ 2. 双哈希的碰撞概率约为 1MOD1×MOD2\frac 1 {MOD1 \times MOD2}MOD1×MOD21 ，实际使用中几乎可以忽略。 ↩︎

有人吗？ > 游戏 && 工作 基金会维基官网 后室维基官网 共创世界 成同学游戏导航 MCのmod MC1 MC2 > C++ 算法可视化 C++知识库 C++知识库2 > 数学 数学工具 > Vscode Vscode官网 MSYS2(VScode所需) Vscode下载指导网站 Vscode网站 > 壁纸 壁纸网站 堆糖头像壁纸 哲风壁纸 > 军事 全国征兵网 联合国 疑似俄罗斯征兵网 德国联邦国防军征兵测试网 国务院新闻办公室 > 未查明（危险） 未知 未知 美国核武器网站(未知) > Other 神秘论坛 工具大全 电子书 LCS模拟 线性代数 北大物科院

#include<bits/stdc++.h> using namespace std; int main(){ int n,num=0;cin>>n; for(int j=1;j<=n;j++){ for(int i=1;i<=n;i++) cout<<++num<<' '; cout<<endl;} return 0;}

c算法与函数 一、 算法基础概念 算法是解决特定问题的一系列有限、确定且可行的指令序列。在 C 中，算法通常体现为对数据的处理逻辑。 ‌算法的五大特征：‌ ‌有穷性‌：算法必须在执行有限步骤后停止，不能陷入死循环。 ‌确定性‌：每一步骤必须有精确的定义，无歧义。 ‌可行性‌：每一步都必须在有限时间内完成。 ‌输入‌：算法可以有零个或多个输入量值。 ‌输出‌：算法必须至少有一个输出结果。 ‌算法与程序的区别：‌ 算法是解决问题的逻辑方法，而程序是算法在特定编程语言（如 C++）中的具体实现。 二、 常用排序算法 排序是将一组数据按照特定顺序（如升序或降序）排列的过程。以下是几种经典的 C++ 排序实现思路： 冒泡排序 (Bubble Sort) ‌原理‌：通过重复交换相邻的元素来排序。如果前一个数大于后一个数，则交换它们。 ‌特点‌：简单直观，但效率较低，时间复杂度为 O(n2) O(n2)。 ‌核心逻辑‌： cpp // void bubbleSort(int arr[], int length) { for (int i = 0; i < length - 1; i++) { for (int j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j + 1]) { stdswap(arr[j], arr[j + 1]); } } } } // 选择排序 (Selection Sort) ‌原理‌每次从未排序的序列中选择最小（或最大）的元素，放到已排序序列的末尾。 ‌特点‌：交换次数少，但比较次数多，时间复杂度为 O(n2) O(n2)。 ‌核心逻辑‌： cpp // void selectionSort(int arr[], int length) { for (int i = 0; i < length - 1; i++) { int minIndex = i; for (int j = i + 1; j < length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } stdswap(arr[i], arr[minIndex]); } } // 快速排序 (Quick Sort) ‌原理‌：基于‌分治算法思想‌。选择一个基准值（Pivot），将数组分为两部分：左侧小于等于基准值，右侧大于基准值，然后递归地对这两部分进行排序。 ‌特点‌：平均效率高，时间复杂度为 O(n log n) O(n log n)，是实际应用中常用的排序算法。 ‌核心逻辑‌： 选取基准值（通常选中间位置 (left + right) / 2）。 使用两个指针 i 和 j，分别从左向右找比基准大的数，从右向左找比基准小的数，找到后交换。 当 i > j 时停止，递归处理左右子区间。 其他常见排序 C++ 标准库及算法大全中还包含插入排序、归并排序、堆排序、希尔排序、计数排序、桶排序和基数排序等，可根据数据规模和特性选择使用。 三、 搜索算法 搜索算法用于在数据集中查找特定目标值。 ‌线性搜索 (Linear Search)‌：逐个检查元素，适用于未排序数据，时间复杂度 O(n) O(n)。 ‌二分搜索 (Binary Search)‌：适用于‌已排序‌数组。通过不断将搜索区间减半来查找目标，时间复杂度 O(log n) O(log n)。 ‌其他搜索‌：插值搜索、斐波那契搜索等，针对特定分布的数据优化搜索效率。 四、 高精度算法 (High Precision Arithmetic) 由于 C++ 内置类型（如 int, long long, double）的范围和精度有限，处理超大整数或高精度浮点数时需要模拟人工运算。 高精度加法 ‌思路‌：使用字符串或字符数组输入大数，将其逆序存储到整型数组中（个位在下标 0）。从低位到高位依次相加，处理进位。 ‌关键点‌： 对齐个位：通常通过逆序存储自然对齐。 进位处理：sum = a[i] + b[i] + carry，当前位结果为 sum % 10，进位为 sum / 10。 注意最高位可能产生的额外进位。 高精度乘法与除法 ‌乘法‌：模拟竖式乘法，注意位权对应关系。 ‌除法‌： ‌高精度除以单精度‌：从高位到低位逐位计算商和余数。 ‌单精度除以单精度求高精度商‌：先算整数部分，余数乘以 10 继续除，可保留任意位小数。 压位优化 ‌思想‌：为了减少计算次数，可以将多位数字压缩到一个数组元素中（例如每 4 位存为一个 int，基数 base=10000）。 ‌优势‌：大幅减少数组长度和循环次数，提高运算效率。 ‌输出注意‌：最高位正常输出，后续低位需补零至固定宽度（如 %04d）。 五、 C++ 标准库与工程实践 在实际开发或竞赛中，合理利用 C++ 标准库可以简化算法实现。 ‌头文件‌：推荐使用 <bits/stdc++.h> 包含所有标准库，或根据需要包含 <iostream>, <vector>, <algorithm> 等。 ‌命名空间‌：使用 using namespace std; 避免每次调用标准库函数前加 std::。 ‌容器与算法‌： stdvector：动态数组，支持随机访问。 stdsort：标准库提供的排序函数，底层通常为内省排序（IntroSort），效率高于手写的简单排序。 std::swap：高效交换两个变量的值。 ‌数据类型选择‌： 普通整数用 int。 较大整数用 long long。 高精度计算需自定义结构体或使用字符串模拟。 六、 总结 掌握 C++ 算法需要从理解基本数据结构开始，熟练运用排序和搜索等基础算法，并在面对超出原生数据类型范围的问题时，能够灵活运用高精度算法进行模拟。同时，熟悉 C++ 标准库（STL）能极大提升代码编写效率和程序性能。 函数的基本结构 一个完整的函数定义通常包含以下四个部分： ‌返回值类型‌：函数执行后返回的数据类型。如果不返回任何值，使用 void。 ‌函数名‌：遵循标识符命名规则，应清晰描述函数功能。 ‌参数列表‌：括号内定义的输入变量（形参），包括类型和名称。可以为空。 ‌函数体‌：花括号 {} 内的代码块，包含具体的逻辑语句。 ‌语法示例：‌ cpp 返回值类型 函数名(参数列表) { // 函数体 return 表达式; // 如果返回值类型不是 void } // 示例：计算两个整数之和 int add(int a, int b) { return a + b; } 2. 函数的声明与定义 ‌函数声明（原型）‌：告诉编译器函数的存在、返回类型和参数类型。通常放在头文件（.h）中。 格式：int add(int a, int b); 作用：允许在定义之前调用函数，支持多文件编程。 ‌函数定义‌：提供函数的实际实现代码。通常放在源文件（.cpp）中。 规则：声明可以多次，但定义在整个程序中只能有一次（遵循单一定义规则 ODR）。 3. 参数传递方式 C++ 主要有三种参数传递方式，区别在于是否影响原始数据以及性能开销： 表格 传递方式 说明 特点 示例语法 ‌值传递‌ 复制实参的值给形参 安全，修改形参不影响实参；大对象拷贝开销大默认方式 void func(int x) ‌引用传递‌ 形参是实参的别名 高效（无拷贝），可直接修改实参；C++ 推荐方式 void func(int& x) ‌指针传递‌ 传递实参的地址 可修改实参，语法稍繁琐（需解引用 ） void func(int x) ‌注意‌：若希望提高效率且防止修改实参，常使用 ‌常量引用‌ (const Type&)。 常见高级特性 函数重载 (Function Overloading) 允许在同一作用域中声明多个同名函数，只要它们的‌参数列表不同‌（参数个数、类型或顺序不同）。 ‌注意‌：仅返回值类型不同‌不能‌构成重载。 cpp int add(int a, int b); double add(double a, double b); // 合法重载 默认参数 (Default Arguments) 可以在函数声明中为参数指定默认值。调用时若省略该参数，则使用默认值。 ‌规则‌：默认参数必须从右向左依次定义，不能跳过中间参数。 cpp void printInfo(string name, int age = 18); printInfo("Alice"); // age 默认为 18 内联函数 (Inline Functions) 使用 inline 关键字建议编译器在调用处直接替换函数体，以减少函数调用的开销。 ‌适用场景‌：代码短小（如1-5行）、频繁调用的函数。 ‌缺点‌：代码过长会导致代码膨胀。 5. 特殊函数类型 ‌main 函数‌：每个 C++ 程序的入口点。 ‌递归函数‌函数内部调用自身。需注意设置终止条件，避免栈溢出。 ‌Lambda 表达式‌：匿名函数，常用于算法标准库（如 std::sort）中作为简短回调。 cpp auto sum = [](int a, int b) { return a + b; };

1 迭代器的概念 迭代器（ITERATOR） 是一种可以遍历容器元素的数据类型。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。C++ 更趋向于使用迭代器而不是数组下标操作，因为标准库为每一种标准容器（如VECTOR、MAP和LIST等）定义了一种迭代器类型，而只有少数容器（如VECTOR）支持数组下标操作访问容器元素。可以通过迭代器指向你想访问容器的元素地址，通过*X打印出元素值。这和我们所熟知的指针极其类似。 C语言有指针，指针用起来十分灵活高效。 C++语言有迭代器，迭代器相对于指针而言功能更为丰富。 VECTOR，是数组实现的，也就是说，只要知道数组的首地址，就能访问到后面的元素。所以，我们可以通过访问VECTOR的迭代器来遍历VECTOR容器元素。 LIST，是链表实现的，我们知道，链表的元素都存储在一段不是连续的地址空间中。我们需要通过NEXT指针来访问下一个元素。那么，我们也可以通过访问LIST的迭代器来实现遍历LIST容器元素。 由此可见，迭代器和容器是密不可分的、紧密相连的的关系。不同的容器，它们的迭代器也是不同的，但是它们的迭代器功能是一样的。假如没有迭代器，由于VECTOR和LIST容器的存储特点，你需要两种算法去实现遍历VECTOR和LIST容器的功能，复杂且低效。有了迭代器，遍历容器的效率会大大提高。 2 迭代器的使用 2.1 迭代器的常用操作 * *ITER ：对ITER进行解引用，返回迭代器ITER指向的元素的引用 * ITER->MEN ：对ITER进行解引用，获取指定元素中名为MEN的成员。等效于(*ITER).MEN * ++ ITER / ITER ++ ：给ITER加1，使其指向容器的下一个元素 * -- ITER / ITER -- ：给ITER减1，使其指向容器的前一个元素 * ITER1==ITER2 ：比较两个迭代器是否相等，当它们指向同一个容器的同一个元素或者都指向同同一个容器的超出末端的下一个位置时，它们相等 * ITER1!=ITER2 2.2 迭代器遍历容器 容器都有成员BEGIN和END，其中BEGIN成员复制返回指向第一个元素的迭代器（用*迭代器打印出元素值），而END成员返回指向容器尾元素的下一个位置的迭代器，它是一个不存在的元素位置。 例1：遍历容器VECTOR 例2：VECTOR容器的迭代器定义 3 迭代器函数 3.1 ADVANCE函数 简介 ADVANCE()函数在头文件：<ITERATOR>。 其可以将指定迭代器前移或后移 N 个位置的距离。ADVANCE() 函数没有任何返回值，其移动的是 IT 迭代器本身。 使用 程序执行结果为： 移动前的 *IT = 1 移动后的 *IT = 3 3.2 PREV函数 简介 PREV函数在头文件：<ITERATOR>。 PREV 原意为“上一个”，但 PREV() 的功能远比它的本意大得多，该函数可用来获取一个距离指定迭代器 N 个元素的迭代器，即生成一个新的迭代器。 PREV函数格式为：PREV（IT, N）。其中，IT 为源迭代器，其类型只能为双向迭代器或者随机访问迭代器；N 为指定新迭代器距离 IT 的距离，默认值为 1。该函数会返回一个距离 IT 迭代器 N 个元素的新迭代器。当 N 为正数时，其返回的迭代器将位于 IT 左侧；反之，当 N 为负数时，其返回的迭代器位于 IT 右侧。 使用 程序执行结果为： PREV(IT, 2) = 4 PREV(IT, -2) = 3 注意 使用PREV函数要保证STL容器不为空。 3.3 NEXT函数 简介 NEXT函数位于头文件：<ITERATOR> 和 PREV相反，NEXT 原意为“下一个”，但其功能和 PREV() 函数类似，即用来获取一个距离指定迭代器 N 个元素的迭代器。 函数格式：NEXT(IT, N)。其中 IT 为源迭代器，其类似可以为前向迭代器、双向迭代器以及随机访问迭代器；N 为指定新迭代器距离 IT 的距离，默认值为 1。该函数会返回一个距离 IT 迭代器 N 个元素的新迭代器。当 IT 为前向迭代器时，N 只能为正数，该函数最终得到的新迭代器位于 IT 右侧；当 IT 为双向迭代器或者随机访问迭代器时，若 N 为正数，则得到的新迭代器位于 IT 右侧，反之位于 IT 左侧。 使用 程序执行结果为： NEXT(IT, 2) = 3 NEXT(IT, -2) = 4 可以看到，和 PREV() 函数恰好相反，当 N 值为 2 时，NEXT(IT, 2) 函数获得的新迭代器位于 IT 迭代器的右侧，距离 2 个元素；反之，当 N 值为 -2 时，新迭代器位于 IT 迭代器的左侧，距离 2 个元素。

#include<bits/stdc++.h> using namespace std; int main() { int a; cin>>a; if(a>=10) cout<<"yes"; else cout<<"no"; return 0; }

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; if(n==1){ cout<<"YES"; }else{ cout<<"no"; } }

数字机遇，森林冒险-注释 ================================================================================================================================================== 👉 广搜路径检查 （“迷宫路径检查”） 1️⃣ 准备探险装备（全局变量与工具） 【伪代码：理清思路】 记录迷宫的大小（行数 n，列数 m）。 准备一个“方向指南针”（包含上、下、左、右 4 个方向的坐标变化）。 准备一张“迷宫地图”，用来记录哪里是路（.），哪里是墙（#）。 准备一张“防迷路脚印图”，用来标记哪些格子已经去过。 准备一个“坐标小包裹”，把横纵坐标绑在一起。 准备一个“待办事项清单”（队列），用来存放准备去探索的格子。 【C++ 具体代码】 2️⃣ 编写辅助小工具（边界检查） 【伪代码：理清思路】 【工具：边界检查】 检查一个坐标 (x, y) 是否安全： 如果 横坐标在 1 到 n 之间，并且 纵坐标在 1 到 m 之间： 返回“安全（在地图内）” 否则： 返回“危险（出界了）” 【C++ 具体代码】 3️⃣ 核心探险魔法 (BFS) 【伪代码：理清思路】 函数 迷宫探险(起点坐标): 把【起点】放进“待办事项清单”，并立刻在“脚印图”上给起点盖章（标记为已访问）。 只要“待办事项清单”不是空的，就一直循环： a. 从清单里拿出排在最前面的那个【当前坐标】，并把它从清单上划掉。 b. 【胜利判断】：如果【当前坐标】就是右下角终点 (n, m)： 直接大喊“YES！找到路了！”，结束探险！ c. 【继续扩散】：拿出“方向指南针”，依次尝试向 上、下、左、右 4个方向走一步： 计算【新坐标】 = 【当前坐标】 + 指南针方向 【三重安检】：如果【新坐标】同时满足以下 3 个条件： * 通过了“边界检查”（没有走出地图） * 在“脚印图”上没盖过章（没去过） * 在“迷宫地图”上不是墙壁（不是 #） 那么： * 立刻在“脚印图”上给【新坐标】盖章！（️ 核心防坑：入队即标记） * 把【新坐标】放进“待办事项清单”的末尾。 如果“待办事项清单”空了，还是没走到终点： 说明迷宫被墙堵死了，大喊“NO！走不到！”。 【C++ 具体代码】 4️⃣ 主程序启动 【伪代码：理清思路】 读入迷宫的行数和列数。 像画画一样，一行一行地把迷宫读进“迷宫地图”里。 呼叫“迷宫探险”魔法，让它从左上角 (1, 1) 开始探险。 根据魔法返回的结果，打印出 "YES" 或 "NO"。 【C++ 具体代码】 完整代码 ================================================================================================================================================== 广搜最短路径 1️⃣在开始寻宝之前，我们需要知道地图有多大，还要准备好记录工具。 【伪代码】 1. 记录地图的行数和列数。 2. 准备一个“方向背包”，里面装着4个方向：上、下、左、右。 3. 准备一张“地图”，用来记录哪里是路（.），哪里是墙（#）。 4. 准备一张“脚印图”，用来标记哪些地方已经去过，防止走回头路。 5. 准备一个“小背包（结构体）”，用来装当前位置的坐标 (x, y) 和已经走的步数。 【对应代码】 2️⃣🛡️第二部分：边界判断（安全区检查） 在地图上移动时，不能跑出地图外面，也不能撞墙。 【伪代码】 检查一个新位置 (nx, ny) 是否安全： 如果 横坐标在 1 到 地图行数 之间， 并且 纵坐标在 1 到 地图列数 之间， 那么 返回“安全”； 否则 返回“危险”。 【对应代码】 3️⃣🔍 第三部分：核心魔法 BFS（水波扩散寻宝） 这是整段代码最核心的部分！就像水波一样，先探索离起点 1 步的地方，再探索 2 步的地方，一层一层往外推。 【伪代码】 1. 把起点放进“排队队列”里，步数设为 0，并在“脚印图”上打个勾。 2. 只要“排队队列”里还有人，就一直循环： 3. 让排在最前面的那个人出来，看看他的坐标和步数。 4. 【到达终点？】如果他的位置就是终点，直接大声喊出他的步数，游戏结束！ 5. 【继续扩散】让他尝试往 上、下、左、右 四个方向走： 6. 计算新位置的坐标。 7. 检查新位置：在地图内吗？没去过吗？是路吗？ 8. 如果都满足：在新位置打上“已去过”的勾，把他和（当前步数+1）放进“排队队列”。 3. 如果队列空了还没找到终点，说明走不到，返回 -1。 【对应代码】 4️⃣🎮 第四部分：主程序（游戏开始） 把地图读进来，然后喊出寻宝的起点！ 、 【伪代码】 1. 读入地图的行数 n 和列数 m。 2. 用循环把地图的每一行读进来。 3. 从左上角 (1, 1) 开始寻宝，打印出结果。 💡 3 个小贴士： 1、为什么要用 vis 脚印图？ 如果不标记去过的地方，你就像无头苍蝇一样在两个格子之间来回走，程序会永远卡住（死循环）。 2、为什么 BFS 找到的第一个解就是最短路径？ 因为它是“一层一层”往外找的，就像水波一样，第一次碰到终点时，经历的圈数（步数）一定是最少的！ 3、dir 数组是个好东西： 以后不管是在网格上走，还是走 8 个方向（比如国际象棋里的马），只要改 dir 数组里的数字就行了，不用写 4 遍 if，非常聪明！ 完整代码

通过查询本喵的获奖记录可以看到，我只有 5 级钩，所以可能不会讲得很深，但应该不会出错。 一、矩阵定义 把若干个数字排成一个矩形表，就是 矩阵。 例如： [abcd]\begin{bmatrix} a & b \\ c & d \end{bmatrix} [ac bd ] 通常记作： A=(aij)m×nA=(a_{ij})_{m\times n} A=(aij )m×n 其中： * mmm 表示行数； * nnn 表示列数； * aija_{ij}aij 表示第 iii 行第 jjj 列的元素。 二、常用概念 * 同型矩阵：行数 和 列数 都相等的 两个 矩阵。 * 方阵：行数 和 列数 都相等的 一个 矩阵。 * 零矩阵：所有元素都是 000 的矩阵，记作 OOO。 * 单位矩阵：主对角线全为 111、其余元素为 000 的方阵，记作 III。 > 主对角线是指从左上角到右下角的对角线。 三、矩阵的加减法 > 只有同型矩阵才可以进行加减运算，即两个矩阵的行数和列数分别相等。 运算规则：对应位置上的元素相加减。 例如： [1324]+[5678]=[1+53+62+74+8]=[69912]\begin{bmatrix} 1 & 3 \\ 2 & 4 \end{bmatrix} + \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} = \begin{bmatrix} 1+5 & 3+6 \\ 2+7 & 4+8 \end{bmatrix} = \begin{bmatrix} 6 & 9 \\ 9 & 12 \end{bmatrix} [12 34 ]+[57 68 ]=[1+52+7 3+64+8 ]=[69 912 ] 四、矩阵乘法 > 我觉得这部分最难了，也可能是本喵太菜了。 1. 乘法条件 若矩阵 AAA 是 m×nm\times nm×n 的矩阵，矩阵 BBB 是 n×pn\times pn×p 的矩阵，则它们可以相乘： C=ABC=AB C=AB 结果 CCC 是一个 m×pm\times pm×p 的矩阵。 也就是说： > AAA 的列数等于 BBB 的行数才可相乘（当然，把这句话反过来说，也就是“BBB 的行数等于 AAA 的列数”，意思是一样的喵）。 2. 乘法规则 接上条，设： C=ABC=AB C=AB 则 CCC 的第 iii 行第 jjj 列的元素为： cij=∑k=1naikbkjc_{ij}=\sum_{k=1}^{n} a_{ik}b_{kj} cij =k=1∑n aik bkj 用喵话说，就是： > AAA 的第 iii 行与 BBB 的第 jjj 列的对应元素相乘后再相加。 例如： A=[1234],B=[5678]A= \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \quad B= \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} A=[13 24 ],B=[57 68 ] 计算 C=ABC=ABC=AB： c11=1⋅5+2⋅7=19c_{11}=1\cdot 5+2\cdot 7=19 c11 =1⋅5+2⋅7=19 c12=1⋅6+2⋅8=22c_{12}=1\cdot 6+2\cdot 8=22 c12 =1⋅6+2⋅8=22 c21=3⋅5+4⋅7=43c_{21}=3\cdot 5+4\cdot 7=43 c21 =3⋅5+4⋅7=43 c22=3⋅6+4⋅8=50c_{22}=3\cdot 6+4\cdot 8=50 c22 =3⋅6+4⋅8=50 所以： C=[19224350]C= \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix} C=[1943 2250 ] 3. 特殊性质 * 矩阵乘法不满足交换律，即 AB≠BAAB\neq BAAB=BA。 * 矩阵乘法满足结合律，即 (AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)。 * 矩阵乘法满足分配律，即 A(B+C)=AB+ACA(B+C)=AB+ACA(B+C)=AB+AC。 五、方阵的幂 显然只有方阵才能自己乘自己。 定义： Ak=AA⋯A⏟k 个A^k = \underbrace{A A \cdots A}_{k \text{ 个}} Ak=k 个AA⋯A 特别地，约定： A0=IA^{0}=I A0=I 六、矩阵快速幂 矩阵快速幂和普通整数快速幂的思想完全一样：将指数按二进制拆分，利用幂的运算性质加速。 我们要计算 AbA^bAb，其中 AAA 是方阵。 如果直接乘 bbb 次，复杂度是 O(b⋅n3)O(b\cdot n^3)O(b⋅n3)，当 bbb 很大时不可接受。 快速幂做法： 把指数 bbb 写成二进制。例如： b=13=11012b=13=1101_2 b=13=11012 那么： A13=A8⋅A4⋅A1A^{13}=A^8 \cdot A^4 \cdot A^1 A13=A8⋅A4⋅A1 我们只需要维护一个底数 base=A2kbase=A^{2^k}base=A2k，每次让 basebasebase 自己乘自己，就能得到 A1,A2,A4,A8,⋯A^1,A^2,A^4,A^8,\cdotsA1,A2,A4,A8,⋯。 如果当前二进制位是 111，就把结果乘上这个 basebasebase。 算法流程 设结果矩阵 res=Ires=Ires=I，底数矩阵 base=Abase=Abase=A。 当 b>0b>0b>0 时： 1. 如果 bbb 的最低位是 111，则 res=res×baseres=res\times baseres=res×base； 2. 令 base=base×basebase=base\times basebase=base×base； 3. 令 b=b>>1b=b>>1b=b>>1。 最后 res=Abres=A^bres=Ab。 复杂度：一次矩阵乘法是 O(n3)O(n^3)O(n3)，快速幂需要乘 O(log⁡b)O(\log b)O(logb) 次，总复杂度 O(n3log⁡b)O(n^3\log b)O(n3logb)。 七、矩阵快速幂优化递推 > 终于到了喵。 例子：斐波那契数列 斐波那契数列的定义： F0=0,F1=1F_0=0,\quad F_1=1 F0 =0,F1 =1 Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} Fn =Fn−1 +Fn−2 直接递推求解显然为 O(n)O(n)O(n)，但可以使用今天的内容优化到 O(log⁡n)O(\log n)O(logn)。 构造转移矩阵 我们把当前需要的两项打包成一个列向量： vn=[FnFn−1]v_n= \begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix} vn =[Fn Fn−1 ] 那么下一项： vn+1=[Fn+1Fn]v_{n+1}= \begin{bmatrix} F_{n+1}\\ F_n \end{bmatrix} vn+1 =[Fn+1 Fn ] 观察： Fn+1=1⋅Fn+1⋅Fn−1F_{n+1}=1\cdot F_n+1\cdot F_{n-1} Fn+1 =1⋅Fn +1⋅Fn−1 Fn=1⋅Fn+0⋅Fn−1F_n=1\cdot F_n+0\cdot F_{n-1} Fn =1⋅Fn +0⋅Fn−1 所以转移矩阵为： M=[1110]M= \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} M=[11 10 ] 于是： vn+1=Mvnv_{n+1}=Mv_n vn+1 =Mvn 连续递推可得： vk=Mkv0v_k=M^k v_0 vk =Mkv0 其中初始向量： v0=[F1F0]=[10]v_0= \begin{bmatrix} F_1\\ F_0 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \end{bmatrix} v0 =[F1 F0 ]=[10 ] 因此求 FkF_kFk ，只需计算 MkM^kMk，然后乘上 v0v_0v0 ，结果向量的第二行就是 FkF_kFk 。 另外，通过归纳法可以证明： Mk=[Fk+1FkFkFk−1]M^k= \begin{bmatrix} F_{k+1} & F_k\\ F_k & F_{k-1} \end{bmatrix} Mk=[Fk+1 Fk Fk Fk−1 ] 所以也可以直接取 MkM^kMk 的第一行第二列。 一般二阶线性递推 如果递推形式是： an=p⋅an−1+q⋅an−2a_n=p\cdot a_{n-1}+q\cdot a_{n-2} an =p⋅an−1 +q⋅an−2 同样把当前两项打包： vn=[anan−1]v_n= \begin{bmatrix} a_n\\ a_{n-1} \end{bmatrix} vn =[an an−1 ] 那么： an+1=p⋅an+q⋅an−1a_{n+1}=p\cdot a_n+q\cdot a_{n-1} an+1 =p⋅an +q⋅an−1 an=1⋅an+0⋅an−1a_n=1\cdot a_n+0\cdot a_{n-1} an =1⋅an +0⋅an−1 所以转移矩阵为： M=[pq10]M= \begin{bmatrix} p & q\\ 1 & 0 \end{bmatrix} M=[p1 q0 ] 更高阶递推 若递推式涉及前 *** 项，则需要维护 *** 维列向量，转移矩阵为 d×dd\times dd×d，第一行放递推系数，下面各行负责把旧分量向下搬运。 例如递推式： an=p⋅an−1+q⋅an−2+r⋅an−3a_n=p\cdot a_{n-1}+q\cdot a_{n-2}+r\cdot a_{n-3} an =p⋅an−1 +q⋅an−2 +r⋅an−3 转移矩阵为： [pqr100010]\begin{bmatrix} p & q & r\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} p10 q01 r00 规律非常明显喵。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 至此，矩阵快速幂优化递推的核心思想就讲完了。总结一下： 1. 确定状态向量； 2. 写出递推关系； 3. 构造转移矩阵； 4. 快速幂求解。

考试题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ STA-STATION 两次DFS 求树的直径 边权>=0 树上游戏 (HARD) 树上游戏 树上慈善基金 树的直径 树上差分 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 自上而下 子树批量修改【模版题】 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DFS序 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ LCA最近公共祖先 朴素版 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ LCA最近公共祖先 倍增优化 树的属性

巅峰赛 #37 题解 | 非官方 本次题目猜测的总体难度如下，仅供参考： 题目编号 题目标题 难度 T1 午枫的幸运名单 普及−\color{orange}{普及-}普及− T2 宝藏密码 普及/提高−\color{yellow}{普及/提高-}普及/提高− T3 午枫的宝藏 普及/提高−\color{yellow}{普及/提高-}普及/提高− T4 午枫的罗盘 普及/提高−\color{yellow}{普及/提高-}普及/提高− T5 午枫的航海日志 普及/提高−\color{yellow}{普及/提高-}普及/提高− T6 午枫的密码本 普及+/提高\color{green}{普及+/提高}普及+/提高 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1. 午枫的幸运名单 题目大意 给一个正整数 nnn 和 nnn 个 字符串 SiS_iSi ，并且给出一个 PPP，判断 PPP 是否在字符串中出现过，并且输出出现的位置的 iii，如果没有出现则输出 -1。 解题思路 对于每一个输入的时候，直接判断输入的字符串是否等于 PPP 即可，但是如果用 solve\mathrm{solve}solve 的话，需要把答案记录下来，不能直接输出。 参考代码 单组测试样例时间复杂度：O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2. 宝藏密码 题目大意 给你 nnn 条公式，每一条公式有一个共同解 xxx，而方程为 aix+bi=cia_ix + b_i = c_iai x+bi =ci ，其中 ai,bi,cia_i, b_i, c_iai ,bi ,ci 的位置可以调换。 解题思路 得出 xxx 所表示： aix+bi=cia_ix + b_i = c_i ai x+bi =ci aix=ci−bia_ix = c_i-b_i ai x=ci −bi x=ci−biaix = \dfrac{c_i-b_i}{a_i} x=ai ci −bi 可以把所有 ui,vi,wiu_i, v_i, w_iui ,vi ,wi 可能的 ai,bi,cia_i, b_i, c_iai ,bi ,ci 枚举出来。如果 ci−bimod  ai=0c_i-b_i\mod a_i=0ci −bi modai =0，则可以将这个答案压入一个 vector\mathrm{vector}vector，然后去重。由于答案为一，所以判断是否满足 aix+bi=cia_ix+b_i=c_iai x+bi =ci 即可。 参考代码 单组测试样例时间复杂度：O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3. 午枫的宝藏 题目大意 有 nnn 个人。船长可以提出一个分配方案，如果投票超过半数则成功，否则船长被杀死。所有水手聪明、贪婪、互不信任，每个人在保证自己不被杀的前提下争取最大利益。求每个人能获取的金（不包括船长），且能保证自己活下来。压缩答案为： R=(∑i=1ni×ri)mod  (109+7)R = (\sum_{i=1}^n i \times r_i) \mod (10^9+7) R=(i=1∑n i×ri )mod(109+7) 解题思路 假设现在有 111 个人（不包括船长），那么他肯定投自己一票，票数过半，所以可以给自己利益最大化。 假设现在有 222 个人（不包括船长），那船长只需要令其中一个人同意，所以会给 222 号水手 111 个金，可以令 222 号水手举手。由于如果 222 号水手不同意，111 号水手就会决定分配，而 222 号水手则一点金都拿不到，所以 222 号水手一定会同意。得出 rrr 数组： 0,1,0,1,0,1,⋯0, 1, 0, 1, 0, 1, \cdots 0,1,0,1,0,1,⋯ 接下来压缩答案，只有双数位的 rir_iri 才会对答案有贡献，所以如果 nnn 为偶数，则答案为 2+4+⋯+n2+4+\cdots+n2+4+⋯+n；否则答案为 2+4+⋯+(n−1)2+4+\cdots+(n-1)2+4+⋯+(n−1)，而公式则为 n×(n+2)4\dfrac{n\times (n + 2)}{4}4n×(n+2) 。 参考代码 单组测试样例时间复杂度：O(1)O(1)O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4. 午枫的罗盘 题目大意 有 nnn 条线，相邻两条线之间的夹角为 180∘k\dfrac{180^\circ}{k}k180∘ ，求有多少对垂直的线。 解题思路 首先观察题目，如果 kkk 是奇数是不可能有任何垂直的线。且如果 n<k2n < \dfrac{k}{2}n<2k ，则不可能有垂直的线。 和 000 垂直的第一条线为 k2\dfrac{k}{2}2k 。设 aaa 为 000 垂直的最后一条线，bbb 为与 000 垂直的线的组数。则对与所有都有 (a−k2+1)×b(a - \dfrac{k}{2}+1)\times b(a−2k +1)×b。而还有多余的线（n−an-an−a）， (a+1,a+1+k)(a + 1, a + 1 + k)(a+1,a+1+k) 的区间有 (b−1)(b-1)(b−1) 条线；(a+1+k,a+1+2k)(a + 1+k,a+1+2k)(a+1+k,a+1+2k) 的区间有 (b−2)(b-2)(b−2) 条线。则是每一组就有 (b−1)×k,(b−2)×k(b-1)\times k, (b-2)\times k(b−1)×k,(b−2)×k，提取 kkk 出来则是 k×(b−1)+(b−2)+(b−3)+(b−4)+⋯+1k\times(b-1)+(b-2)+(b-3)+(b-4)+\cdots+1k×(b−1)+(b−2)+(b−3)+(b−4)+⋯+1，项数为 n−(a+1)k\dfrac{n-(a+1)}{k}kn−(a+1) 。最后运用（首项+末项）×项数2\dfrac{（首项 + 末项）\times 项数}{2}2（首项+末项）×项数 ，求出答案即可。 参考代码 单组测试样例时间复杂度：O(1)O(1)O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5. 午枫的航海日志 题目大意 有 nnn 个数，有多少组数对 (p,q)(p,q)(p,q)，使得序列存在 p,0,p,qp,0,p,qp,0,p,q。 解题思路 考虑这个问题可以先问一些问题： * 对于每一个 ppp，应该选哪一个 000？当然是离 ppp 最近的那个 000，可以最大化后面 qqq 的个数。 * 对于每一个 000，应该选哪一个 ppp？当然是离 000 最近的那个 ppp，可以最大化后面 qqq 的个数。 我们可以用一个 suff\mathrm{suff}suff 数组，表示从当前位置到序列末尾有多少个不同数字个数，而且要记录下来每一个数字出现的位置。我们可以用 lower_bound 来查找后面的下标，再处理一下特殊情况就可以了。 参考代码 单组测试样例时间复杂度：O(N×nlog⁡n)O(N \times n \log n)O(N×nlogn)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6. 午枫的密码本 题目大意 给定一个字符串 SSS，将其拼接 kkk 次得出 S′S'S′，求 S′S'S′ 的 ASCII\mathrm{ASCII}ASCII 值的最长上升子序列的长度。 解题思路 首先看到 kkk 的最大值为 1010010^{100}10100，所以显然不能直接暴力拼接，考虑优化。假设字符串 SSS 为 zyxwvutsrqponmlkjihgfedcba，kkk 为 1010010^{100}10100，结果的值为 262626。由此得知，答案最大为 262626，因为是严格上升子序列，而英文字母只有 262626 个。所以 SSS 拼接 262626 次就可以了。 怎么判断 kkk 是否大于 262626 呢？kkk 是字符串，无法直接判断。我们可以先看 kkk 的长度。如果大于 222 则一定是拼接 262626 次。如果小于，直接换成 int 判断就行了。 最后，使用 dp\mathrm{dp}dp 求最长上升子序列即可。 参考代码 时间复杂度：O(m2)O(m^2)O(m2)，其中 mmm 为拼接后字符串的长度。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

啊喵喵喵树比图要多一些机制, 所!以! 我要新发一篇帖子~ TARJAN算法 这里要讲一下,这并不是主流求LCA的算法,是不太好理解但空间时间都非常good还很短(不是重点)的算法 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 倍增法解决LCA 这个是我们常用的方法,没Tarjan好用(个人认为),放后面展示 树上常见操作探索 最!后! 我要喵两句,递归栈的内存分配和时间复杂度差不多,没超时大胆递归,别信AI说的会栈上溢的鬼话 (某苦喵曾手搓结构体栈模拟递归WA了不知道多少次)

不不不不不我无疑是愤怒的，发不了题解

初赛复习 求赞求赞，B站：只玩鸟的Rhett 1.计算机基础与存储空间 ①计算机的组成 > 处理->存储->输入输出 CPU：[处理]负责读取指令，分析指令，执行运算和控制 内存(RAM)：[存储]程序运行时临时存放的数据，速度快，断电后通常消失 外存(SSD)：[存储]硬盘、U盘等长期保存数据，容量大，速度通常慢于内存，断电后数据不消失 输入输出设备：[输入输出]鼠标键盘是输入，显示器打印机是输出，触摸屏常兼具输入输出 > 提醒:CSP-J组常考"内存"和"硬盘"混在一起，这是高频错误，内存管运行，硬盘管理长期保存 ②CPU的组成：取指，译码，执行，控制 概念 含义 初赛高频考点 运算器 完成算术计算和逻辑运算 加减乘除，与或非... 控制器 协调各组成按指令工作 "指挥"而不是"存储" 寄存器 CPU内部极小、极快的存储单元 速度很快但容量很小 主频 CPU的时间频率，如3.2GHz 高主频通常更快，但不是唯一因素 > 注意：CPU性能还受核心数，架构，缓存，指令集，内存速度等影响 ③内存与外存 特征：速度越快，通常容量越小，价格越高 寄存器(CPU)->缓存Cache->内存RAM->硬盘/U盘->云盘/光盘 速度:快->慢|容量:小->大 缓存Cache：介于CPU和内存之间，用来提高访问速度 ④存储单位的换算 单位 英文 关系 常见含义 bit 比特 / 位(老师课件里面的英文是中文) 最小的储存单位 只能表示0或1(bool类型) Byte 字节/B 1B=8bit 文件大小常用单位 KB KiloByte 1KB=1024B 小文本、图标 MB Megabyte 1MB = 1024KB 图片、音频 GB Gigabyte 1GB = 1024MB 视频、软件、硬盘容量 > 注意：b和B不一样,b表示bit, B表示Byte。1MB 不是 1Mb；总共可以自己想一个口诀：BKMGT(TB)比如：包括美国??不看芒果台?? ⑤计算机的原码、反码、补码 (1)机器数与真值 一个数在计算机中的二进制表示形式叫这个数的机器数。机器数是带符号的，它的最高位作为符号位：0表示位正数；1代表负数。机器数对应的真正数值被称为真值 > 例:以八位二进制为例子，+3表示为00000011,-3表示为10000011 (2)原码的取值范围 以八位二进制，原码的取值范围是+127127127~ −127-127−127，但是原码的取值范围并非真实数值的取值范围(+127+127+127~ −128-128−128) (3)反码 正数的反码和正数的原码一样，负数的反码是其符号位不变，其余各位取反所获得的码。 (4)补码 正数原反补码相同，负数的补码是反码+1 ⑥正数表示与范围 无符号看2n2^n2n，有符号补码看一半给负数 类型 n位标识范围 32位常见结论 unsigned int 000~2n−12^n-12n−1 0~232−12^{32}-1232−1 int −2n−1-2^{n-1}−2n−1~2n−1−12^{n-1}-12n−1−1 −231-2^{31}−231~231−12^{31}-1231−1 > 如果int*int已经溢出上限，再存入long long类型无法存储，应该选用long long * long long 或者1LL*int*int ⑦图片、音频、视频存储空间 图片大小=宽∗高∗每像素位数/8图片大小 = 宽 * 高 * 每像素位数 / 8 图片大小=宽∗高∗每像素位数/8 音频大小=采样率∗量化位数∗声道数∗时间/8音频大小 = 采样率*量化位数*声道数*时间/8 音频大小=采样率∗量化位数∗声道数∗时间/8 视频可以理解为图片连放 视频大小=宽∗高∗每像素位数/8∗帧率∗时长视频大小 = 宽*高*每像素位数/8*帧率*时长 视频大小=宽∗高∗每像素位数/8∗帧率∗时长 2.进制转换 ①进制 k进制代表逢k进1 > 16进制因为有十进制的10、11、12、13、14、15代表不了，使用A~F代表 ②K进制转10进制 按权展开:将各个数码与它的权值相乘，再相加。对于一个K进制数：从小数点往左看，第i位的权值为Ki−1K^{i-1}Ki−1，往右看则为K−iK^{-i}K−i 例:逢K近1 abcd.efg‾=aK3+bK2+cK1+dK0+eK−1+fK−2+gK−3\overline{abcd.efg} = aK^3+bK^2+cK^1+dK^0+eK^{-1}+fK^{-2}+gK^{-3} abcd.efg =aK3+bK2+cK1+dK0+eK−1+fK−2+gK−3 ③10转K进制 短除法:除以K取模，商为0结束，再将模数逆序排列 小数部分:乘以K取整数部分，小数部分积为0结束，再将整数顺序排列 > 10.25(10)转为2进制: > 10 / 2 = 5...0 > 5 / 2 = 2.....1 > 2 / 2 = 1.....0 > 1 / 2 = 0.....1 > 0.25 * 2 = 0.5->0 > 0.5 * 2 = 1->1 > ∴10.25(10) = 1010.01(2) 3.位运算 ①按位与(&)： 规则：将两个二进制数低位对齐，不足高位补零，对两个数字进行比较，只有两个数都是1时其结果对应位置才可为1其余情况皆为0 a b a & b 0 0 0 1 0 0 0 1 0 1 1 1 > 因为其特点，所以两个数字进行与运算不可能大于其中较小的数字 ②按位或(|) 规则:同按位与，但是当两个数中有1时其结果对应位置就为1，其余情况为0 a b a | b 0 0 0 1 0 1 0 1 1 1 1 1 > 因为其特点，所以两个数字进行或运算不可能小于其中较小的数字` ③按位非(~) 规则:将一个二进制数每一位取反(1变0，0变1)，符号位也要取反 ④按位异或(^) 规则:同按位与和或，只是两个数如果不同则为1，相同则为0 a b a ^ b 0 0 0 0 1 1 1 0 1 1 1 0 ⑤按位右移(>>) 规则：a>>ba>>ba>>b代表将二进制数a右移b位，高位补0，低位丢弃，符号位忽略 n>>m=n2mn>>m=\frac{n}{2^m} n>>m=2mn ⑥按位左移(<<) 规则：a<<ba<<ba<<b代表将二进制数a右移b位，高位丢弃，低位补0，符号位忽略 n<<m=2mn n<< m = 2^mn n<<m=2mn 4.链表指针 ①线性表的一种实现方式，由一系列在内存中不连续的存储块，通过指针连接而成 ②存储方式 数组存储方式是连续存储，因此可以用[]随机访问 链表为跳跃存储，因此在存储结构中必须有下个位置的信息 ③链表的跳跃存储 每一个链表节点表示链式结构中的一个存储单元，链表有一个节点连接而成。其主要分为两个部分：数据域和指针域 > |数据域:data|指针域:*next|->... ④链表的分类 (1)单向链表 仅拥有数据域和指针域，最后一个指针的后继指向空(NULL) > |data|*next|--> (2)双向链表 拥有数据与和前驱指针域与后继指针域，第一个指针的前驱与最后一个指针的后继指向空(NULL) > <-|*pre|data|*next|-> (3)循环链表 在单向或双向链表上增加最后一个节点的后继指向第一个节点，第一个的前驱指向最后一个节点 > |data|*next|<-|data|*next| > ㅤ ㅤ ㅤ |ㅤㅤ ㅤ ㅤ ˆ > ㅤㅤ ㅤ Vㅤㅤ ㅤ ㅤ | > ㅤ ㅤ ㅤ ————>| ⑤链表的代码 (1)链表节点的结构体定义 (2)链表申请动态内存 (3)新创节点 (4)访问与赋值 (5)新添加节点 (6)使用尾指针添加新节点 (7)插入新节点HE (8)删除节点HE (9)循环链表 5.栈与队列 ①栈(数组模仿的LIFO结构) (1)定义 (2)入栈 (3)出栈: (4)判空和大小 ②队列(数组模仿的FIFO结构) (1)定义 (2)入队 (3)出队 (4)访问队首元素 (5)访问队尾元素 (6)元素个数(大小) ③循环队列（防止假溢出） (1)意义：把数组首位相连，指针用%N绕回开头，能重复利用之前删掉的各自： (2)判空： (3)判满: (4)入队: (5)出队: (6)元素个数： (7）取队头/队尾 5.哈夫曼树与二叉树: ①二叉树的概念: 是一种度数最大为2的树形结构，即每个节点最多有2个子节点，每个节点严格分为左子树和右子树，被称为左子树和右子树 > 完全二叉树的概念:若某二叉树深kkk层，除第kkk层以外的层节点总数达最大值，且第kkk层节点小于等于2k−12^{k-1}2k−1并靠左侧连续 > 满二叉树的概念:在完全二叉树的基础上，第kkk层的节点数也达最大值 ②二叉树的性质: (1)在二叉树的第 III 层最多有2I−12^{I-1}2I−1个节点 (2)深度为 KKK 的二叉树至多有 2K−12^K-12K−1个节点(K≥1K ≥ 1K≥1) (3)任意一棵二叉树，若其叶子结点(度为 000 的节点)的数量为N0N0N0, 度为 222 的节点数量为 N2N2N2 则:N0N0N0 与 N2N2N2 一定满足N0=N2+1N0=N2+1N0=N2+1 (4)具有N(N≥0)N(N≥0)N(N≥0)个节点的完全二叉树的深度为⌊LOG2(N)⌋+1\LFLOOR LOG2(N) \RFLOOR + 1⌊LOG2(N)⌋+1 (5)针对编号节点为III的节点 其左孩子编号为2i2i2i 右孩子编号为2i+12i+12i+1 父节点为i2\frac{i}{2}2i (6)卡特兰数: 指nnn个节点能工程的不同二叉树形态数，计算公式如下 Catlan(n)=C2nnn+1Catlan(n) = \frac{C_{2n}^n}{n + 1} Catlan(n)=n+1C2nn ③二叉树的遍历 先序遍历：根左右(第一个点是根) 中序遍历：左根右(根的左边是左子树，右边是右子树) 后序遍历：左右根(最后一个点是根) 层序遍历：遍历每一层，每一层中从左往右遍历 ④哈夫曼树的意义 > 哈夫曼树也叫做“最优二叉树”，CSP-J初赛时常考构造过程与WPL > 目标是让出现频率高、权值大的节点离根更近，从而总路径代价最小 WPL=∑叶子节点权值×叶子节点到根的边数=∑非叶子节点权值WPL = \sum{叶子节点权值}×{叶子节点到根的边数} =\sum{非叶子节点权值} WPL=∑叶子节点权值×叶子节点到根的边数=∑非叶子节点权值 ⑤哈夫曼树的构架： 规则：根据贪心思想，每次合并最小的两个 (1)从所有权值中选出最小的两个 (2)合成新节点，权值为两者之和 (3)把新节点放回集合 (4)重复，直到只剩一个节点 ⑦哈夫曼树的性质： (1)哈夫曼树不唯一，但最小WPLWPLWPL相同 (2)NNN个叶子结点的哈夫曼树共有2N−12N-12N−1个节点 (3)哈夫曼树中没有度为111的节点 (4)权值越小的叶子通常更深，权值大的靠近根 6.表达式： ①表达式的分类 (1)中缀表达式：指运算符在操作数中间：A+B (2)前缀表达式（波兰式）：一种没有括号的算术表达式，且运算符在操作数的前面:+A B (3)后缀表达式（逆波兰式）：同波兰式，但是运算符在操作数后面:A B + ②中缀转前/后缀表达式: 这个其实有很多方法,有的人认为可以先按照运算顺序添加多级别的括号，在将运算符移动后去除括号，有的人则直接按照运算顺序将操作符移动 这里给个例子: > 一般方法: > a + b * c - (d + e) = ((a + (b * c)) - (d + e)) > 原式=((a + (b c *) - (d e + )) > ㅤㅤ=a b c * + d e + - > 原式=(a +(b * c) - ((d + e)) > ㅤㅤ=- + a * b c + d e ③后缀表达式的计算： > 后缀表达式的计算也可以用于后缀表达式转中缀表达式 规则： (1)从左往右扫描表达式 (2)遇到运算符,运算符放在左边的两个数中间进行运算(运算符左边第一个数字作为右操作数,运算符左边第二个作为左操作数 AB−=A−BA B - = A- BAB−=A−B )，并将计算结果作为下次计算的操作数 ④前缀表达式的计算： > 前缀表达式的计算也可以用于前缀表达式转中缀表达式 规则： (1)从右往左扫描表达式 (2)遇到运算符,运算符放在右边的两个数中间进行运算(运算符右边第一个数字作为左操作数,运算符右边第二个作为右操作数 −AB=A−B- A B = A- B−AB=A−B )，并将计算结果作为下次计算的操作数 7. 排序 ①冒泡排序 (1)规则：遍历N−1N-1N−1次数组，当下标III的元素大于I+1I+1I+1的元素时进行交换 (2)时间：最好O(N)O(N)O(N),最坏O(N2)O(N^2)O(N2) (3)稳定性:稳定 ②选择排序 (1)规则：每次排序在未排序区寻找最小元素，再与未排序区的的第一个元素进行交换 (2)时间复杂度:O(N2)O(N^2)O(N2) (3)稳定性:不稳定 ③插入排序: (1)规则：把左侧看成已排序区域，每次拿一个新元素，把它插入到左边有序区中正确位置。为了插入，左侧比他的元素依次向右移动 (2)性质：第K趟后前K+1个元素一定有序 (3)稳定性:稳定 (4)时间:最好O(N)O(N)O(N),最坏O(N2)O(N^2)O(N2) ④计数排序： (1)规则：定义一个CNT数组,将待排序的元素按照元素数值放入CNT数组，最后按照CNT数组下标大小依次输出 (2)时间：时间复杂度应该为O(N+K)O(N+K)O(N+K) (3)稳定性：标准写法可稳定 8.排列组合 ①排列 (1)排列的定义：指从给定元素中取出指定个数的元素进行排序 (2)排列的公式: {Anm(m≤n)=n(n−1)(n−2)...(n−(m−1))⏟m,①n(n−1)(n−2)...(n−(m−1))⏟m=n!(n−m)!,②\begin{cases} A^m_n(m≤n)= \underbrace{ n(n-1)(n-2)...(n-(m-1))}_{m},① \newline \underbrace{ n(n-1)(n-2)...(n-(m-1))}_{m}=\frac{n!}{(n-m)!},② \end{cases} ⎩⎨⎧ Anm (m≤n)=mn(n−1)(n−2)...(n−(m−1)) ,①mn(n−1)(n−2)...(n−(m−1)) =(n−m)!n! ,② (3)公式推导解释：根据乘法的原理，可以推出①式，再在上下同时乘以(N−M)!(N-M)!(N−M)!,即可推出② ②组合 (1)组合的定义：指从给定元素中，仅仅取出指定个数的元素 > 例如:213、312两组是不同的排列但是是同一种组合 (2)组合的公式 {Anm=***⋅AmmCnm⋅m!=n!(n−m)!***=n!m!(n−m)!\begin{cases} A^m_n=C^m_n \cdot A^m_m \newline C^m_n \cdot m! = \frac{n!}{(n-m)!} \newline C^m_n=\frac{n!}{m!(n-m)!} \end{cases} ⎩⎨⎧ Anm =*** ⋅Amm *** ⋅m!=(n−m)!n! *** =m!(n−m)!n! ③排列组合的计算: (1)特殊优先： > 例题：6个人排队，甲不在排头，乙不在排尾 > 第一类：乙在开头：A55A^5_5A55 > 第二类：乙放在中间四个:C41∗C41∗A44C^1_4 * C^1_4 * A^4_4C41 ∗C41 ∗A44 > 答案：A55+C41∗C41∗A44A^5_5+C^1_4*C^1_4*A^4_4A55 +C41 ∗C41 ∗A44 (2)捆绑法、插空法: > 例题：8个人站一排，求 > 1.甲乙相邻:A22∗A77A^2_2*A^7_7A22 ∗A77 ，因为把甲乙捆绑在一起，8个位置可以放在7个位置，然后甲乙可以换位置 > 2.甲乙不相邻A66∗A72A^6_6*A^2_7A66 ∗A72 ，先排其他人，再把甲乙插入空隙或者两边中，保证两人不挨在一起 （3)隔板法: 做法： 求不定方程的正整数/非负整数解: x1+x2...+xm⏞m=n\overbrace{x_1+x_2...+x_m}^{m} = n x1 +x2 ...+xm m =n 正整数解的数量：Cn−1m−1C^{m-1}_{n-1}Cn−1m−1 非负整数解的数量:****−1m−1C^{m-1}_{n+m-1}****−1m−1 > 10个人分配到8个班，有多少种方法？ > 把8个班想成7个隔板，隔板两边代表2个班，相当于10个人的9个空中插入7个隔板，所以答案是C97C_9^7C97 9.图论 ①度的性质 (1)握手定理：因为每条边贡献了两个端点各1度，所以无向图中所有的顶点的都之和=边数的两倍，即： ∑deg(v)=2m\sum{deg(v)}=2m ∑deg(v)=2m (2)奇度顶点个数必为偶数 (3)有向图中，所有顶点的入度之和 = 出度之和 = 边数MMM > 易错：有向图的握手定理和无向图是不一样的 ②路径 沿着边从一个顶点走到另一个顶点，会形成不同的走法 术语 定义 关键区别 路径path 从某个顶点沿着依次抵达另一顶点的顶点/边序列v0−>v1−>...−>vkv_0->v_1->...->v_kv0 −>v1 −>...−>vk 顶点和边都可以重复 简单路径simple path 路径上的顶点都不重复（不经过同一顶点两次） 顶点不重复 回路 / 环 cycle 起点和终点相同的路径 收尾同一点 简单回路 / 简单环 simple cycle 除了[起点=终点]之外，其余顶点都不重复的回路 中间顶点不重复 路径长度：无权图为路径经过的边数；带权则为路径上各边的权值之和 > 易错点：简单路径强调 [顶点不重复];简单回路允许 [起点=终点]，但中间顶点不能重复。“最短路径”一般默认为简单路径 ③ 结尾: 祝大家初赛满分吧。

为什么没人用并查集啊

这题太难了吧 😭😭😭

错哪儿了

看看谁的代码编译时间最少！（任何题目、任何代码） 我先来：

此是非官方题解，请勿乱抄，你会被击败的 全是动态规划，最简单的还是1,5 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正片开始 1： 2： 3： 4： 5： 小码王主打一个少年AI编程，教我们的老师是NOONMPLE: 午枫 无敌辣

CSP-J 总结 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 内存数据 速度越快，通常容量越小，价格越高 bit(b)→8Byte(B)→1024KB→1024MB→1024GB\tt{bit (b)} \rightarrow^8 \tt{Byte (B)} \rightarrow^{1024} \tt{KB} \rightarrow^{1024} MB \rightarrow^{1024} \tt{GB}bit(b)→8Byte(B)→1024KB→1024MB→1024GB [1] 其中 bit\tt{bit}bit 为最小单位，Byte\tt{Byte}Byte 为基本单位。 数值在计算机中是以补码的方式存储。 以下是原码反码补码的例子： 正数 负数 原码 00001001 10001001 反码 00001001 11110110 补码 00001001 11110111 其中数字的第一个字符为符号位，000 为正数，111 为负数。 原码是原本的数值的二进制，第一位是符号位，例如十进制的 333 的原码是 000000110000001100000011，十进制的 −3-3−3 的原码是 100000111000001110000011。 反码是原码除了符号位的数值都取反，例如十进制的 333 的反码是 011111000111110001111100，十进制的 −3-3−3 的补码是 111111001111110011111100。 补码是在反码的基础上加 111，包含进位。例如十进制的 333 的补码是 011111010111110101111101，十进制的 −3-3−3 的补是 111111011111110111111101。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 各类大小 有符号 nnn 位二进制整数范围为 [−2n−1, 2n−1−1][-2^{n-1},\space 2^{n-1}-1][−2n−1, 2n−1−1]。 无符号 nnn 位二进制整数范围为 [0, 2n−1][0,\space 2^n-1][0, 2n−1]。 图片大小计算公式为： 宽×高×每位像素位数 (÷8 Byte)宽 \times 高 \times 每位像素位数 \space(\div 8 \space\tt{Byte}) 宽×高×每位像素位数 (÷8 Byte) 例如，1920×10801920 \times 10801920×1080 的 242424 位真彩色图像：                            \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space                            1920×1080×24÷8=62208001920 \times 1080 \times 24 \div 8 = 62208001920×1080×24÷8=6220800 B≈\tt{B} \approxB≈ 5.93 MB5.93 \space \tt{MB}5.93 MB 音频大小计算公式为： 采样率×量化位数×声道数 (单声道为1，双声道为2)×时同 (÷8 Byte)采样率 \times 量化位数 \times 声道数 \space(单声道为 1，双声道为 2) \times 时同 \space(\div 8 \space\tt{Byte}) 采样率×量化位数×声道数 (单声道为1，双声道为2)×时同 (÷8 Byte) 视频大小计算公式为： 每帧图像大小×帧率×秒 (÷8 Byte)每帧图像大小 \times 帧率 \times 秒\space (\div 8 \space\tt{Byte}) 每帧图像大小×帧率×秒 (÷8 Byte) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 数据类型 * char : 888 位，111 字节 * short : 161616 位，222 字节 * int : 323232 位，444 字节 * long long : 646464 位，888 字节 * float : 323232 位，444 字节 * double : 646464 位，888 字节 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 进制转换 简单的英文进制表示符： 字母 进制 B\tt{B}B 二 O\tt{O}O 八 D\tt{D}D 十 H\tt{H}H 十六 当 0x\tt{0x}0x 作为开头是十六进制。 整数部分十进制转为 KKK 进制（短除法）： * 不断除 kkk，商 000 为止，逆序除余。 例子：十进制的 101010 要转为二进制。10÷2=5 ⋯ ⋯0，5÷2=2 ⋯ ⋯1,2÷2=1 ⋯ ⋯0,1÷2=0 ⋯ ⋯110 \div 2 = 5 \space\cdots\space\cdots 0，5 \div 2 = 2 \space\cdots\space\cdots 1,2 \div 2 = 1 \space\cdots\space\cdots 0, 1 \div 2 = 0 \space\cdots\space\cdots 110÷2=5 ⋯ ⋯0，5÷2=2 ⋯ ⋯1,2÷2=1 ⋯ ⋯0,1÷2=0 ⋯ ⋯1，所以二进制为 (1010)2=(10)10(1010)_2 = (10)_{10}(1010)2 =(10)10 。 小数部分十进制转为 KKK 进制： * 不断乘 kkk，小数为 000，正序取整。 例子：十进制的 0.6250.6250.625 要转为二进制。0.625×2=1.25⋯ ⋯1，0.25×2=0.5⋯ ⋯0，0.5×2=1⋯ ⋯10.625 \times 2 = 1.25 \cdots \space \cdots1，0.25 \times 2 = 0.5 \cdots \space \cdots0，0.5 \times 2 = 1 \cdots \space \cdots10.625×2=1.25⋯ ⋯1，0.25×2=0.5⋯ ⋯0，0.5×2=1⋯ ⋯1，所以二进制为 (101)2=(0.625)10(101)_2 = (0.625)_{10}(101)2 =(0.625)10 整数部分 KKK 进制转为十进制： 例子：二进制 100110011001 要转为十进制。 18(23)04(22)02(21)11(20)1_{8 (2^3)}0_{4 (2^2)}0_{2 (2^1)}1_{1 (2^0)} 18(23) 04(22) 02(21) 11(20) 将原本得值乘上权值。 1×1+1×8=1+8=91 \times 1 + 1 \times 8 = 1 + 8 = 9 1×1+1×8=1+8=9 所以 (9)10=(1001)2(9)_{10} = (1001)_2(9)10 =(1001)2 。 小数部分 KKK 进制转为十进制： 例子：二进制 0.1010.1010.101 要转为十进制。 0.10.5(k−1)00.25(k−2)10.125(k−3)0.1_{0.5(k^{-1})}0_{0.25(k^{-2})}1_{0.125(k^{-3})} 0.10.5(k−1) 00.25(k−2) 10.125(k−3) 将原本得值乘上权值。 1×0.5+1×0.125=0.6251 \times 0.5 + 1 \times 0.125 = 0.625 1×0.5+1×0.125=0.625 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 位运算 位运算一共有 666 种，都是在补码的形态下计算的，包括： * 按位与 & * 按位或 | * 按位异或 ^ * 按位取反 ~ * 左移 << * 右移 >> 按位与 aaa bbb a & ba\space \& \space ba & b 0 0 0 1 0 0 0 1 0 1 1 1 按位或 aaa bbb a ∣ ba\space |\space ba ∣ b 0 0 0 1 0 1 0 1 1 1 1 1 按位异或 aaa bbb aaa ^ bbb 0 0 0 1 0 1 0 1 1 1 1 0 右移 n>>m=⌊n2m⌋n >> m = \lfloor \frac{n}{2^m}\rfloorn>>m=⌊2mn ⌋ 左移 n<<m=n×2mn << m = n \times 2^mn<<m=n×2m 特殊性质 * a ∣ b≥max⁡(a,b)a\space | \space b \geq \max(a, b)a ∣ b≥max(a,b) * a & b≤min⁡(a,b)a\space \& \space b \leq \min(a, b)a & b≤min(a,b) * aaa ^ b≤a+bb \leq a + bb≤a+b * ∼x=−(x+1)\sim x = - (x+1)∼x=−(x+1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 链表和指针 链表有分单向链表和双向链表。 单向链表中间插入：（在 AAA 节点后插入 BBB 节点） ①\color{red}{①}① b→next=a→nextb\rightarrow next = a\rightarrow nextb→next=a→next ②\color{red}{②}② a→next=ba \rightarrow next = ba→next=b 单向链表删除节点：（删除 BBB 节点） ①\color{red}{①}① a→next=b→nexta\rightarrow next = b\rightarrow nexta→next=b→next 双向链表中间插入：（在 AAA 节点后插入 BBB 节点） ①\color{red}{①}① b→next=a→nextb\rightarrow next = a \rightarrow nextb→next=a→next ②\color{red}{②}② a→next=ba\rightarrow next = ba→next=b ③\color{red}{③}③ b→pre=ab \rightarrow pre = ab→pre=a ④\color{red}{④}④ b→next→pre=bb \rightarrow next \rightarrow pre = bb→next→pre=b 双向链表删除节点：（删除 BBB 节点） ①\color{red}{①}① b→pre→next=b→nextb \rightarrow pre \rightarrow next = b \rightarrow nextb→pre→next=b→next ②\color{red}{②}② b→next→pre=b→preb \rightarrow next \rightarrow pre = b \rightarrow preb→next→pre=b→pre ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 栈和队列 栈 * 先进后出 FILO\tt{FILO}FILO 队列 * 先进先出 FIFO\tt{FIFO}FIFO ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 树 二叉树的性质 * 二叉树第 iii 层上最多有 2i−12^{i-1}2i−1 个节点。（根在 111 层） * 深度为 kkk 的二叉树只多有 2k−12^k - 12k−1 个节点。（根在 111 层） * 任意一根二叉树，若其叶子结点的数量为 n0n0n0，度为 111 的数量为 n1n1n1，度为 222 的数量为 n2n2n2，则 n0n0n0 与 n2n2n2 一定满足 n0=n2+1n0 = n2+1n0=n2+1 和 n=n0+n1+n2n = n0 + n1 + n2n=n0+n1+n2。 * 具有 n (n≥0)n \space (n \geq 0)n (n≥0) 个节点的完全二叉树的深度为 ⌊log⁡2(n)⌋+1\lfloor \log_2(n)\rfloor + 1⌊log2 (n)⌋+1。 * 若将一颗有 nnn 个节点的完全二叉树自顶而下，同一层自左向右连续给节点编号 1,2,⋯ ,n1, 2, \cdots, n1,2,⋯,n ，则： * 针对编号为 iii 的节点： * 其左孩子的编号为 2×i (2×i≤n)2\times i\space (2 \times i \leq n)2×i (2×i≤n) * 其右孩子的编号为 2×i+1 (2×i+1≤n)2\times i + 1\space (2 \times i+1 \leq n)2×i+1 (2×i+1≤n) 树的遍历 * 先序遍历（根左右） * 中序遍历（左根右） * 后序遍历（左右根） 哈夫曼树 构造 先排序然后两两一组，得出了和之后将和插入，继续循环直至没有值。 带权路径长度 带权路径长度计算公式如下： 带全路径长度 (WPL)=∑(叶子权值×叶子到根的边数)带全路径长度 \space(WPL)=\sum(叶子权值 \times 叶子到根的边数) 带全路径长度 (WPL)=∑(叶子权值×叶子到根的边数) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 图 简单图为没有自环和重边。 多重图为有自环或重边。 完全无向图含有 n×(n−1)2\frac{n \times (n-1)}{2}2n×(n−1) 条边。 有向完全图含有 n×(n−1)n \times (n - 1)n×(n−1) 条边。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 排序 * 冒泡排序 * 一趟确定一个最大值的最终位置 * 选择排序 * 一趟确定一个最小值的最终位置 * 插入排序 * 左边始终有序，当前值找到位置插进去，第 kkk 趟后，前 k+1k + 1k+1 个元素一定是有序的。 定义稳定性为：如果两个元素关键字相同，排序后他们的相对先后顺序不变。 排序算法 稳定性 冒泡排序 ✔\color{green}{✔}✔ 选择排序 ✖\color{red}{✖}✖ 插入排序 ✔\color{green}{✔}✔ 计数排序 半稳定 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前中后缀表达式 中缀 → 后缀 例子为： a+b×c−(d+e)a + b \times c - (d + e) a+b×c−(d+e) 1. 对所有的运算按优先级增加括号： ((a+(b×c))−(d+e))((a + (b \times c)) - (d + e)) ((a+(b×c))−(d+e)) 2. 从内到外江运算符移动至操作数后： ((a (b c ×)+) (d e +) −)((a \space(b\space c\space\times)+) \space (d\space e\space +)\space -) ((a (b c ×)+) (d e +) −) 3. 去括号： a b c×+ d e+−a\space b\space c\times+ \space d\space e+- a b c×+ d e+− 中缀 → 前缀 例子为： a+b×c−(d+e)a + b \times c - (d + e) a+b×c−(d+e) 1. 对所有的运算按优先级增加括号： ((a+(b×c))−(d+e))((a + (b \times c)) - (d + e)) ((a+(b×c))−(d+e)) 2. 从内到外江运算符移动至操作数前： (− (+ a (× b c))(+ d e))(-\space(+\space a \space(\times \space b \space c)) (+\space d \space e)) (− (+ a (× b c))(+ d e)) 3. 去括号： − + a × b c+ d e-\space+\space a \space\times \space b \space c+\space d \space e − + a × b c+ d e 后缀 → 中缀 例子为： a b c×+ d e+−a\space b\space c\times+ \space d\space e+- a b c×+ d e+− 1. 从左到右遍历，如果遇见符号就将符号插入前面两个值得中间并加上括号： a (b×c) +d e +−a\space (b \times c)\space + d\space e\space + - a (b×c) +d e +− (a+(b×c)) d e +−(a + (b\times c))\space d\space e\space + - (a+(b×c)) d e +− (a+(b×c)) (d+e) −(a + (b\times c))\space (d+ e)\space - (a+(b×c)) (d+e) − ((a+(b×c))−(d+e))((a + (b\times c))- (d+ e)) ((a+(b×c))−(d+e)) 2. 去掉可以去的括号： a+b×c−(d+e)a + b\times c- (d+ e) a+b×c−(d+e) 前缀 → 中缀 例子为： − + a × b c+ d e-\space+\space a \space\times \space b \space c+\space d \space e − + a × b c+ d e 1. 从右到左遍历，如果遇见符号就将符号插入前面两个值得中间并加上括号： − + a × b c (d+e)-\space+\space a \space\times \space b \space c\space (d + e) − + a × b c (d+e) − + a (b×c) (d+e)-\space+\space a \space (b \times c)\space (d + e) − + a (b×c) (d+e) − (a+(b×c)) (d+e)-\space (a +(b \times c))\space (d + e) − (a+(b×c)) (d+e) ((a+(b×c))−(d+e))((a +(b \times c))- (d + e)) ((a+(b×c))−(d+e)) 2. 去掉可以去的括号： a+b×c−(d+e)a +b \times c- (d + e) a+b×c−(d+e) 后缀 → 前缀 现把后缀转为中缀，再将中缀转为前缀。 前缀 → 后缀 现把前缀转为中缀，再将中缀转为后缀。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 排列组合 从 nnn 个数中取 mmm 个数的排列被记为 AnmA^m_nAnm 或 PnmP^m_nPnm 的排列。 全排列是当 n=mn=mn=m 的特殊情况。 Anm=n×(n−1)×(n−2)×⋯×(n−(m−1))A^m_n = n \times (n-1) \times (n-2) \times \cdots \times (n - (m - 1)) Anm =n×(n−1)×(n−2)×⋯×(n−(m−1))                                =n!(n−m)! (0!=1)\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space=\frac{n!}{(n-m)!}\space (0!=1)                               =(n−m)!n!  (0!=1)  \space  Anm=Cnm×AmmA^m_n = C^m_n \times A^m_m Anm =*** ×Amm ***=n!m!(n−m)!=Cnn−mC^m_n = \frac{n!}{m!(n-m)!}=C^{n-m}_{n} *** =m!(n−m)!n! =Cnn−m 排列组合的方法 * 特殊优先 * 捆绑法 * 排除法 * 隔板法 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 有任何问题可以纠正！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. A→xB\tt{A} \rightarrow^x \tt{B}A→xB 表示一 B\tt{B}B 等于 xxx 个 A\tt{A}A。例如 Byte→1024KB\tt{Byte} \rightarrow^{1024} \tt{KB}Byte→1024KB 就表示 1KB1 \tt{KB}1KB 等于 1024 Byte1024\space\tt{Byte}1024 Byte。 ↩︎