中国珂学院💭

引言 在 C/C++ 中，不少人把声明（declaration）和定义（definition）搞混淆，下面就通过这篇文章，来详细阐述一下这两者的区别。 声明和定义的概念 声明（declaration）：是指出存储类型，并给存储单元指定名称。 定义（definition）：是分配内存空间，还可为变量指定初始值。 所以，根据这个定义，我们不难发现： 声明可以看做一种规范（规定存储类型和存储单元的名称），所以我们可以在不同的文件进行多次声明，而不会产生冲突。 而定义会对声明的内容进行分配存储空间和初始化等等操作，这个过程是不可以多次重复进行的。 规范 在 C/C++ 的规范中，我们将声明的内容放入头文件 (.h) 中，并且使用 #ifndef的方式来避免重复包含，而将定义的内容放在源文件 (.c, .cpp) 中，所以，我们应该只include头文件，而不应该去引入源文件，这样就能避免重复定义而导致在编译过程中无法进行链接。 具体例子：声明 注：本文就不细讲 extern的具体用法和注意事项了，请自行补充。 假设我们有3个文件，分别是：test1.h、test2.h、main.c ...

引子 在很多博客和视频中，不少人都将 取余(rem) 和 取模(mod) 混为一谈，虽然这两个是同一种运算，实际上他们区别很大，而编程语言的 % 符号，不同语言有着不同的处理方式，比如在 C/C++ 中，这个符号代表 “取余”，而在 Python 中，这个符号代表着 “取模”。 为什么同一种运算会出现区别呢？ 因为在被除数和除数的符号不同时，余数的符号会产生歧义，可正可负。 取模定理和求余定理 前提：设 a=kb+ra = kb + ra=kb+r， 且满足 0≤∣a∣≤∣k∣0 \leq \left | a\right | \leq \left | k\right |0≤∣a∣≤∣k∣ 给定 aaa 和 kkk，求 mod(a,k)mod(a, k)mod(a,k) 和 rem(a,k)rem(a, k)rem(a,k) 显然，对于满足上述两个前提条件，如果 aaa 无法整除 kkk，则存在两对(b,r)(b, r)(b,r)，其中一对的 rrr 为正数（正余数），另一对 rrr 为负数 (负余数) ，我们也可以用一个时钟从0点顺时针和逆时针走到某一点的两种方案来理解。 结果：正因为 ...

1. 快速排序快速简介 快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序个项目要Θ(nlogn)\Theta(nlogn)Θ(nlogn)次比较。在最坏状况下则需要Θ(n2)\Theta (n^2)Θ(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环（inner loop)可以在大部分的架构上很有效率地达成。 2. 快速排序思想 快速排序使用的是分治法中分而治之的思想，把一个待排序的序列分成两个子序列，然后递归的对两个子序列进行操作。（尽量使两个子序列大小接近能获得最优性能） 对某个下标范围为 [l,r][l, r][l,r] 的序列的操作步骤如下： Step1：挑选一个基准值：从数列中以某种方法挑出一个元素，称为 “基准”（pivot）; Step2：划分(partition)：以某种方法将序列重新排序，获得一个新的序列，其满足所有比基准值小的元素都摆放着基准的前面，所有比基准大的元素都摆放在基准值的后面，与基准值相 ...

完整教材： • 全书：Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom: Database systems - the complete book (2. ed.). Pearson Education 2009, ISBN 978-0-13-187325-4, pp. I-XXVI, 1-1203 • 奶牛书：Raghu Ramakrishnan, Johannes Gehrke: Database management systems (3. ed.). McGraw-Hill 2003, ISBN 978-0-07-115110-8, pp. I-XXXII, 1-1065 数据库基础 • 帆船书：Abraham Silberschatz, Henry F. Korth, S. Sudarshan: Database System Concepts, 6th Edition. McGraw-Hill Book Company 2010 • 全书前一半：Hector Garcia-Molina, Jeffrey ...

之前博客因服务器即将到期，迁移数据比较麻烦，所以重新选择了静态博客作为自己的新博客。 本博客使用Hexo作为博客系统，Buffterfly(和自己魔改的内容)作为主题，并使用Vercel的CI/CD功能自动部署。 代码块测试 1234#include <iostream>int main() { std::cout << "hello, world" << std::endl;} 数学公式测试 E=mc2E = mc^2E=mc2 c=abc = \frac{a}{b}c=ba​ 引用和行内代码测试 include <stdio.h> Hexo + Butterfly 强调语法测试 外挂标签预览 语法： 123456{% u 文本内容 %}{% emp 文本内容 %}{% wavy 文本内容 %}{% del 文本内容 %}{% kbd 文本内容 %}{% psw 文本内容 %} ...

1.C++IO流的同步和绑定 在C++中，cin和cout的速度其实不并不慢，C++中的流的IO速度相当的快，其速度与初始设定的缓存区大小和硬盘的IO速度有关。 但在C++中，为了兼容C的IO(scanf和printf)，cin和cout被设置为与C的IO同步，这样导致cin和cout的速度不如scanf和printf快。 另外，在默认情况下，标准输入设备(cin)与标准输出设备(cout)绑定在一起，它保证在调用输入之前已经刷新输出缓冲区，这样也会降低读取效率。 所以，我们可以手动取消他们与C语言IO的同步，并去掉cin和cout的绑定，加速读取，使cin的速度与scanf相差无几，甚至某些情况要快于scanf。 注：在取消绑定后，使用scanf和printf可能会出现问题，比如读取失败或者提前输出的问题，请不要再使用他们，不过可以使用getchar和gets等读入函数。 加速代码： 12345// 取消C++ IO与C的同步std::ios::sync_with_stdio(false);// 取消cin和cout的绑定std::cin.tie(NULL);/*等价于cin.tie ...

1.什么是图床？ 所谓图床工具，就是自动把本地图片转换成链接的一款工具，网络上有很多图床工具，就目前使用种类而言，PicGo 算得上一款比较优秀的图床工具。它是一款用 Electron-vue 开发的软件，可以支持微博，七牛云，腾讯云COS，又拍云，GitHub，阿里云OSS，SM.MS，imgur 等8种常用图床，功能强大，简单易用。 这里是最新版本的项目发布地址： https://github.com/Molunerfinn/PicGo/releases 如果是macos系统，请选择dmg版本下载，windows系统请选择exe版本下载。 下面我们来具体说一下如何进行操作。 2.如何使用PicGo 首先，我们要在github中新建一个仓库，这个仓库可以随意命名，建议名字短一点，这样最后生成的链接也更短。（注：一定要创建公共仓库，私有仓库是无法通过外链显示的) 创建好后，我们需要在github上生成一个token，这样PicGo才能直接对github仓库内容进行操作。 点击头像–>setting–> Developer settings 在侧边栏选择Perso ...

1.单调栈的定义 单调栈是一种特殊的栈，特殊之处在于栈内的元素都保持一个单调性，可能为单调递增，也可能为单调递减。 2.单调栈的意义 能用来维护一个单调序列，可以解决某些区间最值问题，一般题目中会含有最高、最低等单调性词汇，以及最近等词汇。 对于一道题目而言,我们需要对于条件,性质两处地方动手,来思考算法或者数据结构的突破口。 3.例题一：仰视奶牛 **例题传送门：**https://www.acwing.com/problem/content/602/ **题意：**这道题目大致意思是:每一头奶牛往右看,找到离自己最近,而且比自己身高高的牛,如果没有比自己高的牛,那么输出0即可.也就是无解判断。 算法分析： 首先我们知道程序=数据结构+算法,这道题目算法,我们除了暴力+模拟,实在想不到任何解题思路.可能是我太蠢了 所以我们考虑如何通过数据结构来优化这道题目. 数据结构： 对于一道题目而言,我们需要对于条件,性质两处地方动手,来思考算法或者数据结构的突破口,显然这道题目数据结构的确定,同样离不开这条不定的定律. 对于这道题目而言,我们主要是分析条件,因为我们发现这道题目所有的奶牛, ...

1.单调队列的定义 单调队列顾名思义,就是具有单调性质和队列性质的数据结构. 2.单调队列的时间复杂度 单调队列可以保证,对于任何一个数而言,只会在队列中出现一次,一旦这个数对于最后答案没有贡献了,就会及时地将它删除. 一般来说,入队和出队操作满足以下两点. 入队操作:对于一个点而言,如果说它加入队列后满足队列的单调性质,那么我们就可以入队. 出队操作:对于一个点而言,如果说新加入的点,比它更加具有潜力,潜力一般指(拓展性更强,生存能力更高,节点入队时间短.) 因此单调队列的复杂度是我们除了常数复杂度O(1)O(1),O(log)O(log)复杂度级别,第三位最喜欢的线性复杂度O(n)O(n),因为这种算法往往代码短,思路好想,符合人类思维. 所以单调队列算法发明者相信,码量适中,思路精简,结构典型的单调队列,一定可以给你的程序员之旅一个有力的帮助. 3.单调队列适用于那些范围 单调队列,其实是单调栈的一个升级plus版本,或者说是具有[l,r]区间性质的单调栈.(注:单调栈一般来说是[0,r]类型的) 换句话来说,对于单调栈可以做出来的题目,基本上单调队列是可以操作出来的,而且 ...

题目传送门 最短Hamilton路径 内容引入 总所周知，旅行商问题是一个NP完全问题，即没有一个合适的算法来解决它，只能用朴素算法(也就是通常所说的暴力算法)去进行优化。 Hamilton路径的定义：在一张图中，从点0到点n-1不重不漏的恰好经过每一个点一次的路径。 解题思路 我们很容易联想到朴素算法，即dfs枚举n个点的全排列，计算路径长度去最小值，这样时间复杂度为O(n∗n!)O(n*n!)O(n∗n!),如果n的个数过大，那么对于计算机，这也是一个无解问题。 因为n个点，每个点有两种情况，经过和暂时未经过，这样，就有2n2^n2n种状态，我们可以使用二进制状态压缩DP来优化这个朴素算法，时间复杂度为O(n∗2n)O(n * 2 ^n)O(n∗2n)，即状态数乘以状态转移复杂度得到。 我们可以使用一个n位二进制数来表示状态，若其第iii位为1，则表示第iii个点已经被经过，反之未被经过。 在任意时刻还需要知道当前所处的位置，因此我们可以用F[i,j](0≤i≤2n,0≤j<n)F[i,j](0 ≤ i ≤ 2 ^n, 0 ≤ j < n)F[i,j](0≤i≤2n ...