基础算法

发表于 2020-08-04 更新于 2025-02-18 分类于 OI ，模板阅读次数：本文字数： 3.2k 阅读时长 ≈ 12 分钟

1、递推：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)共有 \(n\) 级台阶，每次可以上 \(1-k\) 级，上完的方案数：

#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n,k;
int f[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
int main()
{
	n=qread();
	k=qread();
	f[0]=1;
	for(re int i=1;i<=n;i++)
	{
		for(re int j=max(0,i-k);j<i;j++)
		{
			f[i]+=f[j];
		}
	}
	qwrite(f[n]);
	putchar('\n');
    return 0;
}

2、递归：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)输出 \(a\) 与 \(b\) 的最大公约数：

#include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int a,b;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
in int gcd(re int x,re int y)
{
	return (x?gcd(y%x,x):y);
}
int main()
{
	a=qread();
	b=qread();
	qwrite(gcd(a,b));
	putchar('\n');
    return 0;
}

3、排序：

①、选择排序：

\(\qquad\!\!\)选择排序是易得到的排序算法。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

#include<bits/stdc++.h>
#define in inline
#define re register
#define swap(r,s) (r^s?r^=s^=r^=s:r=s)
const int N=N;
const int inf=0x3f3f3f3f;
using namespace std;
int n;
int a[N];
int minn,o;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
int main()
{
    n=qread();
    for(re int i=1;i<=n;i++)
    {
        a[i]=qread();
    }
    for(re int i=1;i<=n;i++)
    {
        minn=inf;
        o=i;
        for(re int j=i;j<=n;j++)
        {
            if(a[j]<minn)
            {
                minn=a[j];
                o=j;
            }
        }
        swap(a[i],a[o]);
        qwrite(a[i]);
        putchar(' ');
    }
    putchar('\n');
    return 0;
}

②、冒泡排序：

\(\qquad\!\!\)冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

#include<bits/stdc++.h>
#define in inline
#define re register
#define swap(r,s) (r^s?r^=s^=r^=s:r=s) 
const int N=N;
using namespace std;
int n;
int a[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=qread();
	}
	for(re int i=n;i>1;i--)
	{
		for(re int j=1;j<i;j++)
		{
			if(a[j]>a[j+1])
			{
				swap(a[j],a[j+1]);
			}
		}
	}
	for(re int i=1;i<=n;i++)
	{
		qwrite(a[i]);
		putchar(' ');
	}
	putchar('\n');
    return 0;
}

③、插入排序：

\(\qquad\!\!\)插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n;
int a[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=qread();
	}
	for(re int i=2;i<=n;i++)
	{
		int temp=a[i];
		int j=i-1;
		while(j&&temp<a[j])
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=temp;
	}
	for(re int i=1;i<=n;i++)
	{
		qwrite(a[i]);
		putchar(' ');
	}
	putchar('\n');
    return 0;
}

④、快速排序：

#include<bits/stdc++.h>
#define in inline
#define re register
#define swap(r,s) (r^s?r^=s^=r^=s:r=s)
const int N=N;
using namespace std;
int n;
int a[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
in void qsort(re int x,re int y)
{
	int l=x,r=y;
	int mid=a[(x+y)>>1];
	while(l<=r)
	{
		while(a[l]<mid)
		{
			l++;
		}
		while(a[r]>mid)
		{
			r--;
		}
		if(l<=r)
		{
			swap(a[l],a[r]);
			l++;
			r--;
		}
	}
	if(x<r)
	{
		qsort(x,r);
	}
	if(l<y)
	{
		qsort(l,y);
	}
	return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=qread();
	}
	qsort(1,n);
	for(re int i=1;i<=n;i++)
	{
		qwrite(a[i]);
		putchar(' ');
	}
	putchar('\n');
    return 0;
}

⑤、归并排序：

\(\qquad\!\!\)归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。若将两个有序数列合并成一个有序数列，称为二路归并。

#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n;
int a[N],b[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
in void msort(re int x,re int y)
{
	int mid=((x+y)>>1);
	if(x==y)
	{
		return ;
	}
	msort(x,mid);
	msort(mid+1,y);
	int i=x,j=mid+1,o=x;
	while(i<=mid&&j<=y)
	{
		if(a[i]>a[j])
		{
			b[o++]=a[j];
			j++;
		}
		else
		{
			b[o++]=a[i];
			i++;
		}
	}
	while(i<=mid)
	{
		b[o++]=a[i++];
	}
	while(j<=y)
	{
		b[o++]=a[j++];
	}
	for(re int i=x;i<=y;i++)
	{
		a[i]=b[i];
	}
	return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=qread();
	}
	msort(1,n);
	for(re int i=1;i<=n;i++)
	{
		qwrite(a[i]);
		putchar(' ');
	}
	putchar('\n');
    return 0;
}

⑥、堆排序：

\(\qquad\!\!\)堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n;
int a[N];
priority_queue<int> q;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=-qread();
		q.push(a[i]);
	}
	for(re int i=1;i<=n;i++)
	{
		a[i]=-q.top();
		q.pop();
		qwrite(a[i]);
		putchar(' ');
	}
	putchar('\n');
    return 0;
}

⑦、计数排序：

#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N; 
const int M=M;
const int inf=0x3f3f3f3f;
using namespace std;
int n,minn=inf,maxx=-inf,o;
int a[N],b[M];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=qread();
		b[a[i]]++;
		minn=min(minn,a[i]);
		maxx=max(maxx,a[i]);
	}
	for(re int i=minn;i<=maxx;i++)
	{
		while(b[i]--)
		{
			a[++o]=i;
		}
	}
	for(re int i=1;i<=n;i++)
	{
		qwrite(a[i]);
		putchar(' ');
	}
	putchar('\n');
    return 0;
}

4、二分：

①、二分答案：

例题：P2678 跳石头

#include<bits/stdc++.h>
#define in inline
#define re register
const int N=50010;
using namespace std;
int s,n,m;
int a[N];
int l,r,mid,ans;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
in bool pd()
{
	int x=0,now=0;
	for(int j=1;j<n;j++)
	{
		if(now==n-1&&a[n]-a[n-1]<mid)
		{
			x++;
		}
		if(a[j]-a[now]>=mid)
		{
			now=j;
		}
		else
		{
			x++;
		}
	}
	if(x>m)
	{
		return 0;
	}
	return 1;
}
int main()
{
	s=qread();
	n=qread();
	m=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=qread();
	}
	a[n+1]=s;
	n++;
	l=1;
	r=s;
	while(l<=r)
	{
		mid=((l+r)>>1);
		if(pd())
		{
			l=mid+1;
			ans=max(ans,mid);
		}
		else
		{
			r=mid-1;
		}
	}
	qwrite(ans);
	putchar('\n');
    return 0;
}

②、三分答案：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)P3382 【模板】三分法

#include<bits/stdc++.h>
#define in inline
#define re register
const double eps=1e-6;
const int N=20;
using namespace std;
int n;
double a[N];
double l,r,mid;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in double F(re double x)
{
	double res=0;
	for(re int i=n;i>=0;i--)
	{
		res=res*x+a[i];
	}
	return res;
}
int main()
{
	n=qread();
	scanf("%lf%lf",&l,&r);
	for(re int i=n;i>=0;i--)
	{
		scanf("%lf",&a[i]);
	}
	while(r-l>=eps)
	{
		mid=(l+r)/2;
		F(mid+eps)>F(mid-eps)?l=mid:r=mid;
	}
	printf("%.5lf",l);
    return 0;
}

5、贪心：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)P1080 国王游戏（不含高精加 \(60\) 分版本）

#include<bits/stdc++.h>
#define in inline
#define re register
#define int long long
const int N=1010;
using namespace std;
int n,a,b,ans;
struct node
{
	int l,r;
	bool operator < (const node &x)const
	{
		return max(x.r,l*r)<max(r,x.l*x.r);
	}
};
node c[N]; 
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
signed main()
{
	n=qread();
	a=qread();
	b=qread();
	for(re int i=1;i<=n;i++)
	{
		c[i].l=qread();
		c[i].r=qread();
	}
	sort(c+1,c+n+1);
	for(re int i=1;i<=n;i++)
	{
		ans=max(ans,a/c[i].r);
		a*=c[i].l;
	}
	qwrite(ans);
	putchar('\n');
	return 0;
}

6、搜索：

①、深度优先搜索：

in void dfs(参数表)
{
    if(满足条件)
    {
        统计答案
        return;
    }
    for(由此时能够到达的全部可能的情况)
    {
        if(满足传递的条件)
        {
            操作
            dfs(下一个到达的情况);
            回溯
        }
    }
    return;
}

②、广度优先搜索：

in void bfs()
{
    初始化状态入队
    while(!q.empty())
    {
        弹出队头
        if(满足到达的条件)
        {
            if(满足条件)
            {
                统计答案;
                continue;
            }
            for(由此时能够到达的全部可能的情况)
            {
                if(满足传递的条件)
                {
                    操作
                    新情况入队
                }
            }
        }
    }
}

③、记忆化搜索：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)P1434 [SHOI2002]滑雪

#include<bits/stdc++.h>
#define in inline
#define re register
const int N=110;
using namespace std;
int m,n;
int a[N][N],f[N][N];
int fx[4]={1,0,-1,0},fy[4]={0,1,0,-1};
int ans;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
in int dfs(re int x,re int y)
{
	if(f[x][y])
	{
		return f[x][y];
	}
	f[x][y]=1;
	for(re int i=0;i<=3;i++)
	{
		int xx=x+fx[i];
		int yy=y+fy[i];
		if(xx>0&&yy>0&&xx<=m&&yy<=n&&a[x][y]>a[xx][yy])
		{
			f[x][y]=max(f[x][y],dfs(xx,yy)+1);
		}
	}
	return f[x][y];
}
int main()
{
	m=qread();
	n=qread();
	for(re int i=1;i<=m;i++)
	{
		for(re int j=1;j<=n;j++)
		{
			a[i][j]=qread();
		}
	}
	for(re int i=1;i<=m;i++)
	{
		for(re int j=1;j<=n;j++)
		{
			f[i][j]=dfs(i,j);
			ans=max(ans,f[i][j]);
		}
	}
	qwrite(ans);
	putchar('\n');
    return 0;
}

④、搜索剪枝：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)P1120 小木棍［数据加强版］

#include<bits/stdc++.h>
#define in inline
#define re register
const int N=70;
using namespace std;
int n,cnt,sum;
int a[N],nxt[N];
bool vis[N],f;
int len,m;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in bool comp(re int x,re int y)
{
	return x>y;
}
in void dfs(re int x,re int y,re int z)
//现在用第 x 根木棍，编号为 y，总长度为 z
{
	int i=0;
	if(!z)
	{
		if(x==m)
		{
			f=1;
			return ;
		}
		for(i=1;i<=cnt;i++)
		{
			if(!vis[i])
			{	
				break;
			}
		}
		vis[i]=1;
		dfs(x+1,i,len-a[i]);
		if(f)
		{
			return ;
		}
		vis[i]=0;
	}
	int l=y+1,r=n;
	while(l<r)
	{
		int mid=((l+r)>>1);
		if(a[mid]<=z)
		{
			r=mid;
		}
		else
		{
			l=mid+1;
		}
	}
	for(i=l;i<=n;i++)
	{
		if(vis[i])
		{
			continue;
		}
		vis[i]=1;
		dfs(x,i,z-a[i]);
		if(f)
		{
			return ;
		}
		vis[i]=0;
		if(z==a[i]||z==len)
		{
			return ;
		}
		i=nxt[i];
		if(i==cnt)
		{
			return ;
		}
	}
	return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		int x=qread();
		if(x>50)
		{
			continue;
		}
		a[++cnt]=x;
		sum+=x; 
	}
	n=cnt;
	sort(a+1,a+n+1,comp);
	nxt[n]=n;
	for(re int i=n-1;i;i--)
	{
		a[i]==a[i+1]?nxt[i]=nxt[i+1]:nxt[i]=i;
	}
	for(len=a[1];len<=(sum>>1);len++)
	{
		if(sum%len)
		{
			continue;
		}
		m=sum/len;
		vis[1]=1;
		dfs(1,1,len-a[1]);
		if(f)
		{
			qwrite(len);
			putchar('\n');
			return 0;
		}
		vis[1]=0;
	}
	qwrite(sum);
	putchar('\n');
	return 0;
}