饰品企业网站建设,哪家公司做网站便宜,杭州仪器网站制作,怎么做网页长图第一题:全球变暖 题目描述 你有一张某海域 NxN 像素的照片#xff0c;.表示海洋、#表示陆地#xff0c;如下所示#xff1a; ....... .##.... .##.... ....##. ..####. ...###. ....... 其中上下左右四个方向上连在一起的一片陆地组成一…第一题:全球变暖 题目描述 你有一张某海域 NxN 像素的照片.表示海洋、#表示陆地如下所示 ....... .##.... .##.... ....##. ..####. ...###. ....... 其中上下左右四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。 由于全球变暖导致了海面上升科学家预测未来几十年岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)它就会被淹没。 例如上图中的海域未来会变成如下样子 ....... ....... ....... ....... ....#.. ....... ....... 请你计算依照科学家的预测照片中有多少岛屿会被完全淹没。 输入描述 第一行包含一个整数 N (1≤N≤1000)。 以下 N 行 N 列代表一张海域照片。 照片保证第 1 行、第 1 列的像素都是海洋。、 输出一个整数表示答案。 输入输出样例 示例 输入 7
.......
.##....
.##....
....##.
..####.
...###.
.......输出 1 dfs岛屿问题
一个岛屿不会被淹没要有一块大陆上下左右都不和海洋相邻
flag表示一个岛屿中有一块大陆是这样的就不需要再遍历了
其余情况继续遍历并且把对应变成海洋这里用*来代替就不用开状态数组了
#includeiostream
#includequeue
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(){cinn;for(int i 1; i n; i)for(int j 1; j n; j)cing[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);}coutolds-newsendl;return 0;
} 新的方法叫什么弗拉基米得算法通过这可以遍历到每个连通块中的各个陆地
首先遍历如果当前没有被遍历而且为陆地比较边界数量和总数量得值如果相等即要被淹没所以就要加进去
然后是一个BFS,使用stl队列实现如果该陆地相邻有海洋那么他就是边界
是陆地而且没有遍历过的话就放进队列再找
#includeiostream
#includequeue
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){queuepairint, 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(){cinn;for(int i 1; i n; i)for(int j 1; j n; j)cing[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;}coutcntendl; return 0;
}
第四题搬砖 问题描述 这天小明在搬砖。 他一共有 n 块砖, 他发现第 i 砖的重量为 wi, 价值为 vi 。他突然想从这些 砖中选一些出来从下到上堆成一座塔, 并且对于塔中的每一块砖来说, 它上面 所有砖的重量和不能超过它自身的价值。 他想知道这样堆成的塔的总价值即塔中所有砖块的价值和最大是多少。 输入格式 输入共 n1 行, 第一行为一个正整数 n, 表示砖块的数量。 后面 n 行, 每行两个正整数 wi,vi 分别表示每块砖的重量和价值。 输出格式 一行, 一个整数表示答案。 样例说明 选择第 1、2、4块砖, 从上到下按照 2、1、4 的顺序堆成一座塔, 总价值 为 41510 评测用例规模与约定 对于 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 因为题目范围
#includeiostream
#includealgorithm
using namespace std;typedef pairint, 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(){cinn;for(int i 0; i n ; i){int w, v;cinwv;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]);coutmaxvendl;return 0;
}
