知识背景

如何将自己的文件分享给其他人？

直链

实现

把该文件放在自己的服务器当中，其他人去对应网址下载软件。

举例

音乐软件缓存歌曲，小说网站下载小说，应用官网下载软件

缺点

1. 所有人都去一个服务器下载，抢占网络带宽，导致每个人下载速度很慢
2. 十分受分享方、服务器的影响，如果分享方或服务器受到影响就无法正常分享文件

BT

优化

不是全都从服务器下载，而是从已下载的人手中获取相对应的文件。

再优化方案，可以每个人都只下载某一部分文件，然后互相交换获取各自所需要的部分。（即p2p）

实现

制作一个种子文件，记录文件信息、分块大小，以及tracker服务器信息（用于获取谁有下载过该文件）。

缺点

1. 还是无法摆脱服务器
2. BT的资源分享上传全凭自愿，有些下载了某个文件的人不愿意将他的下载部分贡献出来

磁力

优化与实现

摆脱了服务器的限制。

让每个人都成为tracker服务器。在寻找“谁有下载过该文件”的信息时，会先进入到一个DHT网络，然后在这个网络里寻找tracker。（类似树上DFS）

举例

迅雷

PT

实现

将使用者限制在一个小圈子中，强制每个人只有上传了资源才能进行下载。上传数据量和下载数据量实现对等。

并查集的理解

作为一种数据结构，其核心的是修改与查询，并查集实现的是1.将两组的内容合并以及2.查询两个元素是否在同一组内。

并查集的结构往往是以树的形式呈现，所谓的同一组就是是否在同一棵树下，将两组的内容合并就是将一颗的根节点嫁接到另一根树的根节点下面，查询两个元素是否在同一组内就是看两个结点是否在同一棵树下。

lambda表达式的理解

lambda表达式的具体定义可以去网上找，我对它的理解就是将一个函数以更简洁的方式，以表达式的形式内嵌在某个函数中。

lambda表达式的应用场景

lambda表达式最常用的是在sort函数中，把cmp函数以lambda表达式直接写在内部，代码如下:

1
2
3

sort(a.begin(),a.end(),[&](int x,int y){//此排序采用降序排序
   return x>y; 
});

等价于

1
2
3
4

bool cmp(int x,int y){
    return x>y;
}
sort(a.begin(),a.end(),cmp);

题意

给定一串字符串，求其中有多少长度>=3子串，且该子串中某个字符只出现一次。

思路

最终答案的求取可以通过遍历以i位置为所要求的只出现一次的字符所对应的子串数量来求取。

然后显然我们不可能直接对于每个字符c，都暴力的去找左边有多少个相邻的连续的连续的字符与c不同，以及右边有多少个相邻的连续的连续的字符与c不同。于是，我们需要通过预处理，来记录每个字符左右两边分别有多少个相邻的、连续的、与此字符不同的字符，最终的答案也可以理解为左边挑，右边取，然后相乘即可。假设左边的个数为l，右边的个数为r。那么对于该字符，它的贡献为:

由于还有一个限制是长度>=3，所以对某一边没有符合要求的字符时，需要另一边减去只取一个字符的情况，即：

BFS

BFS介绍

BFS，即宽度优先搜索，经常用于图上遍历等。相比于dfs,bfs是横向的搜索，是一层一层找的。

BFS通过队列进行依次处理，对于每个结点的子节点，将它通过排队的形式排在这一层的后面而非直接遍历，对于一颗BFS树，它的BFS序便是一层一层的向下拓展。

同时BFS由于是层层遍历，先访问到的一定是距离初始点最短的。

DFS

DFS介绍

DFS，即深度优先搜索，经常用于暴力以及图上遍历等。相比于bfs,dfs是纵向的搜索，是一次性找到底的。从根找到底，然后退回来换条路继续走到底，直到走完。

DFS可以理解为是递归+回溯。对于一棵DFS树，其搜索的方式是从根结点开始，沿着一条边一直走到底，层层递归，每次进入一个子节点就可以理解为一个新的以此子节点为根的DFS树，称之为递归。当访问到叶子结点时，又需要将叶子结点的信息返回并总结到该叶子节点的父亲节点，称之为回溯。

DFS大部分分为树上DFS与图上DFS，但其实两者是相通的，图上DFS可以将上下左右四个方向的遍历结果转化为该位置的四个儿子结点，此时还需要一个vis数组用来记录该儿子结点是否在别的分支出现过，尽管从一个点到另一个点会有多条路径，但如果不是要求最短路径的情况下，往往只需要记录一次即可。

题意

给定一张二维图，图上有两个连通块，求使得两个连通块相连的最短路径。

思路

由于无法区分两个连通块，所以通过dfs对两个连通块中的元素分别赋值0/1，然后对于两个连通块中的所有点分别求曼哈顿距离-1即可。（曼哈顿距离：水平距离+竖直距离）

前言

由于前缀和和差分一个加一个减，两个在写法上差距不大而且具有一定共同点，所以放在一块进行描述。

前缀和

前缀和介绍

前缀和顾名思义，就是一段数列前面某一段连续数列的和。

他经常用于预处理区间和的信息，通过预处理前缀和，我们可以快速的得到某段连续数列的和是多少。

当我们需要求取的区间和时，我们可以用来获取，经常会有人将减号后面写成，但是我们需要保留的和，需要减去的重复部分应该是之前的部分

题意

给定，求与范围内与互质的数的个数

思路

​ 这个就是欧拉函数的定义。

首先根据唯一分解定理可得：设，其中为质数，有$\phi(n)=n\prod_{i=1}^s\frac{p_i-1}{p_i}k_iap_in\frac{a}{b} \% mod = ab^{mod-2}$就是逆元。

题意

给定n位字符串，可以对连续的几位都进进行+1/-1的操作，求变成目标串最少的操作次数

思路

这里涉及到一个概念叫做相对距离，对于从起始串到目标串的变化可以转化为0000串到某个串的变化，每一位的相对距离保持不变即可。

这样我们就只需要预处理求出0000串到所有状态的最小操作次数即可，可以通过BFS来求出并记录。