草稿纸

时间复杂度

$$\begin{array}{r}n\times (m-1)\\ O(nm)\to O(n^2)\\ 1+2+3+...+n\le \frac{n(n+1)}{2}\to O(n^2)\\ m-2+1=m-1\\ \frac{n}{j}\\ \frac{n}{2}+\frac{n}{3}+...=n(1+\frac{1}{2}+...\frac{1}{n})\approx O(nlog(N))\end{array}$$

分析例子：PTA | 程序设计类实验辅助教学平台 (pintia.cn)

i <= n / i//避免溢出，等价i*i<=n，即i<=sqrt(n)

对这题时间复杂度分析

朴素算法 每次从$p^2$开始筛，筛$2\le p\le \sqrt{n}$

从数学到泛性编程

• [ ] 桶排序
• [ ] 基数排序&后缀数组
• [ ] 计数排序

P1009说反话

P1070 P1055 P1080 比较函数+严格弱序 P1035 归并/插入排序 stable_sort STL稳定排序 归并排序： 逆序对（评估数组排序情况），求元素右侧第一个严格大于他的元素 贪心

1. P1023
2. 牛客round25 B、C 浮点数消去/舍入误差，注意计算顺序 hydro.ac，求一元二次方程

等价变换，如果太近会消去误差

牛客bilabila 64221

引言

将近三周才把23年年末内容整理完，这周量太大了，整个笔记快三万字了。 蓝桥杯授课部分是广度优先搜索和匈牙利算法两节。

原地算法(PAT-1008)

用于将一个数列向右移动$k$个位置，你只需要：

1. 将整个序列翻转；
2. 将前$mmodk$个数翻转一下；
3. 将之后的数翻转一下。

这里需要用到algorithm库的reverse函数，以vector为例：

#include <iostream>
#include <algorithm>
#include <vector>
int main(){
	vector<int> a = {1,2,3,4};
	reverse(a.begin(),a.end());//从头到尾翻转
	reverse(a.begin(),a.begin()+n)//翻转[0,n]之间的元素
}

掌握原理之后还是挺简单的就不放代码了。

迭代器

迭代器是一种对象，用于对其对应的对象进行迭代访问，指向序列中的某个元素。对于上面的向量a，可以通过链式访问的形式看一下迭代器内部干了什么。可以在编辑器中输入a.begin().看看后面itellisense补全了什么，其实就是对一堆运算符的重载。[[2023.12.22-2023.12.29#运算符重载]] 值得注意的是，迭代器可以解引用，例如*(a.begin())就是1，当然这不是真正在解引用，这个操作等价于a.begin().operator*()实际上调用了这个迭代器对象重载的*运算符。 另外，a.end()代表的是4的后一项位置，不是4。 再深入一点，看一下STL的实现，其实底层还是指针。

operator*() const _GLIBCXX_NOEXCEPT
	{ return *_M_current; }

迭代器可分为输出/输出迭代器，前向/双向迭代器和随机访问迭代器（重载对整数的运算）。对不同类型的对象进行迭代应当使用满足其对象底层实现的数据结构的迭代器。

对迭代器有了初步的了解，就可以逐步理解reverse(a.begin(),a.end())在干什么了。 reverse函数原型要求两个迭代器对象，a.begin()和a.end()就是创建了两个迭代器(iterator)对象然后作为参数传入reverse函数，模板推断类型为iterator，然后就是正常的函数调用。

inline void reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)//_BidirectionalIterator是模板类型名

iterator begin() _GLIBCXX_NOEXCEPT
	{ return iterator(this->_M_impl._M_start); }//调用a.begin()返回一个iterator类型的迭代器

typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
//这个所谓的iterator其实是调用__gnu_cxx::__normal_iterator接口创建一个标准迭代器对象？（不确定了这里）

贪心

贪心算法的思路就是自顶向下（从输入的序列开始做选择再向下划分子问题，而不是动态规划的合并多个相同子问题从而求出一个顶端的大问题），每次在求出子问题之间要进行局部最优的选择（可以根据直觉，或者进行证明）。

活动选择问题

本节详细内容参见算法导论第三版P237-P239的分析与证明（群内PDF在230页），当然那就太复杂了，下面总结一下。

活动选择

有一些活动，给出这些活动的开始时间$s_i$和结束时间$f_i$，要求找到一个最大兼容集合，使得集合内的各个元素在时间线上互不重合。 下面是一组可能的数据：

这是贪心算法的典型使用情况，因为很明显你肯定优先选择一堆活动中结束时间最早的那个活动，因为这样会让这个活动占用的时间线资源最小，避免了使用动态规划的繁杂证明。至于证明，如果您高兴的话可以看P239页（PDF232页）对定理16.1的证明。证明的操作还是用练习赛C题吧。

练习赛第一场/C

C-石子合并_JOU练习赛第一场 (nowcoder.com) 本题要求我们每次选取两堆石子，然后合并这两堆，将其和作为价值加在总价值中（这其实就是贪心算法每次要解决的子问题）。当然凭借直觉我们很容易发现只要每次选择的堆只要包含价值最大的那一堆就行了。 可能会疑惑的是，为什么不要考虑选取的两堆之和呢？假设每次选择的堆为集合$\{max,other\}$，满足$other\le max$，显然每次拿走的都是$other$，所以不管这个$other+max$到底是多少，$other$到最后都会被拿走，那它都被拿走了，显然也只会在总价值中只被加一次，所以这个$other$怎么取没有任何关系，这也会被反映在最后的贪心表达式中。 接下来推导贪心表达式。 每次选都必选$max$，然后每个除了最大值之外的元素都只会被选一次，一共选$n-1$轮，非常直观的可以推到公式：

$$\begin{array}{rl}Value& =\sum _{i=0}^n{a}_i+a_{max}(n-1)-a_{max}\\ & =\sum _{i=0}^n{a}_i+a_{max}(n-2)\end{array}$$

注意范围

$0\le a_i\le {10}^9$，开int的话求$sum$会溢出，开long long就能过了。

贪心策略正确性证明

证明使用了反证法，因为我们的贪心策略是每次选择最大的那一堆，那是否可以不选择带$max$的堆呢？ 给出一堆$\{max-2,max-1,max\}$石子，如果我们认为$\{max-2,max-1\}$为局部最优解，显然存在$\{max-1,max\}$比这个局部最优解更好，所以贪心策略选取的堆确实是局部最优解。

最优子结构性质证明

使用贪心和动态规划时，往往还要证明问题具有最优子结构性质，即问题的最优解是局部最优解的组合。 （极其不严谨的非数学证明） 因为这道题选到最后剩下的必然是最大的元素，所以每次我们选最的元素集合是确定的，每次选的对结果没有影响，因此如果我们将每次选的两堆包括最大的元素认为是局部最优解是没有问题的。 贪心策略正确性确保了我们的选取策略可以保证每次选的为局部最优，问题存在最优子结构性质则保证我们认为的最优情况之和为问题的最优解，两层关系保证了贪心算法的正确性。

#include <iostream>
#include <vector>
#define int long long
using namespace std;
signed main(int argc, char const *argv[])//注意signed只能用g++编译，clang++不支持
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int &x : a){
		cin >> x;
	}
	int maax = a[0];
	for(int i = 0;i < n;++i)
	{
		maax = max(maax,a[i]);
	}
	int sum = 0;
	for(int &x : a) sum += x;
	cout << sum + maax*(n-2) << endl;
	return 0;
}

广度优先搜索

先明确一些基础知识。

栈和队列

本节内容位于算法导论第三版第十章第一节（P129），群内PDF在127页。

栈(stack)

栈是一种后进先出的数据结构，最新插入的元素被称为栈顶，将元素放入栈的操作称为压入(push)，删除栈顶的元素的操作被称为弹出(pop)。当一个栈中无任何元素，称这个栈为空(empty)。 对栈的不当操作有时候会引起段错误，比如对一个空栈进行弹出操作，称为栈上溢(underflow)，如果栈的元素过多，则称栈下溢(overflow)，或者叫爆栈，此时应当将数据往堆上转移，开启O3优化等等减少栈空间使用。

其实看算法导论有时候会很好奇，为什么栈和队列要放在一起，一方面是因为这是两个最简单的数据结构，另外一方面对于图的两种搜索模方式来说，深搜其实是栈的思路，先把元素一直到最深压栈，叶子节点是最后放进去的，也是最先出来的。回溯层的节点被全部弹出后自然会回到上一节点，然后向右侧子节点回溯（画个图自己想想），所以深搜用递归非常容易实现，参见[[通过C题重新深入讨论递归#递归中的局部变量与函数栈帧]]，因为递归本身就是基于栈实现的。因为课程也从深搜入手，如果在深搜这块把搜索和数据结构的插入和弹出搞明白，对广搜的理解会更加简单。很不幸我没有这样做，又鲜有人强调递归与栈的关系，而是从广搜这里绕回了深搜，走了不少弯路。在下文[[2023.12.29#为什么要用队列]]中我们来详细探讨这个问题。 C++提供了栈(stack)的STL，这类用于存放某数据结构的对象称之为容器，栈的操作提供了以下方法：

stack<int> a;//这是一个对象，所以后面都是用.操作的
a.push();//压入
a.pop();//弹出
a.empty();//判断是否为空栈
a.top();//返回栈顶的值（最后一个被压入栈的）
a.size();//返回栈的大小

队列(queue)

与栈相反，队列是一种先进先出的数据结构，因为它两边开口。插入元素操作称为入队，删除则为出队，元素入队的位置为队列的队尾，最前面的地方则为队头。

STL中队列的方法如下，当然STL提供的只是一个普通队列的实现，循环队列还需要自己实现。

queue<int> a;
a.push();
a.pop();
a.size();
a.empty();
a.front();//返回队头元素
a.back();//返回队尾元素

这样的话在下面的课程中我们就不用手写队列实现了，所以队列的队头和队尾指针就不需要自己考虑了。

搜索顺序

数据结构——1分钟学会广度优先遍历，这个视频直观地讲解了广度优先的遍历规则及节点间层次划分方法，这里的广度优先搜索树的生成是生成全排列的特殊图，对于更一般的有向图和无向图同样可以使用。

为什么要用队列

看一下这个树是怎么通过广度优先搜索完成遍历的：

1. 选择根节点，这里选择的是0，根节点入队（记根节点为第0层）；
2. 访问根节点的下一层节点：弹出根节点，将弹出的节点保存下来，将其层数+1，访问第1层的节点，并且将其入队；
3. 分别访问1，2下的节点（注意这是两个过程），因为队列中1，2节点是被最先存放进来的，所以每次弹出并保存的节点其实就是接下来要去访问的元素的父节点。（弹出并保存1，生成3，4节点，接着弹出并保存2，生成5，6节点），这个过程结束后，上一层的所有元素都从队列中被弹出，只剩下本层的元素，这就是队列用于广搜的精妙之处。
4. 每次保存父节点后判断是否是叶子节点，如果是的话就直接输出它的解（或者是其他各种操作），由于到最后一层还是从左往右输出各节点的解，所以和深搜的输出结果是相同的，虽然搜索方式不同。 总结一下，广搜巧妙的利用了队列的先进先出特性，让上一层的各个父节点位于队头位置，然后依次弹出并生成下一层的搜索树，顺便清除上一层的结果。

结果存储

广搜存储的节点可以用一个Node对象来表示：

struct Node{
	int no;		   // 结点编号
	int i;		   // 行编号(即深度，从0开始)
	int x[N];	   // 部分解
	bool alloc[N]; // alloc[i]=true表示列i已经选择，为剪枝提供依据
};

对节点的数据操作如下：

memcpy(e1.x, e.x, sizeof(e.x));
memcpy(e1.alloc, e.alloc, sizeof(e.alloc));//继承父节点e的属性（解和选择状态）
e1.alloc[j] = true;//标记当前选择的数
e1.x[e1.i] = j;//写入解
e1.no = total++;//增加节点编号

剪枝

深搜剪枝是在每次向下扩展深度的时候剪枝，保证该节点不向下递归调用增加搜索深度，广搜的剪枝就更简单了：父节点不入队下一层自然不会扩展这个节点了，只要在生成本层节点的时候跳过需要被剪枝的节点即可。

if(e.alloc[j]) continue;//如果该列已经在之前的解中，停止扩展子节点（不入队）

完整代码

解决一个1，2，3，4的全排列问题，用了queue容器简化队列操作：

#include <iostream>
#include <cstring>
#include <queue>
#define M 2000
#define N 10
using namespace std;

struct NodeType // 队列结点类型
{
	int no;		   // 结点编号
	int i;		   // 行编号
	int x[N];	   // 部分解
	bool alloc[N]; // alloc[i]=true表示列i已经选择
};
int n = 4, total, cnt;
queue<NodeType> qu;//创建队列容器
void bfs(){
    int j;//初始化根节点
	NodeType e, e1;//e：整棵树的根节点，e1:扩展结点
	memset(e.x, 0, sizeof(e.x));		 // 初始化根结点的x
	memset(e.alloc, 0, sizeof(e.alloc)); // 初始化根结点的alloc
	e.i = 0;							 // 结点层次
	e.no = total++;						 // 根结点，指定人员为0
    qu.push(e);
    while(qu.empty() == false){
        e = qu.front();//获取队头节点
        qu.pop();//弹出它的父节点！用队列的原因！
        if(e.i == n){//搜索到最深后输出解
            for(j = 1;j<=n;j++){
                cout << e.x[j];
            }
            cout << endl;
            cnt++;
        }
        e1.i = e.i + 1;//生成当前处理的父节点的下一层节点（不是全部的下一层节点！）
        for(j = 1;j<=n;j++){
            if(e.alloc[j]) continue;
            memcpy(e1.x, e.x, sizeof(e.x));
            memcpy(e1.alloc, e.alloc, sizeof(e.alloc));
            e1.alloc[j] = true;
            e1.x[e1.i] = j;
            e1.no = total++;
            if(e.i < n){
                qu.push(e1);//子节点入队
            }
        }
    }
}
int main(int argc, char const *argv[])
{
    bfs();
    cout << cnt;
    return 0;
}

以上只是帮助理解，理解了不等于会，还是要多练。

金陵十三钗

题意

有一个$N\times N$的矩阵，每一行表示一个人，每一列表示其与学生的相似度，要求求出相似度最大的配对方案。

$$\left[\begin{array}{cccc}97& 91& 68& 14\\ 8& 33& 27& 92\\ 36& 32& 98& 53\\ 73& 7& 17& 82\end{array}\right]$$

最优解为$91+92+98+73=354$ 理解了广搜生成全排列这道题就非常简单了，只要把全排列生成的数映射到对应行数的列数上即可。例如$1234$就代表选择第一行的第一列，第二行的第二列...以此类推。对选择的相似度求和与max比较，最后输出max即可。

实现

为了保证全局变量max不与std命名空间的max函数名冲突，使用了::明确其作用域，详见[[2023.12.22-2023.12.29#突然发现的小问题]]

#include <iostream>
#include <cstring>
#include <queue>
#define M 2000
#define N 10
using namespace std;
int num[13][13];
struct NodeType // 队列结点类型
{
	int no;		   // 结点编号
	int i;		   // 行编号
	int x[N];	   // 部分解
	bool alloc[N]; // alloc[i]=true表示列i已经选择
};
int n = 4, total, cnt,max;
queue<NodeType> qu;
void bfs(){
    int j;
	NodeType e, e1;//e：整棵树的根节点，e1:扩展结点
	memset(e.x, 0, sizeof(e.x));		 // 初始化根结点的x
	memset(e.alloc, 0, sizeof(e.alloc)); // 初始化根结点的alloc
	e.i = 0;							 // 结点层次
	e.no = total++;						 // 根结点，指定人员为0
    qu.push(e);
    while(qu.empty() == false){
        e = qu.front();
        qu.pop();//弹出它的父节点！用队列的原因！
        if(e.i == n){
            int sum = 0;
            for(j = 1;j<=n;j++){
                cout << num[j-1][e.x[j]-1] << " ";
                sum += num[j-1][e.x[j]-1];//计算相似度和
            }
            cout << sum << endl;
            if (sum > ::max){
                ::max = sum;
            }
            cnt++;
        }

        e1.i = e.i + 1;//生成下一层节点
        for(j = 1;j<=n;j++){
            if(e.alloc[j]) continue;
            memcpy(e1.x, e.x, sizeof(e.x));
            memcpy(e1.alloc, e.alloc, sizeof(e.alloc));
            e1.alloc[j] = true;
            e1.x[e1.i] = j;
            e1.no = total++;
            if(e.i < n){
                qu.push(e1);
            }
        }

    }
}
int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    for(int i = 0;i<4;i++){
        for(int j = 0;j<4;j++){
            cin >> num[i][j];
        }
    }
    bfs();
    cout << ::max << endl;
    return 0;
}

分支限界

一般广度优先其实我们已经枚举出了解空间中的所有解，然后再从里面选择出一个最优解，而分支限界只要求我们找出解空间中的一个解（或最优解）。 分支限界可以在广度优先或者最小耗费优先的基础上实现。

基础知识

大根堆

大根堆要求父节点的值大于等于其子节点，例如下图：

STL优先队列模板(priority_queue)

优先队列和队列的区别就是优先队列每次最先出队的是要求的属性最大（或最小）的元素。STL的优先队列其实是基于堆的一个抽象，大的先出队就是大根堆，小的先出队就是小根堆，其中涉及到堆排序的相关内容可以看这个视频：从堆的定义到优先队列、堆排序，这里不再啰嗦。 要实现对以某个对象属性作为优先出队依据，需要重载使用优先队列模板的类的 < 运算符，详见[[2023.12.22-2023.12.29#运算符重载]]

bool operator<(const NodeType &s) const{
	return this->lb < s.lb;
}

友元函数实现：

friend bool operator<(const item& a, const item& b){
 if(a.v != b.v){
   return a.v < b.v;
}
return a.cur < b.cur;
}```

分支限界实现

分支限界相较于盲目的广度优先搜索方式，引入了启发式搜索的思想，即在每次生成一个节点之后，计算一个上界期望值：

$$E_k=E_{k-1}+\sum _{k=layer}^n{k}_{max}$$

其实就是在父节点的代价基础上增加下面几层每层的最大值，以计算出当前搜索路径往下的最大期望值$E$，这个期望值可以帮助我们选择向下搜索并发现最优可能得到最大值的路径，这个期望值会受到剪枝函数影响，如果最大期望路径被剪枝，那么只能退而求其次，选择未被选择的节点继续向下搜索，得到相较这个最大期望值更小的一个最优期望。 理解基本原理之后，再详细说明这个$E$有什么用，优先队列会选择队列中$E$最大的节点出队，进而扩展其子节点，如果子节点扩展过程中由于剪枝原因导致当前搜索路径下的$E$小于另一条路径，那么放弃对当前路径的扩展，转而扩展另外一条路径。 直到某条路径终于扩展到最深层，计算当前路径代价之和，作为当前搜索路径最大值，记为$E_{max}$，在接下来的过程中，如果某个节点入队之前发现其接下来的$E\le E_{max}$，直接中断该路径搜索，剪枝即可。 在自己画搜索树的过程中（一定要画！），如果发现节点编号对不上的情况，请你注意：

1. 被剪枝条件剪枝的节点不算编号；
2. 本例中节点是从1开始计数的（当然你把total初始化为0让它从开始也行，不过我的图已经从1开始画了，为了方便下面还是从1开始）；
3. 编号顺序是搜索节点顺序决定的，不再是上面广搜的生成顺序。

如果要进一步提升性能，还可以计算下界期望值，即考虑剪枝情况下的期望值，说是下界，其实是加了限制条件的最优值，对于搜索结果来说，他求的依旧是当前路径的最大值，如果下界都小于$E_{max}$，该节点下的所有路径都不必扩展，可以达到进一步剪枝的效果，不过耗时减少的不是很多。

代码实现

相较课堂上的内容，观察调试输出结果，其实会发现存在一些父节点期望值已经小于Minb但因为通过期望剪枝操作是基于对子节点的搜索完成的，所以可以直接在父节点这里中止搜索，减少判断节点数，提升性能，所以加了一个新的剪枝条件来优化。

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f // 定义∞
#define MAXN 21
// 问题表示
int n = 4;
int c[MAXN][MAXN];// 代价
int Minb;		  // 最小下界		
int bestx[MAXN];  // 最优解
int maxcost = 0;  // 最大值
struct NodeType	  //队列结点类型
{
	int no;									// 结点编号
	int i;									// 层次编号
	int x[MAXN];							// 部分解
	bool alloc[MAXN];						// alloc[i]=true表示列i已经选择
	int cost;								// 当前代价
	int lb;									// 上界（限界函数值）
	bool operator<(const NodeType &s) const // 重载<关系函数
	{
		return this->lb < s.lb;
	}
};
void dispnode(NodeType node) // 显示节点信息，调试可用
{
	printf("node:%d,e.i=%d,e.cost=%d,e.lb=%d, x: [", node.no, node.i, node.cost, node.lb);
	for (int i = 1; i <= n; i++)
		printf(" %d ", node.x[i]);
	printf("]\n");
}
void bound(NodeType &e) // 限界函数，求结点e的限界值，即上文所谓的上界期望
{
	int maxsum = 0;
	for (int i1 = e.i + 1; i1 <= n; i1++) // 求c[e.i+1..n]行中最大元素和
	{
		int maxc = 0;
		for (int j1 = 1; j1 <= n; j1++)
			if (c[i1][j1] > maxc)
				maxc = c[i1][j1];
		maxsum += maxc; // 加每一行的最大值
	}
	e.lb = e.cost + maxsum; //这里是对对象的引用直接操作，不必再返回
}

int total = 1; // 结点个数累计
void bfs()
{
	int j;
	NodeType e, e1;
	priority_queue<NodeType> qu;		 // STL优先队列模板
	memset(e.x, 0, sizeof(e.x));		 // 初始化根结点的x
	memset(e.alloc, 0, sizeof(e.alloc)); // 初始化根结点的alloc
	e.i = 0;							 // 根结点，指定人员为0
	e.cost = 0;
	bound(e); // 求根结点的lb(上界)
	e.no = total++;
	qu.push(e); // 根结点进队列
	// Minb=getminb();
	while (qu.empty() == false)
	{
		e = qu.top();
		qu.pop(); // 出队结点e，当前考虑行e.i
		if (e.lb <= Minb)
		{
			cout << "?????" << endl;
			continue;
		}
		printf("grow:");
		dispnode(e);  // 输出准备扩展的结点
		if (e.i == n) // 达到叶子结点
		{

			if (e.cost > maxcost) // 比较求最优解
			{
				maxcost = e.cost;
				for (j = 1; j <= n; j++)
					bestx[j] = e.x[j];

				Minb = maxcost; // 更新上界
			}
		}

		e1.i = e.i + 1;			 // 扩展结点e，分配下一行的各列，对应结点e1
		for (j = 1; j <= n; j++) // 考虑n个任务
		{
			if (e.alloc[j])
				continue;					// 行j是否已选择某列,若已选择，跳过
			for (int i1 = 1; i1 <= n; i1++) // 复制e.x得到e1.x
				e1.x[i1] = e.x[i1];
			e1.x[e1.i] = j;					// 为行e1.i选择列j
			for (int i2 = 1; i2 <= n; i2++) // 复制e.alloc得到e1.alloc
				e1.alloc[i2] = e.alloc[i2];
			e1.alloc[j] = true;			   // 表示行j已经选择列
			e1.cost = e.cost + c[e1.i][j]; // 继承父节点代价，加上本层的代价
			bound(e1);					   // 求e1的lb
			e1.no = total++;
			if (e1.lb >= Minb)
				qu.push(e1);
		}
	}
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &c[i][j]);
	bfs();
	printf("%d", maxcost);
}

匈牙利算法 Kuhn-Munkres(KM)

有权二部图

二分图： 节点由两个集合组成，且两个集合内部没有边的图，如果节点间带权，那么就是有权二部图，可以用来表示任务指派问题。

如果$\left|u\right|=\left|v\right|$，则适用匈牙利算法。

以下内容可以参考这个视频：14-4: 匈牙利算法 Hungarian Algorithm_哔哩哔哩_bilibili

最小匹配

对于一个这样一个有权二部图，我们可以使用邻接矩阵表示：

$$\left[\begin{array}{ccc}8& 25& 50\\ 50& 35& 75\\ 22& 48& 150\end{array}\right]$$

1. 预处理：找到每一行的最小值，即8，35，22，让每一行的元素减去当前行的最小值（行规约） ，得到：

$$\left[\begin{array}{ccc}0& 17& 42\\ 15& 0& 40\\ 0& 26& 128\end{array}\right]$$

减去每一列的最小值，即0，0，50，让每一列的元素减去当前列的最小值（列规约），得到：

$$\left[\begin{array}{ccc}0& 17& 2\\ 15& 0& 0\\ 0& 26& 88\end{array}\right]$$

操作完毕后，每一行、每一列都存在至少一个0。 2. 接下来循环2-4步。用最少的线覆盖矩阵中的0，如图： 3. 如果用的线等于$\left|u\right|$或$\left|v\right|$，则中止循环； 4. 否则在所有未覆盖的元素中（会被所谓打钩步骤标记）寻找最小的元素，即2，将未覆盖的元素全部减去这个元素，增加矩阵中0的个数；然后将红线交叉的节点加上这个元素，得到：

$$\left[\begin{array}{ccc}0& 15& 0\\ 17& 0& 0\\ 0& 24& 86\end{array}\right]$$

然后循环以上2-4步，最终得到一个满足条件的矩阵，反映最小匹配：

$$\left[\begin{array}{ccc}0& 15& 0\\ 17& 0& 0\\ 0& 24& 86\end{array}\right]$$

5. 接下来选择边。选择$\left|u\right|$个0，要求每列只有一个0被选中，最终的选择为：

$$\left[\begin{array}{ccc}0& 15& (0)\\ 17& (0)& 0\\ (0)& 24& 86\end{array}\right]$$

即选择$u_1$的第三条边，$u_2$的第二条边，$u_3$的第一条边。 当然，这一步可能会出现多种选择方案，说明问题存在多解。

最大匹配

能够处理最小情况的算法在对数据进行一定处理后可以找出最大匹配。 对于匈牙利算法来说，只要把每个边的权重取成它的相反数（或者是和某个值的差），然后按最小匹配来做就行了。

使用匈牙利算法优化

D25 二分图最大匹配 匈牙利算法_哔哩哔哩_bilibili 本节使用匈牙利算法优化金陵十三钗问题。 代码实现KM算法，需要补充图论的几个概念：

交替路

从未匹配点出发，依次经过非匹配边、匹配边的路径。

增广路

从未匹配点（左集合）出发，走交替路，且能够走到另一个未匹配点（右集合）的路径。 例如下图中的$3\to 5\to 1\to 4\to 2\to 7$，此时匹配到两条路径 如果把这条路径倒着走（有时候称之为“取反”），将匹配边视作未匹配边，未匹配边视作匹配边，就可以得到一条新的匹配路径： 进而增加匹配边数。

“划线”实质

这一节部分内容肯定有错，或者是不严谨，大概明白意思就行。 先说结论： 划线覆盖0的原因有二，一是0的边作为最小权重的边存在被匹配的可能，二是如果当前匹配状态下找到增广路并对其进行取反操作后这些0的路径会称为匹配边（所以当划线数等于左右集合元素个数$\left|u\right|$ 或$\left|v\right|$的时候，说明给每个左右节点之间都找到了匹配边，因此可以结束算法）。 接下来实操一下，例如本题的最小数据：

$$\left[\begin{array}{cccc}97& 91& 68& 14\\ 8& 33& 27& 92\\ 36& 32& 98& 53\\ 73& 7& 17& 82\end{array}\right]$$

经过差值转化为最大匹配问题并进行归约处理后得到：

$$\left[\begin{array}{cccc}0& 0& 29& 83\\ 84& 53& 65& 0\\ 62& 60& 0& 45\\ 9& 69& 65& 0\end{array}\right]$$

使用贪心策略（选择当前具有最小未匹配机会的行）对0进行匹配，确保每列只有一个0被选中，存储在一个数组中，这一步选择的结果是$\{0,3,2,-1\}$，如果某一行不存在可以被选择的0，则标记为-1。 然后是本算法最抽象的部分，通过维护一个行列标记系统来覆盖增广路路径。 首先明确一下这个邻接矩阵行列在有权二部图中的含义。每一行的代表的是左集合对应的节点，而每一列的数据则对应当前行向右集合的节点的一条路径。 在对矩阵进行处理的过程中，我们致力于得到并优先选择0，这个0代表两个节点的连接所需代价为0，因为KM算法计算最小匹配路径，所以优先选择权重为0的边。

1. 由增广路定义，其起点应当是左集合中的一个未被匹配的节点，也就是上述被标记为$-1$的那一列。我们又知道增广路要求我们走交替路，所以选择最后一行的权重为0的边，这是一条未匹配路径$U_4\to V_4$（上图中的红线表示已匹配路径，就是通过贪心选择的每列不重复的0，即在上面表格中用正方形括起来的元素）；
2. 接下来选已匹配路径，找一下之前选的匹配路径（红线）与4联通的是$U_2$节点，由交替路定义，此时只能选择这一条路；
3. 接下来选择未匹配路径，由于$V_2$无匹配的边与之相连，故不选择，因此增广路路径应该为$U_2\to V_1$或$V_3$;
4. 接下来选择与上述相同，反正就是走交替路，找到的增广路路径终点就是右侧未匹配点$V_2$ 这个过程要用代码实现，就需要维护一个行列选择状态：
5. 计算preTip，即被选择的边和列之和；
6. 选择增广路起点，将起点（矩阵列）标记为true，只要是未匹配到到左集合节点都是起点，全部都要标记；
7. 从起点出发，选择边权为0的边之后，到达右侧对应列数的节点，此时对应的一整列代表右侧节点与左侧节点相连的各边的权重，选择这列中权重为0的边，将其对应的矩阵行标记为true；
8. 接下来选择匹配边，将其对应的列标记为true，这几步都会有多个满足条件的元素，全部都要标记；
9. 计算curTip，即标记矩阵后被选择的边和列之和，如果curTip相较于preTip没有变化的话，说明已经不能找到更多的增广路了，结束标记；
10. 划线交叉处加上未被划线的区域的最小值，未被划线的区域减去这个最小值；
11. 尝试选择每列不重的0，如果可以则退出循环，不可以则继续上述举证变换；
12. 根据选择的边选择原矩阵对应的边，计算总代价，如果是最大匹配转化的最小匹配问题，则通过某种方法将转化矩阵计算出的最小匹配转化为最大匹配即可。

然后根据行列选择状态划线，规则是划未被选择的行和被选择的列，直到划了n条线为止。这个划线说到底就是把含0的边全部选出来，下次处理矩阵的时候不再考虑这些边，至于划线划到其它非0元素，其实是没有影响的，因为这个节点已经在此之前拥有了权重为0的边，这些边显然比那些非0的边代价更低，选择他们更优（也许吧，真不确定这里hhh），重点就是减小下次矩阵处理的规模。

//代码注释的不一定对，不想细改了，参考一下就行
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

int n;		   // 元素个数
int *assign;   // 分配结果
int **mat;	   // 代价矩阵
int **matRcd;  // 代价矩阵
int totalCost; // 总成本
void p(){
	cout << "----------------" << endl;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			cout<<mat[i][j]<<" ";
		cout<<endl;
	}
}
//-------------------------------------数据读取
bool read(const char *ad)
{
	// 数据读取
	int m;
	ifstream iff;
	iff.open(ad);
	if (!iff)
		return false;
	iff >> n;
	assign = new int[n];
	for (int i = 0; i < n; i++)
		assign[i] = -1;
	mat = new int *[n];
	for (int i = 0; i < n; i++)
		mat[i] = new int[n];
	matRcd = new int *[n];
	for (int i = 0; i < n; i++)
		matRcd[i] = new int[n];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			iff >> m;
			mat[i][j] = 100 - m;
			matRcd[i][j] = mat[i][j];
		}
	}
	iff.close();
	totalCost = 0;
	return true;
}

//-------------------------------------行归约
void rowSub()
{
	int *minEmt = new int[n];
	for (int i = 0; i < n; i++)
		minEmt[i] = (int)1e8;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (mat[i][j] < minEmt[i])
				minEmt[i] = mat[i][j];//得到每一行的最小值
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			mat[i][j] -= minEmt[i];//减去每一行的最小值
	delete[] minEmt;
}

//-------------------------------------列归约
void columnSub()
{
	int *minEmt = new int[n];
	for (int j = 0; j < n; j++)
		minEmt[j] = (int)1e8;
	for (int j = 0; j < n; j++)
		for (int i = 0; i < n; i++)
			if (mat[i][j] < minEmt[j])
				minEmt[j] = mat[i][j];//得到每一列的最小值
	for (int j = 0; j < n; j++)
		for (int i = 0; i < n; i++)
			mat[i][j] -= minEmt[j];//减去每一列的最小值
	delete[] minEmt;
}

//-------------------------------------检验最优
bool isOptimal(int *assign)//匹配矩阵中的0，确保每列只有一个0被选中，应用贪心策略
{
	int *tAssign = new int[n];
	for (int i = 0; i < n; i++)
		tAssign[i] = -1;//动态分配空间给一个临时的分配结果数组，认为-1是该行无法选择
	int *nZero = new int[n];//存储每一行未被匹配的0的数量
	bool *rowIsUsed = new bool[n];//存储每一行是否被使用过
	bool *columnIsUsed = new bool[n];//存储每一列是否被使用过
	for (int i = 0; i < n; i++)
		rowIsUsed[i] = columnIsUsed[i] = false;
	int nLine = 0;//初始化

	while (nLine < n)
	{
		for (int i = 0; i < n; i++)
			nZero[i] = 0;//初始化
		for (int i = 0; i < n; i++)
		{
			if (rowIsUsed[i] == true)
				continue;
			for (int j = 0; j < n; j++)//遍历未被使用过的行的每一列
			{
				if (columnIsUsed[j] == false && mat[i][j] == 0)
					nZero[i]++;//找到一个未被匹配的0，更新该行
			}
		}
		int minZeros = n;
		int rowId = -1;
		for (int i = 0; i < n; i++)
		{
			if (rowIsUsed[i] == false && nZero[i] < minZeros && nZero[i] > 0)
			{
				minZeros = nZero[i];
				rowId = i;
			}
		}
		if (rowId == -1)
			break;
		for (int j = 0; j < n; j++)
		{
			if (mat[rowId][j] == 0 && columnIsUsed[j] == 0)
			{
				rowIsUsed[rowId] = 1;
				columnIsUsed[j] = 1;
				tAssign[rowId] = j;
				break;
			}
		}
		nLine++;
	}
	for (int i = 0; i < n; i++)
		assign[i] = tAssign[i];//存储分配结果
	delete[] tAssign;//回收内存
	delete[] nZero;
	delete[] rowIsUsed;
	delete[] columnIsUsed;

	for (int i = 0; i < n; i++)
		if (assign[i] == -1)
			return false;
	return true;
}

//-------------------------------------矩阵变换
void matTrans()
{
	bool *rowTip = new bool[n];//标记每一行是否被选中，其实是左集合和右集合之间的一条路径
	bool *columnTip = new bool[n];//标记每一列是否被选中
	bool *rowLine = new bool[n];//标记每一行是否被画线
	bool *columnLine = new bool[n];//标记每一列是否被画线
	for (int i = 0; i < n; i++)
		rowTip[i] = columnTip[i] = rowLine[i] = columnLine[i] = 0;//初始化上面四个数组
	// 打钩
	for (int i = 0; i < n; i++)
		if (assign[i] == -1)
			rowTip[i] = true;//寻找一个未被匹配的点，从这个点出发寻找增广路

	while (1)//寻找增广路，以匹配更多的点
	{
		int preTip = 0;//统计被标记的行列数总和
		for (int i = 0; i < n; i++)
			preTip += rowTip[i] + columnTip[i];
		for (int i = 0; i < n; i++)//找到增广路的所有可能起点
		{
			if (rowTip[i] == true)//找到一个增广路起点
			{
				for (int j = 0; j < n; j++)
				{
					if (mat[i][j] == 0)
						columnTip[j] = true;
				}
			}
		}
		for (int j = 0; j < n; j++)
		{
			if (columnTip[j] == true)//延伸增广路
			{
				for (int i = 0; i < n; i++)
				{
					if (assign[i] == j)//根据增广路要求指向已经被分配的节点
						rowTip[i] = true;
				}
			}
		}
		int curTip = 0;
		for (int i = 0; i < n; i++)
			curTip += rowTip[i] + columnTip[i];
		if (preTip == curTip)//不存在新的增广路，退出循环
			break;
	}

	// 画线
	for (int i = 0; i < n; i++)
	{
		if (rowTip[i] == false)
			rowLine[i] = true;
		if (columnTip[i] == true)
			columnLine[i] = true;
	}

	// 找最小元素
	int minElmt = (int)1e8;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (rowLine[i] == false && columnLine[j] == false && mat[i][j] < minElmt)
				minElmt = mat[i][j];
	// 变换
	for (int i = 0; i < n; i++)
		if (rowTip[i] == true)
			for (int j = 0; j < n; j++)
				mat[i][j] -= minElmt;//未选中的元素减去最小值
	for (int j = 0; j < n; j++)
		if (columnTip[j] == true)
			for (int i = 0; i < n; i++)
				mat[i][j] += minElmt;//交叉点加最小值
	delete[] rowTip;
	delete[] columnTip;
	delete[] rowLine;
	delete[] columnLine;
}
//-------------------------------------匈牙利算法
void hungary()
{
	read("input10.txt"); // 读取数据
	rowSub();			 // 行归约
	columnSub();		 // 列归约
	p();
	// 如果不能找到n个独立的0元素，则对矩阵进行变换
	while (!isOptimal(assign))
	{
		matTrans();
		p();
	}
	for (int i = 0; i < n; i++)
		totalCost += matRcd[i][assign[i]];//计算结果
	for (int i = 0; i < n; i++)//释放空间
		delete[] mat[i];
	delete[] mat;
	for (int i = 0; i < n; i++)
		delete[] matRcd[i];
	delete[] matRcd;
}

int main()
{
	// 调用匈牙利算法
	hungary();
	// 输出结果
	cout << n * 100 - totalCost << endl;
	//	for(int i=0;i<n;i++)cout<<"员工"<<i+1<<"-->"<<"任务"<<assign[i]+1<<endl;

	//	cin.get();
}

素数筛法

埃氏筛

先设定is_prime[0]和is_prime[1]为false，其它项为true，然后将后续为true的项加入素数表中，并将其倍数标记为false证明： 对于一个数 $n$，已经筛出了 $1\sim n$ 的所有素数，由素数定义（质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数），$n$ 没有被前面的数的倍数筛掉，说明 $n$ 在 $1\sim n$ 之间没有因数，显然在 $\ge n$ 的区间内也没有它的因数，显然意见 $n$ 就是一个素数。 时间复杂度 $0(n\log (\log n))$

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int maxn = 666;
long prime[maxn];
bool is_prime[maxn+1];
int p = 0;

int sieve(int n){
    p = 0;
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for(int i = 2;i<=n;i++){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j = i;j<=n/i;j++){
                is_prime[i*j] = false;
            }
        }
    }
    return p;    
}

int main(int argc, char const *argv[])
{
    cout << sieve(666) << endl;
    return 0;
}

欧拉筛

埃氏筛作为筛法相对于试除法更为高效，但是存在一些非质数被重复筛去的问题，例如$15=5\times 3=3\times 5$，会被两个不同的数筛两遍，欧拉筛的目的就是保证每个非质数只被其最小质因子筛去。 证明： 欧拉筛的前提是素数定理，一个数总能被分解为一些质因子的乘积：

$$n=\prod _{i=1}^n{p}_i^{e_i}$$

所以在埃氏筛中，一个数会被这些质因子重复筛去，为了将时间复杂度优化成线性，我们只要选取这些质因子中的最小的一个来筛$n$即可。 这个筛法的具体操作就是维护$1\sim i$之间的素数，筛去$j=p_j\times i$，那么接下来的问题就是$p_j$范围怎么取了。![[未标题-2.svg]]

前面已经说了，要用最小质因子筛去，由素数定理可知，$p_i$一定可以分解成质因数乘积，假定其中的最小质因子为$p_i$，为了让$p_j$是$n$的质因子中最小的那一个，一定会有$p_j<p_i$，如上图。 翻译成人话就是数到$i$之后往前找他的最小质因数，把已经筛出的素数与$i$相乘，一直乘到$i$的最小质因子$p_i$为止，筛去乘积。

#include <iostream>
#include <cstring>
using namespace std;
int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    bool isprime[n+1];
    memset(isprime, true, sizeof isprime);
    int prime[n] = {0};
    isprime[0] = isprime[1] = false;
    int p = 0;
    for(int i = 2;i<=n;i++){
        if(isprime[i]) prime[p++] = i;
        int k = 0;
        while(i % prime[k] != 0){
            if(i*prime[k] <= n) isprime[i*prime[k]] = false;
            k++;
        }
        if(i % prime[k] == 0){
            if(i*prime[k] <= n) isprime[i*prime[k]] = false;
        }
    }
    int sum = 0;
    for(auto x:prime){
        if(x != 0) sum++;
    }
    cout << sum << endl;
    return 0;
}

素数估计

在$n$较小的情况下，可以用$\frac{n}{ln(n)}$估计素数个数，更精确一点的可以使用$\underset{2}{\overset{x}{\int }}\frac{dt}{lnt}$