蓝桥杯刷题第二十五天

第一题:全球变暖

题目描述

你有一张某海域 NxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：

.......

.##....

.##....

....##.

..####.

...###.

.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......

.......

.......

.......

....#..

.......

.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入描述

第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列的像素都是海洋。、

输出一个整数表示答案。

输入输出样例

示例

输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出

1

 dfs，岛屿问题

一个岛屿不会被淹没，要有一块大陆上下左右都不和海洋相邻

flag表示一个岛屿中有一块大陆是这样的，就不需要再遍历了

其余情况继续遍历，并且把对应变成海洋，这里用*来代替，就不用开状态数组了

#include<iostream>
#include<queue>
using namespace std;const int N = 1010;
char g[N][N];
int n, cnt, olds, news;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
bool flag;void dfs(int u, int v){if(!flag) {cnt = 0;for(int i = 0; i < 4; i++){int x = dx[i] + u, y = dy[i] + v;if(g[x][y] != '.') cnt++;}if(cnt == 4) {news++;flag = true;}}g[u][v] = '*';for(int i = 0; i < 4; i++){int x = dx[i] + u, y = dy[i] + v;if(x >= 1 && x <= n && y >= 1 && y <= n && g[x][y] == '#')dfs(x, y);}}int main(){cin>>n;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)cin>>g[i][j];for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(g[i][j] == '#'){olds++;flag = false;dfs(i ,j);}cout<<olds-news<<endl;return 0;
}

 新的方法，叫什么弗拉基米得算法，通过这可以遍历到每个连通块中的各个陆地

首先遍历，如果当前没有被遍历，而且为陆地，比较边界数量和总数量得值，如果相等，即要被淹没，所以就要加进去

然后是一个BFS,使用stl队列实现，如果该陆地相邻有海洋，那么他就是边界

是陆地而且没有遍历过的话，就放进队列再找

#include<iostream>
#include<queue>
using namespace std;const int N = 1010;
char g[N][N];
bool st[N][N];
int n;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};void dfs(int ax,int ay, int& total, int& bound){queue<pair<int, int>> q;q.push({ax, ay});st[ax][ay] = true;while(q.size()){auto t = q.front();q.pop();total++;bool is_bound = false;for(int i = 0; i < 4; i++){int x = t.first + dx[i], y = t.second + dy[i];if(x < 1 || x > n && y < 1 || y > n ) continue;if(st[x][y]) continue;if(g[x][y] == '.'){is_bound = true;continue;}q.push({x, y});st[x][y] = true;}if(is_bound) bound++;}}int main(){cin>>n;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)cin>>g[i][j];int cnt = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(!st[i][j] && g[i][j] == '#'){int total = 0, bound = 0;dfs(i ,j ,total, bound);if(total == bound)cnt++;}cout<<cnt<<endl;  return 0;
}

第四题：搬砖

问题描述

这天，小明在搬砖。

他一共有 n 块砖, 他发现第 i 砖的重量为 wi​, 价值为 vi​ 。他突然想从这些 砖中选一些出来从下到上堆成一座塔, 并且对于塔中的每一块砖来说, 它上面 所有砖的重量和不能超过它自身的价值。

他想知道这样堆成的塔的总价值（即塔中所有砖块的价值和）最大是多少。

输入格式

输入共 n+1 行, 第一行为一个正整数 n, 表示砖块的数量。

后面 n 行, 每行两个正整数 wi​,vi​ 分别表示每块砖的重量和价值。

输出格式

一行, 一个整数表示答案。

样例说明

选择第 1、2、4块砖, 从上到下按照 2、1、4 的顺序堆成一座塔, 总价值 为 4+1+5=10

评测用例规模与约定

对于 20% 的数据, 保证 0n≤10;

对于 100% 的数据, 保证 n≤1000;wi​≤20;vi​≤20000 。

样例输入

5
4 4
1 1
5 2
5 5
4 3

样例输出

10

明确排序指标很关键，这是数学，要推导和多做题

然后剩下就是01背包问题了，直接套模板

j <= 2000 因为题目范围

#include<iostream>
#include<algorithm>
using namespace std;typedef pair<int, int> PII;
const int N = 1010;
PII a[N];
int n, f[20004];bool cmp(PII x, PII y){return x.first + x.second < y.first + y.second;
}int main(){cin>>n;for(int i = 0; i < n ; i++){int w, v;cin>>w>>v;a[i] = {w, v};}sort(a, a + n, cmp);for(int i = 0; i < n; i++){int w = a[i].first, v = a[i].second;for(int j = 20000; j >= w; j--)if(v >= j - w) f[j] = max(f[j], f[j - w] + v);}int maxv = 0;for(int i = 0; i <= 20000; i++) maxv = max(maxv, f[i]);cout<<maxv<<endl;return 0;
}