洛谷训练题目讲解

|

P1597 语句解析，P1420 最长连号，P1683入门，P2669 金币，P1162 填涂颜色

作者：肖锐

P1597 语句解析

模拟—–switch

判断左值是哪个，再判断’=’后面是变量还是值

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
#include <iostream>
#include <string>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int len = s.size();
	char a = '0', b = '0', c = '0'; //赋初值，防止掉坑，即谁都没有被赋值或者其中有些没有被赋值
	for(int i = 0; i < len; i += 5)
	{
		switch(s[i]) //判断左值
		{
			case 'a':
			{
				if(s[i + 3] >= '0' && s[i + 3] <= '9') //如果是数字的话直接赋值
					a = s[i + 3];
				else //否则赋值另一个变量的值
				{
					if(s[i + 3] == 'b')
						a = b;
					else if(s[i + 3] == 'c')
						a = c;
				}
				break;
			}
			case 'b':
			{
				if(s[i + 3] >= '0' && s[i + 3] <= '9')
					b = s[i + 3];
				else
				{
					if(s[i + 3] == 'a')
						b = a;
					else if(s[i + 3] == 'c')
						b = c;
				}
				break;
			}
			case 'c':
			{
				if(s[i + 3] >= '0' && s[i + 3] <= '9')
					c = s[i + 3];
				else
				{
					if(s[i + 3] == 'b')
						c = b;
					else if(s[i + 3] == 'a')
						c = a;
				}
				break;
			}
		}
	}
	cout << a << " " << b << " " << c;
	return 0;
}

模拟—–map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<map>
using namespace std;
map <char,int> Map;//表示以char类型为下标，存储的是int
string s;
int main()
{
	ios::sync_with_stdio(false);
	cin >> s;
	int len = s.size();
	Map['a'] = Map['b'] = Map['c'] = '0';
	for(int i = 0; i < len; i += 5)
	{
		if( s[i + 3] >= '0' && s[i + 3] <= '9')
			Map[s[i]] = s[i + 3];//s[i]代表左值，s[i + 3]是要赋的值，直接取出数字赋值给对应变量
		else
			Map[s[i]] = Map[s[i + 3]]; //变量之间相赋值
	}
	cout << Map['a'] << " " << Map['b'] << " " << Map['c'];
	return 0;
}

模拟—–开数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int z[3]={0};//存三个变量的值（初始值为0）
	char q,h,wl;//q为被赋值变量，h为赋值量，wl为赋值表达式中不直接关系到运算的无关字符（直接读掉）
	while(scanf("%c %c %c %c %c",&q,&wl,&wl,&h,&wl)!=EOF)//利用scanf返回值，判断是否已读完
	{
		if('0'<=h&&h<='9')z[q-'a']=h-'0';//若为数字，则给变量赋值为此数字
		else z[q-'a']=z[h-'a'];//若为变量，则将这个变量的值赋值给它
	}
	printf("%d %d %d",z[0],z[1],z[2]);//直接输出三变量值
	return 0;
}

P1420 最长连号

暴力求解

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
#include <iostream>
#include <algorithm> //提供max()函数，找出两者最大的那个
using namespace std;
int arr[11000];
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	cin >> arr[i];
	int i = 0;
	int ans = 1;
	while(i < n)
	{
		if(i + 1 < n && arr[i + 1] - arr[i] == 1) //找到开始符合条件的那两个
		{
			int j;
			for(j = i; j < n; j++) //接着找后面看看最多有多少个符合
			{
				if(arr[j + 1] - arr[j] != 1) //不符合就退出
				break;
			}
			ans = max(ans, j - i + 1); //j - i + 1为刚刚找的长度，将之前的比较，调出最大的
        	i = j + 1;
    	}
		else
			i++;
	}
	cout << ans;
	return 0;
}

类似求最大上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int main()
{
	int n,ans=0,temp,b,max=1;
	cin>>n;
	cin>>b; //输入，初始化b
	for(int i=1;i<=n-1;i++)
	{
		cin>>temp;
		if(temp==b+1) max++; //如果这个数是前一个数加1，最大值就增大1
		else max=1; //否则max回到初始值
		if(ans<max) ans=max; //如果最大值比当前的答案大，更改答案
			b=temp; //b=当前这个数
	}
	cout<<ans; //输出
	return 0;
}

P1683入门

BFS小改动

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int len = 300;
char Map[len][len];
int vis[len][len] = {0};
int ans = 0;
int w, h;

struct point
{
	int x, y;
}in, out, beg;
queue<point> q;

int dir[4][2] =
{
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};

int check(int x, int y)
{
	if(!vis[x][y] && x >= 1 && y >= 1 && x <= h && y <= w
		&& Map[x][y] != '#')
		return 1;
	return 0;
}

void bfs(int x, int y)
{
	vis[beg.x][beg.y] = 1;
	q.push(beg);
	while(!q.empty())
	{
		out = q.front();
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			in.x = out.x + dir[i][0];
			in.y = out.y + dir[i][1];
			if(check(in.x, in.y)) 
                //这里改了下就行了，如果符合条件就会自己走，不符合条件的话就结束函数
			{
				q.push(in);
				vis[in.x][in.y] = 1;
				ans++;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> w >> h;
	for(int i = 1; i <= h; i++)
		for(int j = 1; j <= w; j++)
		{
			cin >> Map[i][j];
			if(Map[i][j] == '@')
			{
				beg.x = i;
				beg.y = j;
			}
		}
	bfs(beg.x, beg.y);
	cout << ans + 1;
	return 0;
}

P2669 金币

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll; //注意相加后超出int
int main()
{
	int n;
	cin >> n;
	ll cnt = 0; //总相加数
	ll begin = 1;
	int num = 0, stop = 0; //stop为总加了多少次
	while(stop != n)
	{
        cnt += begin;
		num++;
		if(num == begin) //加1时要加1次，加2时要加两次，以此类推，当加的次数够了，就加下一个
		{
			num = 0;
			begin++;
		}
		stop++;
	}
	cout << cnt;
	return 0;
}

P1162 填涂颜色

BFS联通块

所有不在圈内的0组成的块，必定会触碰边界。
所以从边界上的0开始进行广搜，把搜过的进行标记，那么没搜过的也不是1的就是要找的2了。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int maxLen = 1100;
int vis[maxLen][maxLen]; //判断有没有走过了
int Map[maxLen][maxLen];

int dir[4][2] = //四个方向
{
{-1, 0},
{1, 0},
{0, 1},
{0, -1}
};
struct point
{
int x, y; //位置
}in, out, beg; //入队的值，出队的值，开始的值
int n;

int check(int x, int y) //检查边界或者是否终点
{
	if(!vis[x][y] && x >= 1 && y >= 1 && x <= n && y <= n && Map[x][y] != 1)
		return 1;
	return 0;
}

void bfs()
{
	memset(vis, 0, sizeof(vis)); //刚开始哪个都没有访问
    queue<point>q;
	//下面四个for循环表示搜索最外一层，如果某个位置为0，那么就搜索，没有的话就不用了
	for(int i = 1; i <= n; i++)
	{
		if(Map[1][i] == 0)
		{
			beg.x = 1;
			beg.y = i;
			vis[beg.x][beg.y] = 1;
			q.push(beg);
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(Map[i][1] == 0)
		{
			beg.x = i;
			beg.y = 1;
			vis[beg.x][beg.y] = 1;
			q.push(beg);
		}
	}
	for(int i = 1; i < n; i++)
	{
		if(Map[i][n] == 0)
		{
			beg.x = i;
			beg.y = n;
			vis[beg.x][beg.y] = 1;
			q.push(beg);
		}
	}
	for(int i = 1; i < n; i++)
	{
		if(Map[n][i] == 0)
		{
			beg.x = n;
			beg.y = i;
			vis[beg.x][beg.y] = 1;
			q.push(beg);
		}
	}
	while(!q.empty())
	{
		out = q.front(); //将第一个元素出队
		q.pop();
		for(int i = 0; i < 4; i++) //四个方向开始走
		{
			in.x = out.x + dir[i][0];
			in.y = out.y + dir[i][1];
			if(check(in.x, in.y))
			{
				q.push(in); //入队
				vis[in.x][in.y] = 1; //访问过了
			}
		}	
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cin >> Map[i][j];
	bfs();
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(!vis[i][j] && Map[i][j] == 0) //没被访问过，同时为0，就输出2
				cout << 2 << " ";
			else
				cout << Map[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}