线性筛素数

发表于 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-10-04 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]<<" ";
	}
}

Floyd算法

定义一个数组 f[k][x][y]，表示只允许经过结点1到 k，结点x到结点y的最短路长度。

容易得到状态转移方程：f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])，而因为第一维对结果无影响，可以省略，故得到状态转移方程：f[x][y] = min(f[x][y], f[x][k]+f[k][y])。

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

#define int long long
#define maxn 110

int ans[maxn][maxn];

signed main()
{
	int n,m,s;
	cin>>n>>m>>s;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j)
				ans[i][j]=0x7f7f7f7f;
		}
	}
	
	for(int i=1,u,v,w;i<=m;i++)
	{
		cin>>u>>v>>w;
		ans[u][v]=min(ans[u][v], w);
	}
	
	for(int k=1;k<=n;k++)
	{
		for(int x=1;x<=n;x++)
		{
			for(int y=1;y<=n;y++)
			{
				ans[x][y]=min(ans[x][y], ans[x][k]+ans[k][y]);
			}
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		cout<<ans[s][i]<<" ";
	}
	
	return 0;
}

二叉查找树

发表于 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() 删除动态数组最后一个元素

哈夫曼编码

发表于 2024-08-05 更新于 2024-08-06 Valine：

不出现歧义的情况下编出来的码长度最短

让出现次数多的字符编码最短

每次合并最小的两个，即生成一个父节点，使得父节点的值为两个子节点的值之和

排序算法综合

发表于 2024-08-04 更新于 2025-02-04 Valine：

下方所有除使用STL库外的所有排序算法调用方法都是qsort(a,0,n-1);

初级排序算法

冒泡排序

void bubblesort(int* arr, int left, int right)
{
	for(int i=left;i<=right;i++)
	{
		for(int j=i+1;j<=right;j++)
		{
			if(arr[i]>arr[j]) swap(arr[i],arr[j]);
		}
	}
}

选择排序

void selectionsort(int* arr, int left, int right)
{
	for(int i=left;i<=right;i++)
	{
		int min=i; 
		for(int j=i+1;j<=right;j++)
		{
			if(arr[j]<arr[min]) min=j;
		}
		swap(arr[i],arr[min]);
	}
}

插入排序

同整理扑克牌，依次将每个元素插入到前面有序的部分。

void insertionsort(int* arr, int left, int right)
{
	for(int i=left;i<=right;i++)
	{
		int cnt=arr[i];
		for(int j=i-1;j>=left && cnt<=arr[j];j--)
		{
			swap(arr[j],arr[j+1]);
		}
	}
}

优化：可以利用折半查找的方法找到插入的位置，即折半插入排序

希尔排序

通过给定间隔h，使得原来的数组被切分为更小的数组，进而提升插入排序效率

void shellsort(int* arr, int left, int right)
{
	int h=1;
	while(h<(right-left+1)/3) h=h*3+1;
	while(h>=1)
	{
		for(int i=left;i<(right-left+1)/h;i++)
		{
			int cnt=arr[i];
			for(int j=i-h;j>=left && cnt<=arr[j];j-=h)
			{
				swap(arr[j],arr[j+h]);
			}
		}
		h/=3; 
	}
}

进阶排序算法

归并排序

void merge(int *arr, int left, int right)
{
	int aux[10000], mid=(left+right)/2;
	int i=left, j=mid+1;
	for(int k=left; k<=right; k++)
	{
		aux[k]=arr[k];
	}
	for(int k=left;k<=right;k++)
	{
		if(i>mid) arr[k]=aux[j++];
		else if(j>right) arr[k]=aux[i++];
		else if(aux[j]<aux[i]) arr[k]=aux[j++];
		else arr[k]=aux[i++];
	}
}

void mergesort(int *arr, int left, int right)
{
	if(left<right)
	{
		int mid=(left+right)/2;
		mergesort(arr, left, mid);
		mergesort(arr, mid+1, right);
		merge(arr, left, right);
	}
}

快速排序

partition函数：以当前给定集合的第一个元素pivot作为基准，比其小的放在左边，比其大的放在右边
随后对pivot左右的数组分别进行排序，直至left=right结束分治

手写快排

可参考(全网最清晰快速排序)[https://www.bilibili.com/video/BV1vP411g7J3]

int partition(int* arr, int left, int right)
{
	int pivot=arr[left];
	while(left<right)
	{
		while(left<right && arr[right]>=pivot)
			right--;
		arr[left]=arr[right];
		
		while(left<right && arr[left]<=pivot)
			left++;
		arr[right]=arr[left];
	}
	arr[left]=pivot; //arr[right]=pivot;
	return left;
}

void qsort(int* arr, int left, int right)
{
	if(left<right)
	{
		int pivot=partition(arr,left,right);
		qsort(arr,left,pivot-1);
		qsort(arr,pivot+1,right);
	}
}

STL sort

排序规则

//调用：sort(a,a+n,cmp);
bool cmp(int a, int b)
{
	return a<b;
}

NexT, Hello World!

发表于 2024-08-01 更新于 2024-08-03 Valine：

博客全新改版

更换主题为NexT
更换域名为yuzh.tech

基于Schtasks的自动打铃机使用教程

发表于 2022-04-04 更新于 2024-08-03 Valine：

脚本已开源在Github

视频教程

阅读全文 »