第一题 【深基9.例1】选举学生会

题目描述

学校正在选举学生会成员，有 $n(n\le 999)$ 名候选人，每名候选人编号分别从 1 到 $n$，现在收集到了 $m(m<=2000000)$ 张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

输入格式

输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

输出格式

求出排序后的选票编号。

样例 #1

样例输入 #1

5 10
2 5 2 2 5 2 2 2 1 2
1
2

样例输出 #1

1 2 2 2 2 2 2 2 5 5
1

解题思路

• 1）sort 进行排序。
• 2）进行输出。

参考代码

#include
using namespace std;
int a[1000050];
int main()
{
    int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++) cin>>a[i];
	sort(a,a+m);
	for(int i=0;i<m;i++) cout<<a[i]<<" ";
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

第二题 [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背包问题。

参考代码

#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

第三题 离开中山路

题目背景

《爱与愁的故事第三弹·shopping》最终章。

题目描述

爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在x1,y1处，车站在x2,y2处。现在给出一个n×n（n<=1000）的地图，0表示马路，1表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（a[i][j]距离为1）。你能帮他解决吗？

输入格式

第1行：一个数 n

第2行~第n+1行：整个地图描述（0表示马路，1表示店铺，注意两个数之间没有空格）

第n+2行：四个数 x1,y1,x2,y2

输出格式

只有1行：最短到达目的地距离

样例 #1

样例输入 #1

3
001
101
100
1 1 3 3
1
2
3
4
5

样例输出 #1

4
1

提示

20%数据：n<=100

100%数据：n<=1000

解题思路

• 1）题目问的是最短到达目的地距离，这里就能看出应该用广度优先搜索。
• 2）用结构体存储位置和步数，使用STL模板库中的。将起点入队。
• 3）循环取队头元素，队头位置能到达的点都依次入队并标记为以访问。
• 4）到达重终点退出循环输出答案。

参考代码

#include
using namespace std;

struct xy{
	int x,y,step;
}now,top;

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,m,x,y,xx,yy;
int vis[10001][10001];
char a[10001][10001];
int step=0;
void bfs(int x,int y,int step)
{
	queue<xy> Q;
	top.x=x;
	top.y=y;
	top.step=step;
	Q.push(top);
	vis[x][y]=1;
	while(!Q.empty())
	{
		now=Q.front();
		Q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];
			if(nx<=0||ny<=0||ny>n||nx>n)continue;
			if(vis[nx][ny]==1||a[nx][ny]=='1')continue;			
			top.x=nx;
			top.y=ny;
			top.step=now.step+1;
			vis[nx][ny]=1;
			if(top.x==xx&&top.y==yy)
			{
				cout<<top.step;
				return ;
			}
			Q.push(top);
		}
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>x>>y>>xx>>yy;
	bfs(x,y,0);
	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
56
57
58
59

第四题 入门

题目描述

不是任何人都可以进入桃花岛的，黄药师最讨厌象郭靖一样呆头呆脑的人。所以，他在桃花岛的唯一入口处修了一条小路，这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩，我们认为是安全的，而有的瓷砖一踩上去就会有喷出要命的毒气，那你就死翘翘了，我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上，但它也必须是安全的才行。

由于你是黄蓉的朋友，她事先告诉你哪些砖是安全的、哪些砖是不安全的，并且她会指引你飞到第一块砖上（第一块砖可能在任意安全位置），现在她告诉你进入桃花岛的秘密就是：如果你能走过最多的瓷砖并且没有死，那么桃花岛的大门就会自动打开了，你就可以从当前位置直接飞进大门了。

注意：瓷砖可以重复走过，但不能重复计数。

输入格式

第一行两个正整数 $W$ 和 $H$，分别表示小路的宽度和长度。

以下 $H$ 行为一个 $H\times W$ 的字符矩阵。每一个字符代表一块瓷砖。其中，. 代表安全的砖，# 代表不安全的砖，@ 代表第一块砖。

输出格式

输出一行，只包括一个数，即你从第一块砖开始所能安全走过的最多的砖块个数（包括第一块砖）。

样例 #1

样例输入 #1

11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
1
2
3
4
5
6
7
8
9
10

样例输出 #1

59
1

提示

数据规模与约定

对于全部的测试点，保证 $1\le W,H\le 20$。

解题思路

• 1）深度优先搜索，需要注意的是第一步自己脚下的也要算。

参考代码

#include 
using namespace std;
int sx , sy , ans = 1, n , m; 
char st;
int a[50][50] = {0}; 
int dx[4] = {0 , 1 , 0 , -1} , dy[4] = {1 , 0 , -1 , 0}; 
void dfs(int x , int y){
	for(int v = 0; v < 4; v++)
	{ 
		int xx = x + dx[v] , yy = y + dy[v]; 
		if(a[xx][yy] == 0 && xx <= n && xx >= 1 && yy <= m && yy >= 1){ //既能走，又不越界 
			a[xx][yy] = -1; 
			ans++; 
			dfs(xx , yy); 
		}
	}
}
int main()
{
	cin >> m >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			cin >> st;
			if(st == '.') a[i][j] = 0;
			if(st == '#') a[i][j] = -1;
			if(st == '@')
			{
				sx = i;
				sy = j;
			}
		}
	a[sx][sy] = -1; 
	dfs(sx , sy);
	cout << ans;
	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