单调队列

发表于 2024-09-24 Valine：

单调队列能够保证最大/最小的元素始终出现在队首，同时维持原先数据的顺序。实现单调队列需要用到deque双向队列。

每当获取到一个元素时，弹出前方所有比它小的元素，从而保证队列的单调性；每当最大/最小元素，即队首离开窗口时，则将其弹出队列。

单调队列可以用于解决滑动窗口问题。

滑动窗口问题

有一个长为n的序列a，以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

本题通过分别生成单调递增队列和单调递减队列得到所需结果。完整代码见下：

#include<bits/stdc++.h>
using namespace std;

struct Node
{
	long long id, value;
}node[1000010];

deque<Node> dq;
int n,k;

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>node[i].value;
		node[i].id=i;
		while(dq.size()!=0 && node[i].value<dq.front().value)
		{
			dq.pop_front();
		}
		while(dq.size()!=0 && node[i].value<dq.back().value)
		{
			dq.pop_back();
		}
		dq.push_back(node[i]);
		if(i-dq.front().id>k-1) dq.pop_front();
		if(i>=k) cout<<dq.front().value<<" ";
	}
	cout<<endl;
	dq.clear();
	
	for(int i=1;i<=n;i++)
	{
		node[i].id=i;
		while(dq.size()!=0 && node[i].value>dq.front().value)
		{
			dq.pop_front();
		}
		while(dq.size()!=0 && node[i].value>dq.back().value)
		{
			dq.pop_back();
		}
		dq.push_back(node[i]);
		if(i-dq.front().id>k-1) dq.pop_front();
		if(i>=k) cout<<dq.front().value<<" ";
	}
	return 0;
}

附 C++ deque API：

1. dq.front():返回的一个元素的引用。
2. dq.back():返回最后一个元素的引用。
3. dq.pop_back():删除尾部的元素。不返回值。
4. dq.pop_front()：删除头部元素。不返回值。
5. dq.push_back(e):在队尾添加一个元素e。
6. dq.push_front(e):在对头添加一个元素e。

最小生成树

发表于 2024-09-22 更新于 2024-10-02 Valine：

最小生成树

模板：P3366 【模板】最小生成树 - 洛谷

Prim算法

将任意节点作为根，并找出与之相邻的所有边，获取未获得答案的节点中dis最小的节点(dis用于记录节点到所有邻接点的最短距离)
标记获得的最小节点cur的访问状态为true
将cur节点的临界点dis值进行更新
以cur节点作为根继续搜索下一个dis最小的节点

// Prim
bool flag[maxn];
memset(flag, false, sizeof(flag));
bool pd=false;
int ans=0, dis[maxn];
dis[1]=0;
for(int i=2;i<=n;i++)
{
    dis[i]=0x7f7f7f;
}
for(int i=1;i<=n;i++)
{
    int temp=0x7f7f7f, cur, pnt;
    for(int j=1;j<=n;j++)
    {
        if(flag[j]==false && temp>dis[j])
        {
            temp=dis[j];
            cur=j;
            pnt=edge[j].to;
        }
    }
    if(temp==0x7f7f7f) pd=true;
    flag[cur]=true;

    for(int j=head[cur];j!=-1;j=edge[j].next)
    {
        if(!flag[edge[j].to] && dis[edge[j].to]>edge[j].weight)
        {
            dis[edge[j].to]=edge[j].weight;
        }
    }
    ans+=temp;
}

Kruskal算法

将边从小到大排序
若没有回路，则添加当前边
边数达到n-1时，最小生成树建成

bool cmp(Edge a, Edge b)
{
	return a.weight<b.weight;
}

int fa[maxn];
int findroot(int x) { return fa[x] == x ? x : fa[x] = findroot(fa[x]); }
void Merge(int x, int y) {
	x = findroot(x);
	y = findroot(y);
	fa[x] = y;
}

int main()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++){ fa[i]=i; }
	for(int i=1,u,v,w;i<=m;i++)
	{
		cin>>u>>v>>w;
		addEdge(u,v,w);
		addEdge(v,u,w);
	}
	sort(edge, edge+m*2, cmp);
	int ans=0;
	for(int i=0;i<m*2;i++)
	{
		if(findroot(edge[i].from)!=findroot(edge[i].to))
		{
			Merge(edge[i].from,edge[i].to);
			ans+=edge[i].weight;
		}
	}
	cout<<ans;
	return 0;
}

单源最短路的链式前向星实现

发表于 2024-09-21 更新于 2024-10-02 Valine：

算法的原理以及邻接矩阵实现见先前写的单源最短路径。

相较于邻接矩阵，邻接矩阵在进行松弛操作时需要遍历每一条边，而基于链式前向星的实现仅需执行出度的个数次，大大节省了循环次数。

Dijkstra

下方算法中，dist记录了每个节点当前的最短路径，初始值设定为无穷大；flag记录了先前每一轮循环中未确定答案的点中路径最短的点，即已经获得答案的点；p记录了节点的直接前驱。

// Dijkstra
flag[1]=true;
dist[1]=0;
for(int i=head[1]; i!=-1; i=edge[i].next)
{
    dist[edge[i].to]=edge[i].weight;
    p[edge[i].to]=1;
}

for(int i=1;i<=n-1;i++)
{
    int temp=0x7f7f7f, t=1; // t为源点，此处设定为1 
    for(int j=1;j<=n;j++)
    {
        if(flag[j]==false && dist[j]<temp)
        {
            temp=dist[j];
            t=j;
        }
    }
    if(t==1) break; //无法到达任何一个点 
    flag[t]=true;
    for(int k=head[t]; k!=-1; k=edge[k].next)
    {
        int j=edge[k].to;
        if(flag[j]==false && dist[j]>dist[t]+edge[k].weight )
        {
            dist[j]=dist[t]+edge[k].weight;
            p[j]=t;
        }
    }
}

SPFA

此处实现中的pd用于判断是否存在负环，其余部分为标准SPFA。

判断负环的原理：判断入队次数是否>=n，如果是则说明有负环。

int dis[maxn], cnt[maxn];
bool inq[maxn], pd=false;
memset(dis, 0x3f3f3f3f, sizeof(dis));
memset(cnt, 0, sizeof(cnt));
memset(inq, false, sizeof(inq));
int n,m;
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++)
{
    cin>>u>>v>>w;
    if(w>=0)
    {
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    else
    {
        addEdge(u,v,w);
    }
}
queue<int> q;
q.push(1);
dis[1]=0;
inq[1]=true;
while(!q.empty())
{
    int cnthead=q.front(); q.pop(); inq[cnthead]=false;
    for(int i=head[cnthead];i!=-1;i=edge[i].next)
    {
        int to=edge[i].to, weight=edge[i].weight;
        if(dis[to]>dis[cnthead]+weight)
        {
            dis[to]=dis[cnthead]+weight;
            if(!inq[to])
            {
                if(++cnt[to]>=n)
                {
                    pd=true;
                    break;
                }
                inq[to]=true;
                q.push(to);
            }
        }
    }
    if(pd==true) break;
}
if(pd==true) cout<<"YES"<<endl;
else cout<<dis[n]<<endl;

链式前向星

发表于 2024-09-21 Valine：

概念

链式前向星是一种图的存储方式，相比于邻接矩阵和邻接表，链式前向星是一种静态链表存储，用边集数组和邻接表相结合，可以快速访问一个顶点的所有邻接点。

数据结构详解见视频。

实现

链式前向星存储包括两种结构：

边集数组edge[]：edge[i]表示第i条边;
头结点数组head[]：head[i]存以i为起点的第一条边的下标(在edge[]中的下标)。

Edge结构如下：

struct Edge
{
	int to;
	int weight;
	int next;
}edge[maxn*maxn];

其中，to为当前边的终点，weight为边权，next为当前边终点的兄弟节点，即当前边起点的另外一个邻接点。

添加边需要通过addEdge(u,v,w);执行，完整数据结构维护代码见下：

#define maxn 10001

struct Edge
{
	int to;
	int weight;
	int next;
}edge[maxn*maxn];

int head[maxn], cnt=0;

void addEdge(int from, int to, int weight)
{
	edge[cnt].to=to;
	edge[cnt].weight=weight;
	edge[cnt].next=head[from];
	head[from]=cnt++;
}

若需访问某个节点u的所有邻接点，使用for循环即可，如下所示：

for(int i=head[4];i!=-1;i=edge[i].next)
{
    //输出临界点的编号和到这个临界点的边权
    cout<<edge[i].to<<" "<<edge[i].weight<<endl;
}

线性筛素数

发表于 2024-09-15 Valine：

线性筛（欧拉筛）

原理：每个数都被其最小的质因数筛掉

#include<bits/stdc++.h>
using namespace std;

vector<int> prime;
bool mmap[100000001];

bool isPrime(int a)
{
	for(int i=2;i<=a;i++)
	{
		if(mmap[i]==false) 
		{
			prime.push_back(i);
		}
		for(int j : prime)
		{
			if(j*i>a) break;
			mmap[i*j]=true;
			if(i%j==0) break;
		}
	}
	return mmap[a];
}

int main()
{
	int n;
	cin>>n;
	cout<<!isPrime(n);
	return 0;
}

bfs

发表于 2024-09-13 更新于 2024-09-21 Valine：

广度优先算法

COGS3008 朋友圈

NOI班有n位学员，因为相处时间有限，有的学员之间加了微信，有的学员之间没有。假设加微信的关系是相互的，即如果a加了b的微信，b也会加a的微信。

现在有一条NOI班上的爆炸性的新闻从1号学员发出，每个看到这个新闻的NOI班学员都会在朋友圈转发，而加了他微信的朋友都会看到。没有在NOI班上的学员都不会转发（因为和自己关系不大）。

告诉你NOI班上的学员之间的微信好友关系，请问最终有多少个学员看到这则新闻。

本题为最基本的BFS应用，每有一个元素i入列，使ans+1，同时标记inq[i]=1。

#define MAXN 10010

int n,m;
int mmap[MAXN][MAXN], inq[MAXN];
queue<int> Q;

int main()
{
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)
	{
		cin>>x>>y;
		mmap[x][y]=true;
		mmap[y][x]=true;
	}
	Q.push(1);
	inq[1]=true;
	int ans=1;
	while(!Q.empty())
	{
		int hd=Q.front();
		for(int i=1;i<=n;i++)
		{
			if(mmap[hd][i]==true && inq[i]==false)
			{
				Q.push(i);
				ans++;
				inq[i]=true;
			}
		}
		Q.pop();
	}
	cout<<ans;
	return 0;
}

COGS152 泥潭

1
2
3

Farmer John在早晨6点准时去给贝茜挤奶，然而昨天晚上下了大雨，他的牧场变得泥泞不堪了。Farmer John的家在坐标平面的 (0,0) 处，贝茜在 (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500)。他看见了所有的 N  (1 ≤ N ≤ 10,000) 个泥潭，分别在 (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) 。每个泥潭只占一个点的位置。

Farmer John 刚刚买了新的靴子，他绝对不想把靴子踩进泥潭弄脏，而他又想尽快的找到贝茜。他已经快晚了，因为他花了大量的时间来找到所有的泥潭的位置。 Farmer John 只能平行于坐标轴移动，每次移动一个单位。请你帮助 Farmer John 找到一条路，使得 Farmer John 能够最快的找到贝茜，而且不会弄脏靴子。我们约定一定存在一条路使 Farmer John 找到贝茜。

本题使用结构体记录当前深度，从而得以满足题意

#define MAXN 1010

int dirx[4]={-1,1,0,0};
int diry[4]={0,0,-1,1};

struct cor
{
	int x,y,step;
};

bool mud[MAXN][MAXN], inq[MAXN][MAXN];
queue<cor>Q;
int ans;

int main()
{
	int orix,oriy,n;
	cin>>orix>>oriy>>n;
	for(int i=1,a,b;i<=n;i++)
	{
		cin>>a>>b;
		mud[a+500][b+500]=true;
	}
	Q.push({orix+500,oriy+500,0});
	ans=0;
	inq[orix+500][oriy+500]=true;
	while(!Q.empty())
	{
		cor cur=Q.front();
		if(cur.x==500&&cur.y==500) break;
		for(int i=0;i<4;i++)
		{
			int newx=cur.x+dirx[i], newy=cur.y+diry[i];
			if(newx>=0&&newx<=1000 && newy>=0&&newy<=1000 && inq[newx][newy]==false && mud[newx][newy]==false )
			{
				Q.push({newx, newy, cur.step+1});
				inq[newx][newy]=true;
			}
		}
		Q.pop();
	}
	cout<<Q.front().step;
	return 0;
}

洛谷P1949 聪明的打字员

题目待做，之后补全。

单源最短路径

发表于 2024-08-09 更新于 2024-09-21 Valine：

模板：洛谷P3371 单源最短路径（弱化版）

Bell-man Ford算法

在每一轮对每个点进行松弛，即比较目标点当前的最短路径和出发点最短路径与边权相加的值，取最小值作为最短路径。

int edg[100010][3];
int D[100010];

void bellman(int v)
{
	memset(D,0x3f,sizeof(D));
	D[v]=0;
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(D[edg[j][1]]>D[edg[j][0]]+edg[j][2])
				D[edg[j][1]]=D[edg[j][0]]+edg[j][2];
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<D[i]<<" ";
	}
}

SPFA算法

设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点hd，并且用hd点当前的最短路径估计值对离开hd点所指向的结点to_node进行松弛操作，如果to_node点的最短路径估计值有所调整，且to_node点不在当前的队列中，就将to_node点放入队尾。

void spfa(int root)
{
	memset(D,0x7f7f7f7f,sizeof(D));
	D[root]=0;
	queue<int>Q;
	Q.push(root);
	inq[root]=1;
	
	//当队列不为空
	while(!Q.empty())
	{
		int hd=Q.front();//取出队首节点
		for(int i=0;i<M[hd].size();i++)
		{
			edg e=M[hd][i];
			if(D[e.to_node]>D[hd]+e.value)
			{
				D[e.to_node]=D[hd]+e.value;
				if(inq[e.to_node]==0)
				{
					inq[e.to_node]=true;
					Q.push(e.to_node);
				}
			}
		}
		inq[hd]=0;
		Q.pop();
	}
	
	for(int i=1;i<=n;i++)
	{
		cout<<D[i]<<" ";
	}
}

Dijkstra算法

用于求解非负权图上单源最短路径的算法。从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

vector<edg>M[maxn];
int D[maxn],used[maxn];

void djs(int root)
{
	memset(D,0x7f7f7f7f,sizeof(D));
	D[root]=0;
	
	for(int i=1;i<n;i++)
	{
		int mx=1;
		while(used[mx]==true && mx<=n) mx++;//找到未被使用的点
		for(int j=1;j<=n;j++)
		{
			if(used[j]==false && D[mx]>D[j])
			{
				mx=j;//定位到第一个没有被确认的点 
				break;
			}
		}
		used[mx]=true;
		for(int j=0;j<M[mx].size();j++)
		{
			edg e=M[mx][j];
			if(D[e.to_node]>D[mx]+e.value)
			{
				D[e.to_node]=D[mx]+e.value;
			}
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		cout<<D[i]<<" ";
	}
}

二叉查找树

发表于 2024-08-07 Valine：

基本实现

节点定义

struct Node
{
	int val; //Öµ 
	Node *lefttree,*righttree;//×ó×ÓÊ÷£¬ÓÒ×ÓÊ÷
};
Node *root=NULL;

插入

void insert(Node *&node, int val)
{
	if(node==NULL)
	{
		node = new Node;
		node->val=val;
		node->lefttree = node->righttree = NULL;
        return;
	}
	if(node->val==val) return;
	else if(node->val>val) insert(node->lefttree, val);
	else insert(node->righttree, val);
}

查找

bool search(Node *&node, int val)
{
	if(node==NULL) return false;
	if(node->val==val) return true;
	else if(node->val>val) search(node->lefttree, val);
	else search(node->righttree, val);
}

获取最大值节点和最小值节点

Node *max(Node *&node)
{
	if(node==NULL) return NULL;
	if(node->righttree==NULL) return node;
	else return(max(node->righttree));
}

Node *min(Node *&node)
{
	if(node==NULL) return NULL;
	if(node->lefttree==NULL) return node;
	else return(max(node->lefttree));
}

删除节点

void del(Node *&node, int val)
{
	if(node==NULL) return;
	if(node->val==val)
	{
		if(node->lefttree==NULL && node->righttree==NULL) node=NULL;
		else if(node->lefttree!=NULL)
		{
			Node *pre=max(node->lefttree);
			node->val=pre->val;
			del(node->lefttree, pre->val);
		}
		else if(node->righttree!=NULL)
		{
			Node *aft=min(node->righttree);
			node->val=aft->val;
			del(node->righttree, aft->val);
		}
	}
	else if(node->val>val) del(node->lefttree, val);
	else del(node->righttree, val);
}

使用样例

int main()
{
	insert(root, 1);
	insert(root,3);
	insert(root,4);
	insert(root,2);
	//cout<<root->righttree->val;
	//cout<<search(root,3);
	del(root,4);
	cout<<max(root)->val;
	cout<<min(root)->val;
	return 0;
}

性能分析

最优情况下：二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数为：log(N)。

最差情况下：二叉搜索树退化为单支树（或者类似单支），其平均比较次数为 N。

因此，需要使用平衡二叉树来确保查找、插入和删除的时间复杂度为O(log n)。

链表与下压堆栈

发表于 2024-08-06 Valine：

链表

节点记录

struct Node
{
  int item;
  Node *next;
};

构造链表

为每个元素创造节点

1
2
3

Node *first=new Node;
Node *second=new Node;
Node *third=new Node;

将每个结点的item域设为所需的值

1
2
3

first->item="to";
second->item="be";
third->item="or"

设置next域来构造链表

1 2	first->next=second; second->next=third;

下压堆栈(LIFO)

在表头插入节点

void push(int item)
{
	Node *newNode=new Node;
	newNode->item=item;
	newNode->next=first;
	first=newNode;
	N++;
}

从表头删除节点

int pop()
{
	int item=first->item;
	first=first->next;
	N--;
	return item;
}

遍历链表

for(Node *x=first;x!=NULL;x=x->next)
{
    //处理x->item
}

完整实现

#include<bits/stdc++.h>
using namespace std;

int N;

struct Node
{
  int item;
  Node *next;
};

Node *first = NULL;

void push(int item)
{
	Node *newNode=new Node;
	newNode->item=item;
	newNode->next=first;
	first=newNode;
	N++;
}

int pop()
{
	int item=first->item;
	first=first->next;
	N--;
	return item;
}

int main()
{
	push(1);push(3);push(2);push(4);
	for(Node *x=first;x!=NULL;x=x->next)
	{
		cout<<pop();
	}
	return 0;
}

C++ Vector

发表于 2024-08-06 Valine：

定义方式

1	vector</数据类型/>/名称/(int nSize);

举例：

1	vector<int>vec;

操作方法

vec.push_back() 在动态数组最后插入一个新的元素

vec.pop_back() 删除动态数组最后一个元素