这是我的第一篇个人博客，接下来将为您介绍：
本博客如何食用、我的联系方式、其他博客推荐

最近闲来无事（犯懒），把CS144的lab记一下（目前lab4待调试，但是时间被占用了，后面看情况填坑吧QAQ）

前置知识建议学下MIT6.081，good to have

树状数组

定义

树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。

构造

参考链接

C81【模板】树状数组 点修+区查 区修+点查

C81【模板】树状数组

并查集的定义

并查集（Union Find）：一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。不交集指的是一系列没有重复元素的集合。

并查集主要支持两种操作：

• 合并（Union）：将两个集合合并成一个集合。
• 查找（Find）：确定某个元素属于哪个集合。通常是返回集合内的一个「代表元素」。

原文：Introduction to the A* Algorithm，本文略有改动

lab导航

以下两个网站主要登记了国外计算机专业的课程和一些学习经验，方便找lab和工具学习文章

1. CS自学指南
2. HackWay技术学习路线
3. CS基础课不完全自学指南-康宇PL’s Blog

工具学习

1. Makefile

2. Linux101（入门）

前言

2024新年伊始，我也到了要准备工作的时候了，我计划开始写一篇长篇的C++面经整理，记录看到的点滴面经。

目录：（一级标题：知识框架；二级标题：知识领域；三级标题：面试问题：四级：内容）

• C++语言
  • 特性
  • 原理
  • 内存安全
• 工具
• 算法题
• Linux
• 操作系统
• 计算机网络
• 设计模式
• 测试调优
• 数据库原理

C++语言

特性

C++11有哪些特性？

C++20有哪些特性？

原理

cpp编译一般经过几个步骤?

1. 预处理阶段：在这个阶段，预处理器处理源文件中的预处理指令，比如 #include、#define 等。预处理器会根据这些指令展开头文件并替换宏定义，生成一个经过预处理的源文件。

   1	$ g++ -E source.cpp -o source.ii

2. 编译阶段：编译器将预处理后的源文件转换成汇编代码。在这个阶段，编译器会对源文件进行词法分析、语法分析和语义分析，并生成相应的中间代码或汇编代码。

   1	$ g++ -S source.ii -o source.s

3. 汇编阶段：汇编器将汇编代码转换成机器码或者目标文件。在这个阶段，汇编器会将汇编代码转换成可重定位的机器码，并生成目标文件。

   1	$ as source.s -o source.o

4. 链接阶段：链接器将目标文件和库文件链接在一起，生成最终的可执行文件。在这个阶段，链接器会解析目标文件之间的引用关系，将它们连接到正确的位置上，并将库文件中的函数和变量链接到可执行文件中。

   1	$ g++ source.o -o executable

内存安全

工具

MySQL

CMake

算法题

Linux

操作系统

计算机网络

设计模式

测试调优

数据库原理

题解

在归并排序中加一行公式计算原序列逆序数

在合并过程中，如果a[i]大于a[j]，那么a[i]后面的元素也都大于a[j]，所以逆序对的数量就是从i到mid的元素的数量，即mid - i + 1。

AC代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100005;

int n;
long long k,ans;
int a[N],b[N];


void merge(int l, int mid, int r){
    int i = l, j = mid + 1;
    int idx = 0;
    while(i <= mid && j <= r){
        if(a[i] > a[j]){
            b[idx ++] = a[j ++];
            ans += mid - i + 1;
        }
        else b[idx ++] = a[i ++];
    }
    while(i <= mid )b[idx ++] = a[i ++];
    while(j <= r )b[idx ++] = a[j ++];
    for (int i = 0; i < idx; ++i)
    {
        a[l + i] = b[i];
    }
    return;
}

void merge_sort(int l, int r){
    int mid = (l + r) / 2;
    if(l >= r)return;
    else{
        merge_sort(l, mid);
        merge_sort(mid +1, r);
        merge(l, mid, r);
    }
    return;
}


int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    while(cin >> n >> k){
        memset(b, 0, N);
        memset(a, 0, N);
        ans = 0;
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
        }
        merge_sort(0, n - 1);
        cout << (ans - k > 0 ? (long long)(ans - k) : 0) << endl;
    }
    return 0;
}

1. muduo安装

参考链接

2. 编译

参考同上

3. 编写echo服务代码

muduo作者写的三个半：

https://blog.csdn.net/Solstice/article/details/6171831

我认为，TCP 网络编程最本质的是处理三个半事件：

1. 连接的建立，包括服务端接受 (accept) 新连接和客户端成功发起 (connect) 连接；
2. 连接的断开，包括主动断开 (close 或 shutdown) 和被动断开 (read 返回 0)；
3. 消息到达，文件描述符可读。这是最为重要的一个事件，对它的处理方式决定了网络编程的风格（阻塞还是非阻塞，如何处理分包，应用层的缓冲如何设计等等）；
4. 消息发送完毕，这算半个。对于低流量的服务，可以不必关心这个事件；另外，这里“发送完毕”是指将数据写入操作系统的缓冲区，将由 TCP 协议栈负责数据的发送与重传，不代表对方已经收到数据。

参考文章

浅谈线段树

线段树

线段树是基于分治思想的二叉树，用于维护区间信息（区间和、区间最值、区间GCD等），可以在logn的时间内执行区间修改和区间查询。

线段树中每个叶子节点储存元素本身，非子叶节点存储区间内元素的统计值。

• 优点：较快完成区间更新和查询
• 缺点：空间大(2n - 4n)

代码实现

A

题解

因为最晚也会在 t = 1 的时候使用工具，如果数不大于 a - 1 ，则全部保留，其他保留a - 1

题目

• ACWing 843

题目

• ACWing 844

题目

• ACWing 842

Bits

安装参考

• B站视频

• 教程：尚硅谷

学习教程

21分钟速成MySQL 来自Github

原文链接 - 知乎

作者：陈益波

转载记：作者的专业水平虽然大部分人达不到，但是可以作为学习计算机编程的一个清单，文章很多经验之谈在学长学姐那里也听过，脚踏实地，立意高远。

作者于2015年博士毕业加入一家量化私募公司，刚好做了四年系统工程师的工作。本文作为这个岗位所用到的技能总结，希望对想进入这个行业的人有所帮助。本人非科班出身，工作中用的技术大多数通过自学获得，有不足之处还请同行多多指教，有好的学习资料希望不吝推荐！

量化交易这些年在国内方兴未艾，这几年国外顶级量化交易公司纷纷进入国内来捞金。预计未来量化交易在中国会有一个长足发展。一般量化团队分两类技术工种，策略开发岗和系统开发岗。本文介绍系统开发岗涉及的一些技术知识，文中前面几点C++、 操作系统、网络等是核心技能，后面几点是辅助技能。精学其中的一部分就足以找到工作。

算法常见简写

题目

Leetcode

206. 反转链表

92. 反转链表 II

25. K 个一组翻转链表

题单

[kuangbin带你飞]专题六 最小生成树

最小生成树

简介

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

prime

1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；

2. 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；

3. 递归下列操作，直到Vnew = V：

   1. 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
   2. 将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4. 输出：使用集合Vnew和Enew来描述所得到的最小生成树。

代码

题解

参考资料

最小生成树-Prim算法和Kruskal算法 - 博客园-华山大师兄

只做出A、L就只写这两吧（雾

因一段时间未用虚拟机，打开后发现崩了QAQ，故重新配置了一下，写个文档节约下次时间。

安装VMware17

bilibili找的盗版（雾

安装Ubuntu的ISO

在阿里云或者其他大学镜像安装对应，我下载的版本是：ubuntu-20.04.6-live-server-amd64

安装linux 配置

参考链接

题目

• ACWing 836
• ACWing 837

题目

AcWing 835

题目

AcWing 840

题目

AcWing 841

题单

[kuangbin带你飞]专题五 并查集

1. POJ 2236 Wireless Network
2. POJ 1611 The Suspects
3. HDU 1213 How Many Tables
4. HDU 3038 How Many Answers Are Wrong
5. POJ 1182 食物链
6. POJ 1417 True Liars
7. POJ 1456 Supermarket
8. POJ 1733 Parity game
9. POJ 1984 Navigation Nightmare
10. POJ 2492 A Bug’s Life
11. POJ 2912 Rochambeau
12. ZOJ 3261 Connections in Galaxy War
13. HDU 1272 小希的迷宫
14. POJ 1308 Is It A Tree?

并查集

题目

AcWing 831

单调栈

AcWing 830

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

const int N = 100010;

int stk[N], tt;

void init(){
	tt = 0;
}

void push(int x){
	stk[ ++ tt] = x;
}

void pop(int x){
	tt -- ;
}

bool empty(){
	if (tt > 0)
		return 0;
	else 
		return 1;	
}

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const int N = 100010;

int q[N], hh, tt = -1;

void push(int x){
	q[++ tt] = x;
}

void pop(){
	hh ++;
}

bool empty(){
	if(hh <= tt)
		return 0;
	else
		return 1;
}

单链表

题目

AcWing 826

题目

• ACWing 93

题目

AcWing 94

题目

• ACWing 92

The Missing Semester of Your CS Education 计算机教育中缺失的一课

计算机导论的补充，介绍了工作中常用的几个工具，Shell，Git，Vim等，适合初学者了解。

课程链接

题目：

• HDU 4699

• ACWing 128(译)

环境搭建

安装

1

pip install django

当我们做一件事的时候，我们会发现，几乎只要时间足够充裕，几乎所有的事情都能够做的很好。然而，现实并不会给我们那么多的机会。

我们所做的一切都是有限的，我们的时间是有限的，我们的人力是有限的，我们的精力是有限的、所调动的资源、所能汲取到的智慧等等都是有限的，那些近乎无限的条件往往是不存在的，所以我们必须认识到这一点，我们生活在一个有限度的世界里，而衡量我们有没有成就的标准，就是我们能否在有限的时间里，完成一项工作。

就拿高中生举个例子，学生与老师在学习上最大的不同在于，老师可以用二三十年的时间，不断深入研究学习高中的知识体系和教育，单纯以教学质量来考量，这是一个近乎理想的模型，而学生却不一样，学生只能在2-3（4）年的时间内完成整个规则的学习和应用，衡量学生是否成功的，就是他们是否在最后的教育成果上有个结果。

质数

试除法-判定 O(sqrt(n))

1
2
3
4
5
6
7
8

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ ) // i * i可能会爆int，使用等价写法
        if (x % i == 0)
            return false;
    return true;
}

试除法-分解质因数 O(log n) - O(sqrt(n))

1
2
3
4
5
6
7
8
9
10
11
12

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

朴素筛法求素数

1
2
3
4
5
6
7
8
9
10
11
12
13

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法求素数

介绍参考文末引用文章

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i; //记录素数
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

试除法求约数

1
2
3
4
5
6
7
8
9
10
11
12

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

求欧拉函数

欧拉函数是求小于等于n的数中与n互质的数的数目

1
2
3
4
5
6
7
8
9
10
11
12
13

int phi(int x) // phi 是欧拉函数/fa/读音
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

筛法求欧拉函数

法一

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

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉

void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

法二

来自博客园

需要用到如下性质

p为质数

1. $phi(p)=p-1$ 因为质数 p 除了 1 以外的因数只有 p，故 1 至 p 的整数只有 p 与 p 不互质

2. 如果i mod p = 0, 那么 $phi(i * p)=phi(i) * p$

3. 若i mod p ≠0, 那么 $phi( i * p )=phi(i) * ( p-1 )$

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

#include<cstdio>
using namespace std;
const int N = 1e6+10 ;
int phi[N], prime[N];
int tot;//tot计数，表示prime[N]中有多少质数
void Euler(){
    phi[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!phi[i]){
            phi[i] = i-1;
            prime[tot ++] = i;
        }
        for(int j = 0; j < tot && 1ll*i*prime[j] < N; j ++){
            if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j]-1);
            else{
                phi[i * prime[j] ] = phi[i] * prime[j];
                break;
            }
        }
    }
}

int main(){
    Euler();
}

​

快速幂

原理：$A^{n}=(A^{n/2})^2$

• 如果是偶数幂，计算平方根次幂

• 如果是奇数幂，计算$n - 1$次幂

递归实现（伪代码）

1
2
3
4
5
6

int binpow(int a,int n){
	if n==0 return 1; 
    if n是奇数 reutrn binpow(a,n-1);
       n是偶数 return binpow(a,n/2)*binpow(a,n/2);
       // 用 t 储存 binpow(a,n/2)，return t*t;
}

利用十进制转二进制的原理，可以进行非递归运算

非递归优化（C++）（位运算）

1
2
3
4
5
6
7
8
9
10
11
12

int binpow(int a,int n){
	int res = 1;
	while(n){
		/*如果n末位为1，把对应幂乘进去*/
		if (n & 1) 
			res *=a;
		/*计算位对应的幂*/
		a*=a;
 		n>>=1;
	}
	return res;
}

GCD 最大共因子

1
2

方法1 gcd(a,b)=gcd(b,a mod b) if b == 0 return
方法2 gcd(a,b)=gcd(b,a - b)

可扩展至 gcd(a,b,c,…,n)

参考

1. AcWing
2. 素数筛 - 知乎Pecco用户

文章首次写于：2023-04-19

更新日志：

• 20230419：编写了字符串-C、字符串-C++的输入输出

• 20230916：添加了< String >库、< cctype >库、字符串流 < sstream >库

包括二分、前缀和、差分、双指针

目前还在学习阶段，此贴无参考价值（2023 06 03）

参考资料

[1].最小生成树Kruskal和Prim算法动画演示

经典ICG博弈算法(Impartial Combinatorial Games 公平组合游戏)

两个性质

1. 最优子结构：问题的最优解由其子问题的最优解组合而成；且子问题可独立求解；
2. 重叠子问题：子问题的算法相同。

步骤

1. 问题结构分析（数学语言描述）；

2. 递推关系建立；

3. 自底向上计算，确立计算顺序；

4. 最优方案追踪（记录数组回溯）

   阅读全文 »

BFS+三维，一直WA找不到问题，后来发现是没有初始化（菜

N皇后（八皇后）问题、棋盘问题

递归DFS解法

两种图，从外文摘抄的，后续有时间了反应一下

搜索基础

包括：

常用的STL库接口（vector,deque,list,stack,queue,priority_queue,ste,map）

string的用法