网络模型

• 物理层：物理层处于OSI参考模型的最低层。物理层的主要功能是利用物理传输介质为数据链路层提供物理连接，以透明地传送比特流。
• 数据链路层：数据链路层在物理层提供比特流传输服务的基础上，在通信实体之间建立数据链路连接，传送以帧为单位的数据，通过差错控制、流量控制方法，变有差错的物理线路为无差错的数据链路。
• 网络层：网络层主要任务是通过执行路由选择算法，为报文分组通过通信子网选择最适当的路径。它是OSI参考模型七层中最复杂的一层。
• 传输层：传输层是向用户提供可靠的端到端服务，透明地传送报文。
• 会话层：会话层的主要目的是组织同步的两个会话用户之间的对话，并管理数据的交换。
• 表示层：表示层主要用于处理两个通信系统间信息交换的表示方式，它包括数据格式变换、数据加密与解密、数据压缩与恢复等功能。
• 应用层：应用层是OSI参考模型的最高层。应用层不仅要提供应用进程所需要信息交换和远程操作，而且还要作为应用进程的用户代理，完成一些为进行语义上有意义的信息交换所必须的功能。

TCP首部

• 源端口和目的端口，各2字节
• 序号，4字节，面向字节流传输，标识当前报文段发送数据的起始编号，接受方根据起始编号和数据大小，就可以推算出下一个应该接受报文的起始编号
• 确认号，4字节，下一个希望收到报文的起始编号，即表示：N之前编号的数据已经成功收到
• 数据偏移，4字节，数据部分离报文段起始位置有多远
• 保留位，6字节，暂时没用，留着以后使用
• URG：说明有紧急数据，应尽快发送
• ACK：建立连接后所有ACK报文必须置为1
• PSH：。。。
• RST：出现了严重错误，必须重新建立连接
• SYN：请求连接
• FIN：释放连接
• 窗口：发送本报文段的一方的接受窗口
• 检验和：检验报文的首部和数据是否发送改变
• MSS：规定的最大报文长度

题意

在数轴上找到一个点，使得到其余 $n$ 个点距离之和最小。$(n \in [1, 1e5])$

Solution

考虑绝对值不等式：

并发和并行

并发：宏观上两个程序在同时运行，实际上是交织运行的，单个周期只运行了一个指令，用于提高效率。
并行：物理意义上的同时运行，如多核cpu，运行在不同的核上，互不影响。

进程和线程的概念，区别，使用场景

进程：资源分配的基本单位，实现了操作系统的并发。
线程：线程是进程的子任务，是CPU调度的基本单位，不拥有资源，但可以使用进程所属的资源。每个进程都有一个主线程，实际上是主线程来执行main函数中的代码。

进程在创建，撤销，切换时的开销都显著大于线程，系统要为之分配，回收，切换资源。

一个线程只属于一个进程，进程间不会相互影响，一个线程挂掉将影响整个进程挂掉。

线程并不是越多越好，每个线程都需要一个独立的堆栈空间，线程之间的切换需要保存很多中间状态，耗费程序运行时间。多线程开销远远小于多进程。

进程在同一时间只能干一件事，进程在执行过程中如果阻塞，整个进程就会挂起，然后其中有些工作并不依赖阻塞的资源，却还是卡在那里。因此引入线程，减少程序在并发时付出的时空开销。

题意

给定一个已排序的正整数数组 $nums$，和一个正整数 $n$ 。从 $[1, n]$ 区间内选取任意个数字补充到 $nums$ 中，使得 $[1, n]$ 区间内的任何数字都可以用 $nums$ 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

Soluiton

容易证明，对于正整数 $x$，如果区间 $[1,x−1]$ 内的所有数字都已经被覆盖，且 $x$ 在数组中，则区间 $[1,2x−1]$ 内的所有数字也都被覆盖。

题意

给定一个仅包含 $0$ 和 $1$ 、大小为 $n * m$ 的二维二进制矩阵，找出只包含 $1$ 的最大矩形，并返回其面积。$(n, m \in [1, 200])$

思路

有一个子问题，求柱状图最大矩形。预先求出 $1-i$ 层的 $h[i]$ 然后利用套用子问题的模板即可，复杂度 $O(n * m)$.

题意

现在有 $n$ 个音符和 $m$ 对共鸣关系，编号为 $1-n$，每个音符自己有一个奏响时的优美程度，共鸣关系 $(x,y,z)$ 表示音符 $x$ 和 $y$ 同时奏响的额外优美程度是 $z$，同时不奏响则为 $-z$，其他情况为 $0$，求最大优美程度。$(n,m \in [1,1e5])$

思路

对于一对共鸣关系而言，在不选的情况下收益为 $-z$，则选择一个的话，收益为 $-z + z = 0$，都选择的话为 $-z + 2z = z$。因此可以预先把每对关系的两个数都加上 $z$，刚开始我们是不选任何有联系的音符的，因此初值为 $-z$，那么选择一个数就会加上 $z$，选择两个就会加上 $2z$，满足了之前所讨论的关系。答案初始化为所有关系都不选的情况，即 $-sum(z)$，然后只要贪心的选择对答案有正贡献的值就行了。

题意

从 $n$ 个数中任选 $k$ 个数，取得这 $k$ 个数中最大的一个数，求每个数被取得的概率。$(n, k \in [1, 2e5])$

Solution

将数组排序后，枚举每个数被作为最大值的可能性，当第 $i$ 个数作为最大值时，其它 $k - 1$ 个一定从前 $i - 1$ 个里面选，即方案数为 $C(i - 1, k - 1)$，将其除以总方案数 $C(n, k)$ 即为被取得概率。

GCC编译器

GCC 编译器支持编译 Go、Objective-C，Objective-C++，Fortran，Ada，D 和 BRIG（HSAIL）等程序。

实际使用中，使用 gcc 指令编译 C 代码，使用 g++ 指令编译 C++ 代码。

编译过程

例如 g++ test.cpp -o test 可拆解为以下步骤：

题目

给定一个整数数组 $a$，返回区间和在 $[lower, upper]$ 之间的个数，包含 $lower$ 和 $upper$。
区间和 $S(i, j)$ 表示在 $a$ 中，位置从 $i$ 到 $j$ 的元素之和，包含 $i$ 和 $j$ $(i ≤ j)$。

Solution

内存管理

内存管理详解

内存分配方式

分配方式简介

在C++中，内存分为5个区：

1. 栈：执行函数时，函数内部局部变量存储单元在栈上创建，结束时自动释放。效率很高，但存储容量有限。
2. 堆：由 new 分配的内存块，编译器不会自动释放，需要应用程序对应的 delete 进行释放。如果没有释放，则程序运行结束后会由操作系统自动回收。
3. 自由存储区：由 malloc 等分配的内存块，类似堆，由 free 结束自己的生命。
4. 全局/静态存储区：存储全局变量和静态变量。
5. 常量存储区：存放常量，不允许修改。