第一题【深基7.例2】质数筛
题目描述
输入 n个不大于的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。
输入格式
第一行输入一个正整数 n ，表示整数个数。
第二行输入 n 个正整数 a i ，以空格隔开。
输出格式
输出一行，依次输出 a i 中剩余的质数，以空格隔开。
样例 #1
样例输入 #1
5 3 4 5 6 7
样例输出 #1
3 5 7
提示
解题思路
1）这道题目本质上就是质数问题，这里介绍一种高效的挑选质数方法，欧拉筛法。
2）我们创建两个数组，用vis数组标记每个对应下标的数是否为质数，为0则为质数，为1则为合数。用prime数组记录遍历过程中找到的质数。
3）遍历时如果当前数是素数就标记一下，再把当前的数×之前的筛出来的素数，这个数标记为合数。
参考代码
#include <bits/stdc++.h> 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; }
第二题 马的遍历
题目描述
有一个 n × m的棋盘，在某个点 ( x , y ) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数，分别为 n , m , x , y。
输出格式
一个 n × m的矩阵，代表马到达某个点最少要走几步（左对齐，宽 5格，不能到达则输出 − 1 ）。
样例 #1
样例输入 #1
3 3 1 1
样例输出 #1
0 3 2 3 -1 1 2 1 4
提示
数据规模与约定
解题思路
1）这道题目本质上就是广度优先搜索问题，这里可以使用STL模板库 中的<queue>。
2）将棋盘上能到达的点按找顺序依次入队，第一次到达目标点就是最后的答案了。
参考代码
#include<bits/stdc++.h> 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; }
第三题 [NOIP2001 普及组] 装箱问题
题目描述
有一个箱子容量为 V ，同时有 n 个物品，每个物品有一个体积。
现在从 n个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。
输入格式
第一行共一个整数 V，表示箱子容量。
第二行共一个整数 n ，表示物品总数。
接下来 n行，每行有一个正整数，表示第 i个物品的体积。
输出格式
共一行一个整数，表示箱子最小剩余空间。
样例 #1
样例输入 #1
24 6 8 3 12 7 9 7
样例输出 #1
0
提示
解题思路
1）这道题目要求求出最大的可装数量，可以将一个物体的重量当作它的价值，进而将题目转变为一个简单的01背包问题。
2）直接套背包板子。
参考代码
#include<bits/stdc++.h> 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; }
第四题 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
550
解题思路
1）这道题目在01背包的基础上多了一个维度，直接就可以套用01背包中f[j]=max{f[j],f[j-a[i]]+c[i]的结论，因为维度由一维变成了二维，所以设一个二维动态数组
2）套用01背包板子，稍微变一下形式。
参考代码
#include<bits/stdc++.h> 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; }
