第一题【深基7.例2】质数筛

题目描述

输入 $n$ 个不大于的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。

输入格式

第一行输入一个正整数 $n$，表示整数个数。

第二行输入 $n$ 个正整数 $a_i$，以空格隔开。

输出格式

输出一行，依次输出 $a_i$ 中剩余的质数，以空格隔开。

样例 #1

样例输入 #1

5
3 4 5 6 7
1
2

样例输出 #1

3 5 7
1

提示

数据保证，$1\le n\le 100$，$1\le a_i\le 10^5$。

解题思路

• 1）这道题目本质上就是质数问题，这里介绍一种高效的挑选质数方法，欧拉筛法。
• 2）我们创建两个数组，用vis数组标记每个对应下标的数是否为质数，为0则为质数，为1则为合数。用prime数组记录遍历过程中找到的质数。
• 3）遍历时如果当前数是素数就标记一下，再把当前的数×之前的筛出来的素数，这个数标记为合数。

参考代码

#include 
using namespace std;
long long n,m;
bool vis[10000001]={1,1};
int Prime[10000001],k;
void prime(long long n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            Prime[++k]=i;
         }
        for(int j=1;j<=k;j++)
        {
            if(Prime[j]*i>n)
            {
                break;
            }
            vis[Prime[j]*i]=true;
            if(i%Prime[j]==0)
            {
                break;
            }
        }
    }
}
int main()
{
    cin>>n;
    prime(100001);
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        if(!vis[t])
        {
            cout<<t<<" ";
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

第二题 马的遍历

题目描述

有一个 $n\times m$ 的棋盘，在某个点 $(x,y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 $n,m,x,y$。

输出格式

一个 $n\times m$ 的矩阵，代表马到达某个点最少要走几步（左对齐，宽 $5$ 格，不能到达则输出 $-1$）。

样例 #1

样例输入 #1

3 3 1 1
1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4
1
2
3

提示

数据规模与约定

对于全部的测试点，保证 $1\le x\le n\le 400$，$1\le y\le m\le 400$。

解题思路

• 1）这道题目本质上就是广度优先搜索问题，这里可以使用STL模板库 中的。
• 2）将棋盘上能到达的点按找顺序依次入队，第一次到达目标点就是最后的答案了。

参考代码

#include
using namespace std;

struct xy{
	int x,y;
}node,top;
const int dx[8]={-1,-2,-2,-1,1,2,2,1};
const int dy[8]={2,1,-1,-2,2,1,-1,-2};
int a[401][401];
int vis[401][401];
int n,m;
void bfs(int x,int y,int step)
{
	a[x][y]=step;
	vis[x][y]=1;
	queue<xy> Q;
	node.x=x;
	node.y=y;
	Q.push(node);
	while(!Q.empty()){
		top=Q.front();
		Q.pop();
		for(int i=0;i<8;i++)
		{
			int nx=top.x+dx[i];
			int ny=top.y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m)continue;
			if(vis[nx][ny]==0)
			{
				node.x=nx;
				node.y=ny;
				Q.push(node);
				vis[nx][ny]=1;
				a[nx][ny]=a[top.x][top.y]+1;
			}
		}
	}
}

int main()
{
	memset(a,-1,sizeof(a));
	int x,y;
	cin>>n>>m>>x>>y;
	bfs(x,y,0);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			printf("%-5d",a[i][j]);
		}
		cout<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

第三题 [NOIP2001 普及组] 装箱问题

题目描述

有一个箱子容量为 $V$，同时有 $n$ 个物品，每个物品有一个体积。

现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 $V$，表示箱子容量。

第二行共一个整数 $n$，表示物品总数。

接下来 $n$ 行，每行有一个正整数，表示第 $i$ 个物品的体积。

输出格式

• 共一行一个整数，表示箱子最小剩余空间。

样例 #1

样例输入 #1

24
6
8
3
12
7
9
7
1
2
3
4
5
6
7
8

样例输出 #1

0
1

提示

对于 $100\%$ 数据，满足 $0<n\le 30$，$1\le V\le 20000$。

解题思路

• 1）这道题目要求求出最大的可装数量，可以将一个物体的重量当作它的价值，进而将题目转变为一个简单的01背包问题。
• 2）直接套背包板子。

参考代码

#include
using namespace std;
int dp[105000];
int main()
{
	int v,n;
	cin>>v>>n;
	for(int i=1;i<=n;i++)
	{
		int V;
		cin>>V;
		for(int j=v;j>=V;j--)
		{
			dp[j]=max(dp[j],dp[j-V]+V);
		}
	}
	cout<<v-dp[v];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第四题 NASA的食物计划

题目背景

NASA(美国航空航天局)因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋,因此在各方压力下终止了航天飞机的历史,但是此类事情会不会在以后发生，谁也无法保证,在遇到这类航天问题时,解决方法也许只能让航天员出仓维修,但是多次的维修会消耗航天员大量的能量,因此NASA便想设计一种食品方案,让体积和承重有限的条件下多装载一些高卡路里的食物.

题目描述

航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.

输入格式

第一行 两个数 体积最大值(<400)和质量最大值(<400)

第二行 一个数 食品总数N(<50).

第三行－第3+N行

每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)

输出格式

一个数 所能达到的最大卡路里(int范围内)

样例 #1

样例输入 #1

320 350
4
160 40 120
80 110 240
220 70 310
40 400 220
1
2
3
4
5
6

样例输出 #1

550
1

解题思路

• 1）这道题目在01背包的基础上多了一个维度，直接就可以套用01背包中f[j]=max{f[j],f[j-a[i]]+c[i]的结论，因为维度由一维变成了二维，所以设一个二维动态数组
• 2）套用01背包板子，稍微变一下形式。

参考代码

#include
using namespace std;

int dp[550][550];

int main()
{
	int V,M,N;
	cin>>V>>M>>N;
	for(int i=1;i<=N;i++)
	{
		int v,m,ka;
		cin>>v>>m>>ka;
		for(int j=V;j>=v;j--)
		{
			for(int k=M;k>=m;k--)
			{
				dp[j][k]=max(dp[j][k],dp[j-v][k-m]+ka);
			}
		}
	}
	cout<<dp[V][M];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24