当前位置：网站首页>One hundred - day plan -- -- DAY2 brush

One hundred - day plan -- -- DAY2 brush

2022-08-05 02:46:00 【Ceylon_CC】

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

题目描述

输入 $n$ a positive integer no greater than .要求全部储存在数组中,去除掉不是质数的数字,依次输出剩余的质数.

输入格式

第一行输入一个正整数 $n$ ,表示整数个数.

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

输出格式

输出一行,依次输出 $a_i$ the remaining prime numbers in ,以空格隔开.

样例 #1

样例输入 #1

5
3 4 5 6 7

样例输出 #1

3 5 7

提示

数据保证, $1\le n\le100$ , $\leq a_i \leq 10^5$ .

解题思路

1）This problem is essentially a prime number problem,Here is an efficient method for picking prime numbers,欧拉筛法.
2）我们创建两个数组,用vis数组标记每个对应下标的数是否为质数,为0则为质数,为1则为合数.用prime数组记录遍历过程中找到的质数.
3）When traversing, if the current number is a prime number, mark it,Then put the current number×The prime numbers from the previous sieve,This number is marked as composite.

参考代码

#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;
}

第二题马的遍历

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3 3 1 1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点,保证 $\leq x \leq n \leq 400$ , $\leq y \leq m \leq 400$ .

解题思路

1）This problem is essentially a breadth-first search problem,这里可以使用STL模板库中的<queue>.
2）The points that can be reached on the chessboard are entered in the order in which they are found,The first time to reach the target point is the final answer.

参考代码

#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

样例输出 #1

提示

对于 $100\%$ 数据,满足 $\le 30$ , $\le V \le 20000$ .

解题思路

1）This question asks to find the maximum amount that can be loaded,You can think of an object's weight as its value,Then turn the question into a simple one01背包问题.
2）Directly set the backpack board.

参考代码

#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(美国航空航天局)因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋,Therefore, the history of the space shuttle was terminated under pressure from all parties,但是此类事情会不会在以后发生,谁也无法保证,在遇到这类航天问题时,The solution may only be to get astronauts out of the warehouse for repairs,But multiple repairs consume a lot of energy for astronauts,因此NASAI want to design a food plan,Load up on high-calorie foods with limited bulk and weight.

题目描述

Space shuttles are limited in size,Of course if the load is too heavy,Fuel wastes a lot of money,Each food item has its own volume、quality and calories,In the case of telling you the maximum value of volume and mass,Please output the maximum calorie value of the food plan you can achieve,Of course each food can only be used once.

输入格式

第一行两个数体积最大值(<400)and mass maximum(<400)

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

第三行－第3+N行

每行三个数体积(<400) 质量(<400) Calories(<500)

输出格式

一个数 The maximum calorie that can be reached(int范围内)

样例 #1

样例输入 #1

样例输出 #1

解题思路

1）这道题目在01There is one more dimension on the basis of the backpack,Can be applied directly01背包中f[j]=max{f[j],f[j-a[i]]+c[i]的结论,Because the dimension has changed from one dimension to two dimensions,So set up a two-dimensional dynamic array
2）套用01背包板子,Change the form a bit.

参考代码

#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;
}