当前位置： 首页 > article >正文

C++各类函数评点+详解

article 2024/11/16 17:50:34

1. C++源代码1.0 新手必看

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

int main()
{
	
	
	return 0;
}

#include <bits/stdc++.h>

//#include <iostream>
using namespace std;

int main()
{
        
    return 0;
}
 

#include

 1 #include <bits/stdc++.h>

这个头文件可以在99%评测系统和Dev-C++编译环境使用 （VScode VS不适用）

2 #include <iostream>

这个头文件可以在100%评测系统和Dev-C++编译环境使用 （VScode VS适用）

但是------------------------

       只能控制cin和cout，几乎不能控制任何函数，比较麻烦

using namespace std;

如果不加，几乎所有语句需要加上：

std::

例如：

std::cout<<"hello!"<<endl;//或者'\n'

std::cout<<"hello!"<<endl;//或者'\n'

2.判素数

bool pss(int n)
{
	if(n<2) return false;
	for(int i=2; i<=sqrt(n); i++)
	{
		if(n%i==0) return false; 
	}
	return true;
}

bool pss(int n)
{
    if(n<2) return false;
    for(int i=2; i<=sqrt(n); i++)
    {
        if(n%i==0) return false; 
    }
    return true;
}‘

当是素数时返回1，否则返回0。

for()循环中，sqrt(n)的时间复杂度比 i*i<=n 要小很多，建议使用。

完整代码：

#include <bits/stdc++.h>
using namespace std;
long long n;
bool pss(int n)
{
	if(n<2) return false;
	for(int i=2; i<=sqrt(n); i++)
	{
		if(n%i==0) return false; 
	}
	return true;
}
int main()
{
	
	cin>>n;
	cout<<pss(n)<<'\n';
	system("pause");
	for(int i=1; i<=n; i++)
	{
		cout<<setw(10)<<i<<": "<<pss(i)<<'\n';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long n;
bool pss(int n)
{
    if(n<2) return false;
    for(int i=2; i<=sqrt(n); i++)
    {
        if(n%i==0) return false; 
    }
    return true;
}
int main()
{
    
    cin>>n;
    cout<<pss(n)<<'\n';
    system("pause");
    for(int i=1; i<=n; i++)
    {
        cout<<setw(10)<<i<<": "<<pss(i)<<'\n';
    }
    return 0;
} 

3.约数和

long long ysh(long long n)
{
	long long s=0;
	for(int i=1; i<=sqrt(n); i++)
	{
		if(n%i==0) s=s+i+n/i;
		if(i*i==n) s=s-i; 
	}
	return s;
}

long long ysh(long long n)
{
    long long s=0;
    for(int i=1; i<=sqrt(n); i++)
    {
        if(n%i==0) s=s+i+n/i;
        if(i*i==n) s=s-i; 
    }
    return s;
}

完整输出1~n每一个数约数和的代码：

#include <bits/stdc++.h>
using namespace std;
long long n;
long long ysh(long long n)
{
	long long s=0;
	for(int i=1; i<=sqrt(n); i++)
	{
		if(n%i==0) s=s+i+n/i;
		if(i*i==n) s=s-i; 
	}
	return s;
}
int main()
{
	
	cin>>n;
	cout<<ysh(n)<<'\n';
	system("pause");
	for(int i=1; i<=n; i++)
	{
		cout<<setw(10)<<i<<": "<<setw(15)<<ysh(i)<<'\n';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long n;
long long ysh(long long n)
{
    long long s=0;
    for(int i=1; i<=sqrt(n); i++)
    {
        if(n%i==0) s=s+i+n/i;
        if(i*i==n) s=s-i; 
    }
    return s;
}
int main()
{
    
    cin>>n;
    cout<<ysh(n)<<'\n';
    system("pause");
    for(int i=1; i<=n; i++)
    {
        cout<<setw(10)<<i<<": "<<setw(15)<<ysh(i)<<'\n';
    }
    return 0;
}
 

难度增加-------------------------------

进入算法

1 数字地图遍历

#include <bits/stdc++.h>
using namespace std;
int n,m,gx,gy;
int a[25][25];//请注意范围
int ans;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
	a[x][y]=-1;
	ans++;//直接累加求和 
	for(int i=0; i<4; i++)
	{
		int lx=x+dx[i];
		int ly=y+dy[i];
		if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
		if(a[lx][ly]==0) dg(dep+1,lx,ly);
	}
}
void dr()
{
	memset(a,-1,sizeof(a));
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			int t;
			cin>>t;
			if(t==0) a[i][j]=0;
			if(t==1) a[i][j]=-1;
			if(t==2)
			{
				a[i][j]=0;
				gx=i;
				gy=j;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	dr();//用来套模板
	dg(1,gx,gy);
	cout<<ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m,gx,gy;
int a[25][25];//请注意范围
int ans;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
    a[x][y]=-1;
    ans++;//累加求和 
    for(int i=0; i<4; i++)
    {
        int lx=x+dx[i];
        int ly=y+dy[i];
        if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
        if(a[lx][ly]==0) dg(dep+1,lx,ly);
    }
}
void dr()
{
    memset(a,-1,sizeof(a));
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            int t;
            cin>>t;
            if(t==0) a[i][j]=0;
            if(t==1) a[i][j]=-1;
            if(t==2)
            {
                a[i][j]=0;
                gx=i;
                gy=j;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    dr();//用来套模板
    dg(1,gx,gy);
    cout<<ans;
    return 0;
}

字符版：

#include <bits/stdc++.h>
using namespace std;
int n,m,gx,gy;
int a[25][25];//请注意范围
int ans;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
	a[x][y]=-1;
	ans++;//累加求和 
	for(int i=0; i<4; i++)
	{
		int lx=x+dx[i];
		int ly=y+dy[i];
		if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
		if(a[lx][ly]==0) dg(dep+1,lx,ly);
	}
}
void dr()
{
	memset(a,-1,sizeof(a));
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			char t;
			cin>>t;
			if(t=='.') a[i][j]=0;
			if(t=='#') a[i][j]=-1;
			if(t=='@')
			{
				a[i][j]=0;
				gx=i;
				gy=j;
			}
		}
	}
}
int main()
{
	dr();//用来套模板
	dg(1,gx,gy);
	cout<<ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m,gx,gy;
int a[25][25];//请注意范围
int ans;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
    a[x][y]=-1;
    ans++;//累加求和 
    for(int i=0; i<4; i++)
    {
        int lx=x+dx[i];
        int ly=y+dy[i];
        if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
        if(a[lx][ly]==0) dg(dep+1,lx,ly);
    }
}
void dr()
{
    memset(a,-1,sizeof(a));
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            char t;
            cin>>t;
            if(t=='.') a[i][j]=0;
            if(t=='#') a[i][j]=-1;
            if(t=='@')
            {
                a[i][j]=0;
                gx=i;
                gy=j;
            }
        }
    }
}
int main()
{
    dr();//用来套模板
    dg(1,gx,gy);
    cout<<ans;
    return 0;
}

递归求解问题

池塘遍历，有几个连通块

#include <bits/stdc++.h>
using namespace std;
int n,m,gx=1,gy=1;
int a[105][105];//请注意范围
int ans;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
	a[x][y]=-1;
	for(int i=0; i<4; i++)
	{
		int lx=x+dx[i];
		int ly=y+dy[i];
		if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
		if(a[lx][ly]==0) dg(dep+1,lx,ly);
	}
}//用来搜索并蔓延该池塘每个角落的-1 
void dr()
{
	memset(a,-1,sizeof(a));
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			char t;
			cin>>t;
			if(t=='W') a[i][j]=0;
			if(t=='.') a[i][j]=-1;
		}
	}
}
int main()
{
	dr();//用来套模板
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			if(a[i][j]==0)
			{
				/*
				1 为什么不会重复
				    因为dg()函数已经将前面的池塘扫描并赋为-1
				2 为什么可以使用“0 ”，题目中为字符
				    因为dr()函数已经将 "."和"W"变为了-1和 0
				*/
				ans++;
				dg(1,i,j);
			}
		}
	}
	cout<<ans;
	return 0;
}
/*
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

20 20
WWW.......WWW..WWWW.
.WWW...WWWWW...WWWWW
.WWWWW..WWWWWW.WWWWW
WWWWW..WWW......WWW.
WWWWWW.WW.......WW..
WWWWW...W......WW...
WWWWW.....W....W..WW
W........WWWWW...WWW
.......WWWWWWWWW.WW.
.W.W.W.WWW...W...W..
.WWWW.WWW.....WWWWWW
...............WW... 
.WW.............W..W
.W..........WW....WW
.WWWWWWWW.WWW....WWW
.....WWWW.WWWW.....W
.WWWWWWW.....WWW...W
..W.......W...W.....
..WWW....WWWW.....WW
W..W..WW...W..W.W..W

ans:16
*/

#include <bits/stdc++.h>
using namespace std;
int n,m,gx=1,gy=1;
int a[105][105];//请注意范围
int ans;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
    a[x][y]=-1;
    for(int i=0; i<4; i++)
    {
        int lx=x+dx[i];
        int ly=y+dy[i];
        if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
        if(a[lx][ly]==0) dg(dep+1,lx,ly);
    }
}//用来搜索并蔓延该池塘每个角落的-1 
void dr()
{
    memset(a,-1,sizeof(a));
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            char t;
            cin>>t;
            if(t=='W') a[i][j]=0;
            if(t=='.') a[i][j]=-1;
        }
    }
}
int main()
{
    dr();//用来套模板
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(a[i][j]==0)
            {
                /*
                1 为什么不会重复
                    因为dg()函数已经将前面的池塘扫描并赋为-1
                2 为什么可以使用“0 ”，题目中为字符
                    因为dr()函数已经将 "."和"W"变为了-1和 0
                */
                ans++;
                dg(1,i,j);
            }
        }
    }
    cout<<ans;
    return 0;
}
/*
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

20 20
WWW.......WWW..WWWW.
.WWW...WWWWW...WWWWW
.WWWWW..WWWWWW.WWWWW
WWWWW..WWW......WWW.
WWWWWW.WW.......WW..
WWWWW...W......WW...
WWWWW.....W....W..WW
W........WWWWW...WWW
.......WWWWWWWWW.WW.
.W.W.W.WWW...W...W..
.WWWW.WWW.....WWWWWW
...............WW... 
.WW.............W..W
.W..........WW....WW
.WWWWWWWW.WWW....WWW
.....WWWW.WWWW.....W
.WWWWWWW.....WWW...W
..W.......W...W.....
..WWW....WWWW.....WW
W..W..WW...W..W.W..W

ans:16
*/ 

8方向

#include <bits/stdc++.h>
using namespace std;
int n,m,gx=1,gy=1;
int a[105][105];//请注意范围
int ans;
int dx[10]= {0,0,1,-1,1,-1,1,-1};
int dy[10]= {1,-1,0,0,-1,1,1,-1};
void dg(int dep,int x,int y)
{
	a[x][y]=-1;
	for(int i=0; i<8; i++)//8方向 
	{
		int lx=x+dx[i];
		int ly=y+dy[i];
		if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
		if(a[lx][ly]==0) dg(dep+1,lx,ly);
	}
}//用来搜索并蔓延该池塘每个角落的-1 
void dr()
{
	memset(a,-1,sizeof(a));
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			char t;
			cin>>t;
			if(t=='W') a[i][j]=0;
			if(t=='.') a[i][j]=-1;
		}
	}
}
int main()
{
	dr();//用来套模板
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			if(a[i][j]==0)
			{
				/*
				1 为什么不会重复
				    因为dg()函数已经将前面的池塘扫描并赋为-1
				2 为什么可以使用“0 ”，题目中为字符
				    因为dr()函数已经将 "."和"W"变为了-1和 0
				*/
				ans++;
				dg(1,i,j);
			}
		}
	}
	cout<<ans;
	return 0;
}
/*
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

20 20
WWW.......WWW..WWWW.
.WWW...WWWWW...WWWWW
.WWWWW..WWWWWW.WWWWW
WWWWW..WWW......WWW.
WWWWWW.WW.......WW..
WWWWW...W......WW...
WWWWW.....W....W..WW
W........WWWWW...WWW
.......WWWWWWWWW.WW.
.W.W.W.WWW...W...W..
.WWWW.WWW.....WWWWWW
...............WW... 
.WW.............W..W
.W..........WW....WW
.WWWWWWWW.WWW....WWW
.....WWWW.WWWW.....W
.WWWWWWW.....WWW...W
..W.......W...W.....
..WWW....WWWW.....WW
W..W..WW...W..W.W..W

ans:13
*/

#include <bits/stdc++.h>
using namespace std;
int n,m,gx=1,gy=1;
int a[105][105];//请注意范围
int ans;
int dx[10]= {0,0,1,-1,1,-1,1,-1};
int dy[10]= {1,-1,0,0,-1,1,1,-1};
void dg(int dep,int x,int y)
{
    a[x][y]=-1;
    for(int i=0; i<8; i++)//8方向 
    {
        int lx=x+dx[i];
        int ly=y+dy[i];
        if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
        if(a[lx][ly]==0) dg(dep+1,lx,ly);
    }
}//用来搜索并蔓延该池塘每个角落的-1 
void dr()
{
    memset(a,-1,sizeof(a));
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            char t;
            cin>>t;
            if(t=='W') a[i][j]=0;
            if(t=='.') a[i][j]=-1;
        }
    }
}
int main()
{
    dr();//用来套模板
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(a[i][j]==0)
            {
                /*
                1 为什么不会重复
                    因为dg()函数已经将前面的池塘扫描并赋为-1
                2 为什么可以使用“0 ”，题目中为字符
                    因为dr()函数已经将 "."和"W"变为了-1和 0
                */
                ans++;
                dg(1,i,j);
            }
        }
    }
    cout<<ans;
    return 0;
}
/*
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

20 20
WWW.......WWW..WWWW.
.WWW...WWWWW...WWWWW
.WWWWW..WWWWWW.WWWWW
WWWWW..WWW......WWW.
WWWWWW.WW.......WW..
WWWWW...W......WW...
WWWWW.....W....W..WW
W........WWWWW...WWW
.......WWWWWWWWW.WW.
.W.W.W.WWW...W...W..
.WWWW.WWW.....WWWWWW
...............WW... 
.WW.............W..W
.W..........WW....WW
.WWWWWWWW.WWW....WWW
.....WWWW.WWWW.....W
.WWWWWWW.....WWW...W
..W.......W...W.....
..WWW....WWWW.....WW
W..W..WW...W..W.W..W

ans:13
*/ 

迷宫问题
正常版
#include <bits/stdc++.h>
using namespace std;
int n,gx=1,gy=1;
int a[105][105];//请注意范围
int xa,ya,xb,yb;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
	a[x][y]=-1;
	if(x==xb&&y==yb)
	{
		cout<<"YES";
		exit(0); 
	}
	for(int i=0; i<4; i++)
	{
		int lx=x+dx[i];
		int ly=y+dy[i];
		if(lx<1||lx>n||ly<1||ly>n||a[lx][ly]==-1) continue;
		if(a[lx][ly]==0) dg(dep+1,lx,ly);
	}
}
void dr()
{
	memset(a,-1,sizeof(a));
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			int t;
			cin>>t;
			if(t==0) a[i][j]=0;
			if(t==1) a[i][j]=-1;
		}
	}
	cin>>xa>>ya>>xb>>yb;
}
int main()
{
	dr();//用来套模板
	if(a[xa][ya]==-1||a[xb][yb]==-1)
	{
		cout<<"NO";
		return 0;
	}
	dg(1,xa,ya);
	cout<<"NO";//如果没有在递归中终止，说明无法到达，输出“NO ” 
	return 0;
}
/*

*/

#include <bits/stdc++.h>
using namespace std;
int n,gx=1,gy=1;
int a[105][105];//请注意范围
int xa,ya,xb,yb;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
    a[x][y]=-1;
    if(x==xb&&y==yb)
    {
        cout<<"YES";
        exit(0); 
    }
    for(int i=0; i<4; i++)
    {
        int lx=x+dx[i];
        int ly=y+dy[i];
        if(lx<1||lx>n||ly<1||ly>n||a[lx][ly]==-1) continue;
        if(a[lx][ly]==0) dg(dep+1,lx,ly);
    }
}
void dr()
{
    memset(a,-1,sizeof(a));
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            int t;
            cin>>t;
            if(t==0) a[i][j]=0;
            if(t==1) a[i][j]=-1;
        }
    }
    cin>>xa>>ya>>xb>>yb;
}
int main()
{
    dr();//用来套模板
    if(a[xa][ya]==-1||a[xb][yb]==-1)
    {
        cout<<"NO";
        return 0;
    }
    dg(1,xa,ya);
    cout<<"NO";//如果没有在递归中终止，说明无法到达，输出“NO ” 
    return 0;
}
/*

*/ 

字符版
#include <bits/stdc++.h>
using namespace std;
int n,gx=1,gy=1;
int a[105][105];//请注意范围
int xa,ya,xb,yb;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
	a[x][y]=-1;
	if(x==xb&&y==yb)
	{
		cout<<"YES";
		exit(0); 
	}
	for(int i=0; i<4; i++)
	{
		int lx=x+dx[i];
		int ly=y+dy[i];
		if(lx<1||lx>n||ly<1||ly>n||a[lx][ly]==-1) continue;
		if(a[lx][ly]==0) dg(dep+1,lx,ly);
	}
}
void dr()
{
	memset(a,-1,sizeof(a));
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			char t;
			cin>>t;
			if(t=='.') a[i][j]=0;
			if(t=='#') a[i][j]=-1;
		}
	}
	cin>>xa>>ya>>xb>>yb;
}
int main()
{
	dr();//用来套模板
	if(a[xa][ya]==-1||a[xb][yb]==-1)
	{
		cout<<"NO";
		return 0;
	}
	dg(1,xa,ya);
	cout<<"NO";//如果没有在递归中终止，说明无法到达，输出“NO ” 
	return 0;
}
/*

*/

#include <bits/stdc++.h>
using namespace std;
int n,gx=1,gy=1;
int a[105][105];//请注意范围
int xa,ya,xb,yb;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
void dg(int dep,int x,int y)
{
    a[x][y]=-1;
    if(x==xb&&y==yb)
    {
        cout<<"YES";
        exit(0); 
    }
    for(int i=0; i<4; i++)
    {
        int lx=x+dx[i];
        int ly=y+dy[i];
        if(lx<1||lx>n||ly<1||ly>n||a[lx][ly]==-1) continue;
        if(a[lx][ly]==0) dg(dep+1,lx,ly);
    }
}
void dr()
{
    memset(a,-1,sizeof(a));
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            char t;
            cin>>t;
            if(t=='.') a[i][j]=0;
            if(t=='#') a[i][j]=-1;
        }
    }
    cin>>xa>>ya>>xb>>yb;
}
int main()
{
    dr();//用来套模板
    if(a[xa][ya]==-1||a[xb][yb]==-1)
    {
        cout<<"NO";
        return 0;
    }
    dg(1,xa,ya);
    cout<<"NO";//如果没有在递归中终止，说明无法到达，输出“NO ” 
    return 0;
}
/*

*/ 

走法
#include <bits/stdc++.h>
using namespace std;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
int ans=INT_MAX,n,m;
int a[105][105];
int d[105][105];
int xa,ya,xb,yb;
void dg(int dep,int x,int y)
{
	if(dep<d[x][y])
	{
		d[x][y]=dep;
		for(int i=0; i<4; i++)
		{
			int lx=x+dx[i];
			int ly=y+dy[i];
			if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1||dep+1>=ans) continue;
			if(a[lx][ly]==0) dg(dep+1,lx,ly);
		}
	}
}
void dr()
{
	cin>>n>>m;
	memset(a,-1,sizeof(a));
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			char t;
			cin>>t;
			if(t!='#') a[i][j]=0;
			if(t=='@')
			{
				xa=i;
				ya=j;
			}
			if(t=='*')
			{
				xb=i;
				yb=j;
			}
		}
	}
}
int main()
{
	dr();
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++) d[i][j]=INT_MAX;
	}
	dg(0,xa,ya);
	if(d[xb][yb]==INT_MAX) cout<<-1;
	else cout<<d[xb][yb];
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int dx[5]= {0,0,1,-1};
int dy[5]= {1,-1,0,0};
int ans=INT_MAX,n,m;
int a[105][105];
int d[105][105];
int xa,ya,xb,yb;
void dg(int dep,int x,int y)
{
    if(dep<d[x][y])
    {
        d[x][y]=dep;
        for(int i=0; i<4; i++)
        {
            int lx=x+dx[i];
            int ly=y+dy[i];
            if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1||dep+1>=ans) continue;
            if(a[lx][ly]==0) dg(dep+1,lx,ly);
        }
    }
}
void dr()
{
    cin>>n>>m;
    memset(a,-1,sizeof(a));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            char t;
            cin>>t;
            if(t!='#') a[i][j]=0;
            if(t=='@')
            {
                xa=i;
                ya=j;
            }
            if(t=='*')
            {
                xb=i;
                yb=j;
            }
        }
    }
}
int main()
{
    dr();
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++) d[i][j]=INT_MAX;
    }
    dg(0,xa,ya);
    if(d[xb][yb]==INT_MAX) cout<<-1;
    else cout<<d[xb][yb];
    return 0;
}

跳马问题

正常版
#include <bits/stdc++.h>
using namespace std;
int dx[10]={1,2,2,1,-1,-2,-2,-1};
int dy[10]={-2,-1,1,2,2,1,-1,-2};
int n,m,x,y,s,t,ans=INT_MAX;
int a[10][10];
int d[10][10];
void dg(int dep,int x,int y)
{
	if(x==s&&y==t)
	{
		if(dep<ans) ans=dep;
		return ;
	}
	a[x][y]=-1;
	for(int i=0; i<=7; i++)
	{
		int lx=x+dx[i];
		int ly=y+dy[i];
		if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
		if(a[lx][ly]==0) dg(dep+1,lx,ly);
	}
	a[x][y]=0;	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>x>>y>>s>>t;
	dg(0,x,y);
	cout<<ans;
	return 0;
}
障碍版
#include <bits/stdc++.h>
using namespace std;
int dx[10]={1,2,2,1,-1,-2,-2,-1};
int dy[10]={-2,-1,1,2,2,1,-1,-2};
int n,m,x,y,s,t,ans=INT_MAX;
int a[10][10];
int d[10][10];
void dg(int dep,int x,int y)
{
	if(x==s&&y==t)
	{
		if(dep<ans) ans=dep;
		return ;
	}
	a[x][y]=-1;
	for(int i=0; i<=7; i++)
	{
		int lx=x+dx[i];
		int ly=y+dy[i];
		if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
		if(a[lx][ly]==0) dg(dep+1,lx,ly);
	}
	a[x][y]=0;	
}
void dr()
{
	memset(a,-1,sizeof(a));
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			int t;
			cin>>t;
			if(t==0) a[i][j]=0;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>x>>y>>s>>t;
	dr();
	dg(0,x,y);
	cout<<ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int dx[10]={1,2,2,1,-1,-2,-2,-1};
int dy[10]={-2,-1,1,2,2,1,-1,-2};
int n,m,x,y,s,t,ans=INT_MAX;
int a[10][10];
int d[10][10];
void dg(int dep,int x,int y)
{
    if(x==s&&y==t)
    {
        if(dep<ans) ans=dep;
        return ;
    }
    a[x][y]=-1;
    for(int i=0; i<=7; i++)
    {
        int lx=x+dx[i];
        int ly=y+dy[i];
        if(lx<1||lx>n||ly<1||ly>m||a[lx][ly]==-1) continue;
        if(a[lx][ly]==0) dg(dep+1,lx,ly);
    }
    a[x][y]=0;    
}
void dr()
{
    memset(a,-1,sizeof(a));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            int t;
            cin>>t;
            if(t==0) a[i][j]=0;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>x>>y>>s>>t;
    dr();
    dg(0,x,y);
    cout<<ans;
    return 0;
}

字符+障碍
#include <bits/stdc++.h>
using namespace std;
int dx[10]= {1,2,2,1,-1,-2,-2,-1};
int dy[10]= {-2,-1,1,2,2,1,-1,-2};
int n,m,gx,gy,ex,ey;
int a[105][105];
int d[105][105];
void dg(int dep,int x,int y)
{
	if(dep<d[x][y])
	{
		d[x][y]=dep;
		for(int i=0; i<=7; i++)
		{
			int lx=x+dx[i];
			int ly=y+dy[i];
			if(lx<1||lx>n||ly<1||ly>m||a[x][y]==-1) continue;
			dg(dep+1,lx,ly);
		}
	}
}
void dr()
{
	cin>>m>>n;
	memset(a,-1,sizeof(a));
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			char t;
			cin>>t;
			d[i][j]=INT_MAX;
			if(t!='*') a[i][j]=0;
			if(t=='K')
			{
				gx=i;
				gy=j;
			}
			if(t=='H')
			{
				ex=i;
				ey=j;
			} 
		}
	}
}
int main()
{
	dr();
	dg(0,gx,gy);
	cout<<d[ex][ey];
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int dx[10]= {1,2,2,1,-1,-2,-2,-1};
int dy[10]= {-2,-1,1,2,2,1,-1,-2};
int n,m,gx,gy,ex,ey;
int a[105][105];
int d[105][105];
void dg(int dep,int x,int y)
{
    if(dep<d[x][y])
    {
        d[x][y]=dep;
        for(int i=0; i<=7; i++)
        {
            int lx=x+dx[i];
            int ly=y+dy[i];
            if(lx<1||lx>n||ly<1||ly>m||a[x][y]==-1) continue;
            dg(dep+1,lx,ly);
        }
    }
}
void dr()
{
    cin>>m>>n;
    memset(a,-1,sizeof(a));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            char t;
            cin>>t;
            d[i][j]=INT_MAX;
            if(t!='*') a[i][j]=0;
            if(t=='K')
            {
                gx=i;
                gy=j;
            }
            if(t=='H')
            {
                ex=i;
                ey=j;
            } 
        }
    }
}
int main()
{
    dr();
    dg(0,gx,gy);
    cout<<d[ex][ey];
    return 0;
}


汉诺塔
#include <bits/stdc++.h>
using namespace std;
int n;
void dg(int n,char a,char b,char c)
{
	if(n==1)
	{
		cout<<a<<" To "<<c<<'\n';
		return ;
	}
	dg(n-1,a,c,b);
	cout<<a<<" To "<<c<<'\n';
	dg(n-1,b,a,c);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	dg(n,'A','B','C');
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
void dg(int n,char a,char b,char c)
{
    if(n==1)
    {
        cout<<a<<" To "<<c<<'\n';
        return ;
    }
    dg(n-1,a,c,b);
    cout<<a<<" To "<<c<<'\n';
    dg(n-1,b,a,c);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    dg(n,'A','B','C');
    return 0;
}

01背包
#include <bits/stdc++.h>
using namespace std;
// 01背包(1.0.0版本) 难度： Lv.1
/*
实现版块
1 求出各种数值 
*/
int ans,n;
/*
ans:价钱不同时的数量
n:物品的数量
*/ 
int a[500];//存储每一个物品的价格 
int b[50000];//答案数量数组 
void dg(int dep,int money)
{
	if(dep>=n)//当已经完全遍历完每一个物品时
	{
		int f=1;//旗帜 
		for(int i=1; i<=ans; i++)
		{
			if(money==b[i])//得出的价钱与以前拥有的值重复
			{
				f=0;//遍历失败
				break;//退出循环
			}
		}
		if(f==1)
		{
			ans++;//当遍历成功，不同的价钱数量增加 
			b[ans]=money;//存入这个价钱
		}
		return ;//因为类型是无返回值类型，所以手动结束程序
	}
	dg(dep+1,money+a[dep]);//分类讨论
	dg(dep+1,money);//分类讨论
}
int main()
{
	cin>>n;//输入 n
	for(int i=1; i<=n; i++) cin>>a[i];//输入 n 个物品的价格
	dg(1,0);//使用 01 背包递归以解决所有的值
	cout<<ans;//输出： 通过选择各个物品分类讨论买与不买的情况，最后得出不同的值的数量
	return 0;
}
/*
样例1（建议复制换行）
5
1 2 3 3 3

结果：10

-------------------------------
样例2（建议复制换行）
10
2 2 2 2 2 2 2 2 2 2

01背包问题总解决方案
01背包的代码长度优化
01背包时间复杂度改进
*/

 

#include <bits/stdc++.h>
using namespace std;
// 01背包(1.0.0版本) 难度： Lv.1
/*
实现版块
1 求出各种数值 
*/
int ans,n;
/*
ans:价钱不同时的数量
n:物品的数量
*/ 
int a[500];//存储每一个物品的价格 
int b[50000];//答案数量数组 
void dg(int dep,int money)
{
    if(dep>=n)//当已经完全遍历完每一个物品时
    {
        int f=1;//旗帜 
        for(int i=1; i<=ans; i++)
        {
            if(money==b[i])//得出的价钱与以前拥有的值重复
            {
                f=0;//遍历失败
                break;//退出循环
            }
        }
        if(f==1)
        {
            ans++;//当遍历成功，不同的价钱数量增加 
            b[ans]=money;//存入这个价钱
        }
        return ;//因为类型是无返回值类型，所以手动结束程序
    }
    dg(dep+1,money+a[dep]);//分类讨论
    dg(dep+1,money);//分类讨论
}
int main()
{
    cin>>n;//输入 n
    for(int i=1; i<=n; i++) cin>>a[i];//输入 n 个物品的价格
    dg(1,0);//使用 01 背包递归以解决所有的值
    cout<<ans;//输出： 通过选择各个物品分类讨论买与不买的情况，最后得出不同的值的数量
    return 0;
}
/*
样例1（建议复制换行）
5
1 2 3 3 3

结果：10

-------------------------------
样例2（建议复制换行）
10
2 2 2 2 2 2 2 2 2 2

01背包问题总解决方案
01背包的代码长度优化
01背包时间复杂度改进
*/

01背包2.0
#include <bits/stdc++.h>
using namespace std;
// 01背包(1.1.0版本) 难度： Lv.2
/*
实现版块
1 求出最优方案
*/
int ans,n,m;
/*
ans:价钱不同时的数量
n:物品的数量
m:可以装载货物的重量
*/
int a[500];//存储每一个物品的价格
int b[500];//存储每一个物品的体积
void dg(int dep,int v,int money)
{
	if(v>m) return ;
	if(dep>=n)//当已经完全遍历完每一个物品时
	{ 
		if(v<=m&&money>ans) ans=money;
		return ;//因为类型是无返回值类型，所以手动结束程序
	}
	dg(dep+1,v+b[dep],money+a[dep]);//分类讨论
	dg(dep+1,v,money);//分类讨论
}
int main()
{
	cin>>n>>m;//输入 n,m
	for(int i=1; i<=n; i++) cout<<i<<":",cin>>a[i]>>b[i];//输入 n 个物品的价格
	cout<<"---------------------"<<'\n';
	dg(1,0,0);//使用 01 背包递归以解决所有的值
	cout<<"ans:"<<ans<<'\n';//输出： 通过选择各个物品分类讨论买与不买的情况，最后得出不同的值的数量
	return 0;
}
/*

01背包问题总解决方案
01背包的代码长度优化
01背包时间复杂度改进
*/

#include <bits/stdc++.h>
using namespace std;
// 01背包(1.1.0版本) 难度： Lv.2
/*
实现版块
1 求出最优方案
*/
int ans,n,m;
/*
ans:价钱不同时的数量
n:物品的数量
m:可以装载货物的重量
*/
int a[500];//存储每一个物品的价格
int b[500];//存储每一个物品的体积
void dg(int dep,int v,int money)
{
    if(v>m) return ;
    if(dep>=n)//当已经完全遍历完每一个物品时
    { 
        if(v<=m&&money>ans) ans=money;
        return ;//因为类型是无返回值类型，所以手动结束程序
    }
    dg(dep+1,v+b[dep],money+a[dep]);//分类讨论
    dg(dep+1,v,money);//分类讨论
}
int main()
{
    cin>>n>>m;//输入 n,m
    for(int i=1; i<=n; i++) cout<<i<<":",cin>>a[i]>>b[i];//输入 n 个物品的价格
    cout<<"---------------------"<<'\n';
    dg(1,0,0);//使用 01 背包递归以解决所有的值
    cout<<"ans:"<<ans<<'\n';//输出： 通过选择各个物品分类讨论买与不买的情况，最后得出不同的值的数量
    return 0;
}
/*

01背包问题总解决方案
01背包的代码长度优化
01背包时间复杂度改进
*/

 

完全背包
#include <bits/stdc++.h>
using namespace std;
// 完全背包(1.1.0版本) 难度： Lv.2
/*
实现版块
1 求出最优方案
*/
int ans,n,m;
/*
ans:价钱不同时的数量
n:物品的数量
m:可以装载货物的重量
*/
int a[500];//存储每一个物品的价格
int b[500];//存储每一个物品的体积
void dg(int dep,int v,int money)
{
	if(v>m) return ;
	if(dep>=n)//当已经完全遍历完每一个物品时
	{ 
		if(v<=m&&money>ans) ans=money;
		return ;//因为类型是无返回值类型，所以手动结束程序
	}
	dg(dep+1,v+b[dep],money+a[dep]);//分类讨论
	dg(dep+1,v,money);//分类讨论
}
int main()
{
	cin>>n>>m;//输入 n,m
	for(int i=1; i<=n; i++) cout<<i<<":",cin>>a[i]>>b[i];//输入 n 个物品的价格
	cout<<"---------------------"<<'\n';
	dg(1,0,0);//使用 01 背包递归以解决所有的值
	cout<<"ans:"<<ans<<'\n';//输出： 通过选择各个物品分类讨论买与不买的情况，最后得出不同的值的数量
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
// 完全背包(1.1.0版本) 难度： Lv.2
/*
实现版块
1 求出最优方案
*/
int ans,n,m;
/*
ans:价钱不同时的数量
n:物品的数量
m:可以装载货物的重量
*/
int a[500];//存储每一个物品的价格
int b[500];//存储每一个物品的体积
void dg(int dep,int v,int money)
{
    if(v>m) return ;
    if(dep>=n)//当已经完全遍历完每一个物品时
    { 
        if(v<=m&&money>ans) ans=money;
        return ;//因为类型是无返回值类型，所以手动结束程序
    }
    dg(dep+1,v+b[dep],money+a[dep]);//分类讨论
    dg(dep+1,v,money);//分类讨论
}
int main()
{
    cin>>n>>m;//输入 n,m
    for(int i=1; i<=n; i++) cout<<i<<":",cin>>a[i]>>b[i];//输入 n 个物品的价格
    cout<<"---------------------"<<'\n';
    dg(1,0,0);//使用 01 背包递归以解决所有的值
    cout<<"ans:"<<ans<<'\n';//输出： 通过选择各个物品分类讨论买与不买的情况，最后得出不同的值的数量
    return 0;
} 

dp

1 走台阶

#include <bits/stdc++.h>
using namespace std;
int dp[100]={1,1}; 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for(int i=2; i<=n; i++) dp[i]=dp[i-1]+dp[i-2];
	cout<<dp[n]; 
	return 0;
}

 #include <bits/stdc++.h>
using namespace std;
int dp[100]={1,1}; 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=2; i<=n; i++) dp[i]=dp[i-1]+dp[i-2];
    cout<<dp[n]; 
    return 0;
}

01背包dp通用模板

#include <bits/stdc++.h>
using namespace std;
int t,m,a[20005],b[20005];
int dp[20005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t>>m;
	for(int i=1; i<=m; i++)
	{
		cin>>a[i];
		for(int j=t; j>=a[i]; j--)
		{
			dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
		}
	}
	cout<<t-dp[t];
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int t,m,a[20005],b[20005];
int dp[20005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>a[i];
        for(int j=t; j>=a[i]; j--)
        {
            dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
        }
    }
    cout<<t-dp[t];
    return 0;
}
重要代码：

for(int i=1; i<=m; i++)
	{
		cin>>a[i];
		for(int j=t; j>=a[i]; j--)
		{
			dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
		}
	}

for(int i=1; i<=m; i++)
    {
        cin>>a[i];
        for(int j=t; j>=a[i]; j--)
        {
            dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
        }
    }


http://www.kler.cn/a/396140.html

相关文章：

  • 鸿蒙北向开发 : hdmfs-分布式文件系统
  • arm64架构的linux 配置vm_page_prot方式
  • 医院信息化与智能化系统(21)
  • 【服务器】本地安装X11 服务器-Windows
  • 【LeetCode】【算法】5. 最长回文子串
  • FBX福币交易所恒指收跌1.96% 半导体股继续回调
  • MySQL数据库最大连接数查询及修改
  • R语言贝叶斯分析：INLA 、MCMC混合模型、生存分析肿瘤临床试验、间歇泉喷发时间数据应用|附数据代码...
  • Python实现PSO粒子群优化算法优化CNN-Transformer回归模型(优化权重和阈值)项目实战
  • 开源的说话人分离项目 | 可以对指定的音频分离不同的说话人 | 通话录音中分离不同的说话人
  • 开发中SQL积累
  • 量子奇异值阈值算法
  • vue3: ref, reactive, readonly, shallowReactive
  • Django Form
  • 【计算机网络】TCP网络特点2
  • 理解Go中的append函数及其返回值
  • MFC中Picture Control控件显示照片的几种方式
  • python基础 基本数据类型 执行顺序 条件判断 常用字符串操作 常用工具类
  • 英伟达 Isaac ROS产品体验
  • Java—— 正则表达式
  • 【系统架构设计师】真题论文: 论基于 DSSA 的软件架构设计与应用（包括解题思路和素材）
  • Nacos黑马笔记
  • 前端知识点---this的用法 , this动态绑定(Javascript)
  • 大数据如何助力干部选拔的公正性
  • 宝塔面板从 Nginx 切换到 Caddy：详细教程
  • 麒麟时间同步搭建chrony服务器