5.1 传输层提供的服务 端口的作用 通过**“端口号”**标识本主机的一个特定进程 每台主机的端口号是相互独立的 TCP、UDP两种协议的端口号也是相互独立的 TCP或UDP协议，通过Socket 套接字={IP地址：端口号}，唯一标识网络中的一台主机上的一个应用进程 端口号的分类 服务器使用的端口号 熟知端口号（0~1023） 登记端口号（1024~49151） 客户端使用的端口号——短暂端口号 49152~65535 功能 实现端到端（进程到进程）的通信 复用和分用 复用（从上到下） 在发送数据的时候，同一台主机上的多个进程可以使用同一个传输协议 分用（从下到上） 在接收数据的时候，传输层可以把数据正确交付到目的进程 差错检测 TCP检测出差错后丢弃数据，并通知发送方重传 UDP检测出错误后直接丢弃，且不通知发送方 向应用层提供两种服务 面向连接的、可靠的端到端传输服务（TCP）——确保数据正确/完整，但开销大、实时性差 无连接的、不可靠的端到端传输服务（UDP ...

4.1 网络层的功能 网路层为传输层提供服务，将传输层的数据封装成**“IP数据报”。网络中的路由器根据IP数据报首部中的源IP地址**、目的IP地址进行“分组转发”。因此，网络层实现了**“主机到主机”**的传输。 数据链路层为网络层提供服务，将网络层的 **IP数据报（分组）**封装成帧，传输给下一个相邻结点。 异构网络互联 异构：每个网络的拓扑结构不同、物理层&链路层的实现不同、主机类型也各不相同 重要的设备：路由器（Router） 注：在TCP/IP文献中，路由器也称为 网关（Gateway） 路由与转发 路由 各个路由之间相互配合，规划IP数据报（分组）的最佳转发路径 注：各个路由器需要运行“路由协议”，最终生成各自的“路由表” 转发 一台路由器，根据自己的“转发表”，将收到的IP数据报从合适的接口转发出去 注：转发表 = 精简版路由表。更精简的数据结构有助于快速检索 拥塞控制 拥塞 原因：网络上出现过量分组、超负荷，引起网络性能下降 现象：网络上的分组增加，但吞吐量反而降低 拥塞控制 ...

物理层任务：实现相邻节点之间比特的传输。 2.1 通信基础 基本概念 信源：信号的来源（数据的发送方） 信宿：信号的”归宿“（数据的接收方） 信号： 信号的通道 信号：数据的载体 数字信号，信号值是离散的 模拟信号，信号值是连续的 每一个信号就是一个码元 ​ 如果一个码元（一个信号），可能有4种状态，那么可以称其为4进制码元。如果有K种，则一个码元可携带 \(\log_{2}{K}\ bit\) 的数据 。波特率也是速率的一种表现方式，其单位为 \(码元/s\) 或 \(波特\) 。 信道的极限容量 带宽：信道允许通过的信号频带范围，单位：Hz 噪声：对信道产生干扰，影响信道的数据传输效率。 奈奎斯特定理：对于一个理想低通信道（没有噪声、带宽有限的信道），极限波特率 = \(2W\) (单位：波特) 香农定理：对于一个有噪声、带宽有限的信道，极限比特率 = \(W \log_2{(1+\frac{S}{N})}\) ，其中 \(\frac{S}{N}\) 为信噪比。 ​ 信噪比作为数值往往很大，可以用 db（分贝）为单位，此时 ...

1.1 计算机网络概述 计算机网络的概念 ​ 计算机网路是一个将众多分散的、自洽的计算机系统，通过通信设备与线路连接起来，有功能完善的软件实现资源共享和信息传递的系统。 ​ 计算机网络(简称 网络)：由若干结点和链接这些结点的链路(link)组成。结点可以是计算机、集线器、交换机、路由器等。 ​ 把两个或多个计算机网络互相连接起来，形成规模更大的计算机网络，也可称“互连网“。 ​ 互联网(因特网)指当前全球最大的、开放的、由众多网络和路由器互连而成的特定计算机网络，它采用了TCP/IP协议族作为通信规则。 注意：家用路由器往往是路由器+交换机+其他功能 计算机网络的组成 ​ 从组成部分看，计算机网络主要由硬件、软件、协议三大部分组成。 ​ 从工作方式看，计算机网络(这里主要指Internet，互联网) 可分为边缘部分和核心部分。边缘部分由互联网上的供用户直接使用的主机组成，用来进行通信和资源共享;核心部分由大量网络和连接这些网络的路由器组成，它为边缘部分提供连通性和交换服务。 ​ 从功能组成上看，计算机网路由通信子网和资源子网组成。 计算机网络的功能 ...

《硅谷之火》部分简述 b { all: unset; font-weight:bold; } 内容太多，目前只做了第一章的简述，对此感兴趣可以看看原书《硅谷之火》 ​ 尽管个人计算机问世于20世纪70年代中期、巨型计算机要回溯到20世纪50年代，我们甚至能够追溯到19世纪末对未来的幻想。 火种 上帝保佑，我真希望计算能用蒸汽运行。 ——查尔斯·巴贝奇 ​ 这是火种。 ​ 诗人拜伦和雪莱注意到科学带来的变化，交流着人工生命与人工思维，雪莱夫人玛丽·雪莱由此创作了《弗兰肯斯坦》，科学怪人这一小说形象令人望而生畏。1833年，查尔斯·巴贝奇谈起利用蒸汽进行计算并真的开始实施，他认为这“分析机”将会让人们从枯燥的脑力劳动中解放出来，而拜伦女儿艾达·拜伦极力支持并提供帮助，由于她做的工作，人们视艾达为世界上第一位程序员(Ada语言的命名因此而生)。巴贝奇关于分析机的3种设计均已失败告终，他设计的差分机虽简单而显雄心，却也仍未实现。1991年，伦敦科学博物馆的一位馆长多伦·斯沃德成功用巴贝奇时代的技术、材料造出了巴贝奇的差分机。事实上，巴贝奇设 ...

.red{ color:red; font-weight:600; //bold为700，normal为400 } .lbold{ font-weight:bold; font-size:24px; //默认16px } .bold{ font-weight: bold; } details { border: 1px solid #ccc; background-color: #f0f8ff; /* 浅蓝，适合白天 */ border-radius: 6px; padding: 0.5em; transition: background-color 0.3s ease, border-color 0.3s ease; } ...

参考资料：动态规划基础 - OI Wiki 目前绝大多数内容摘自OI-Wiki,个人理解重构等后续更新 动态规划初步 ​ 动态规划(Dynamic Programming)，简称DP，它本身不是一种特定的算法，而是一种思想。当状态变动与之前或之后状态有关时，我们往往可以使用方程来描述这种关系。这种方程被称作状态转移方程。 动态规划原理 能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。 最优子结构 具有最优子结构也可能是用适合贪心的方法求解。 注意要确保我们考察了最优解中用到的所有子问题 证明问题最优解的第一个组成部分是做出一个选择; 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解，你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间； 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本省的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题中的解用 ...

线段树 参考: 线段树 - OI Wiki ​ 线段树是一种二叉搜索树、平衡二叉树，对于区间的修改、维护和查询时间复杂度优化为log级别。对区间不断做平分区间，直到划分到只有一个或多个数据的区间，可表示区间的和或者最小最大值。在进行更新区间操作时，通过小区间更新大区间。 ​ 对于下面的内容，我们主要针对于区间加法的线段树(即其节点表示区间之和)。 ​ 局限性： 问题需满足区间加法：对于[L,R]的区间，它的答案可以由[L,M]和[M+1,R]的答案合并求出。 不满足区间的众数、区间最长连续问题、最长不下降问题等。 建树 当我们拥有数组 \(a\) 并且用来区间求和之类的问题时，我们可以这样做： ​ 以堆的方式实现存储(树形数组)，将元素放至树的最下面一层。 由于我们使用树形数组，为了存储下数组 \(a\), 数组 \(tree\) 的长度应当为 \(a\) 的四倍，并且初始节点位置为1。同时，当前区间[s,t]只有一个元素时(即s==t)，意味着当前节点为叶子节点，就要让当前节点 \(tree[p] = a[s]\)。对于其它的情况，我们 ...

快速幂 快速幂，即快速取幂的技巧。 对于在取幂过程中，需要不断取模的过程中（例如费马小定理求模逆元）时，单纯的pow函数已经不再满足我们的需要。我们需要明白pow函数的原理，以方便我们“魔改”pow函数。 定义 快速幂，二进制取幂（Binary Exponentiation),是一个在 \(O(logn)\) 的时间计算 \(a^n\) 的小技巧。 实现 递归形式 按幂的定义而言，\(a^n\) 等于 \(n\) 个 \(a\) 相乘，如果我们按照这样的定义实现算法的话，当 \(n\) 足够大时，资源的开销就很大了。 根据指数乘法，\(a^{b+c}=a^{b}+a^{c}\), 当 \(n\) 为偶数时, \(a^{n}=a^{\frac{n}{2}}·a^{\frac{n}{2}}\), 对于 \(n\) 为奇数的情况, 无非是在此基础上再乘以 \(a\) 罢了。因此，我们很容易就能得到实现快速幂的递归形式。 1234567long long pow(long long a, long long b){ if(b == 0) ret ...