第一題:全球變暖

題目描述

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

.......

.##....

.##....

....##.

..####.

...###.

.......

其中"上下左右"四個(gè)方向上連在一起的一片陸地組成一座島嶼。例如上圖就有 2 座島嶼。

由于全球變暖導(dǎo)致了海面上升，科學(xué)家預(yù)測(cè)未來(lái)幾十年，島嶼邊緣一個(gè)像素的范圍會(huì)被海水淹沒(méi)。具體來(lái)說(shuō)如果一塊陸地像素與海洋相鄰(上下左右四個(gè)相鄰像素中有海洋)，它就會(huì)被淹沒(méi)。

例如上圖中的海域未來(lái)會(huì)變成如下樣子：

.......

.......

.......

.......

....#..

.......

.......

請(qǐng)你計(jì)算：依照科學(xué)家的預(yù)測(cè)，照片中有多少島嶼會(huì)被完全淹沒(méi)。

輸入描述

第一行包含一個(gè)整數(shù) N?(1≤N≤1000)。

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

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

輸出一個(gè)整數(shù)表示答案。

輸入輸出樣例

示例

輸入

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

輸出

1

?dfs，島嶼問(wèn)題

一個(gè)島嶼不會(huì)被淹沒(méi)，要有一塊大陸上下左右都不和海洋相鄰

flag表示一個(gè)島嶼中有一塊大陸是這樣的，就不需要再遍歷了

其余情況繼續(xù)遍歷，并且把對(duì)應(yīng)變成海洋，這里用*來(lái)代替，就不用開(kāi)狀態(tài)數(shù)組了

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

?新的方法，叫什么弗拉基米得算法，通過(guò)這可以遍歷到每個(gè)連通塊中的各個(gè)陸地

首先遍歷，如果當(dāng)前沒(méi)有被遍歷，而且為陸地，比較邊界數(shù)量和總數(shù)量得值，如果相等，即要被淹沒(méi)，所以就要加進(jìn)去

然后是一個(gè)BFS,使用stl隊(duì)列實(shí)現(xiàn)，如果該陸地相鄰有海洋，那么他就是邊界

是陸地而且沒(méi)有遍歷過(guò)的話，就放進(jìn)隊(duì)列再找

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

第四題：搬磚

問(wèn)題描述

這天，小明在搬磚。

他一共有?n?塊磚, 他發(fā)現(xiàn)第?i?磚的重量為 wi?, 價(jià)值為 vi??。他突然想從這些 磚中選一些出來(lái)從下到上堆成一座塔, 并且對(duì)于塔中的每一塊磚來(lái)說(shuō), 它上面 所有磚的重量和不能超過(guò)它自身的價(jià)值。

他想知道這樣堆成的塔的總價(jià)值（即塔中所有磚塊的價(jià)值和）最大是多少。

輸入格式

輸入共 n+1?行, 第一行為一個(gè)正整數(shù)?n, 表示磚塊的數(shù)量。

后面?n?行, 每行兩個(gè)正整數(shù) wi?,vi??分別表示每塊磚的重量和價(jià)值。

輸出格式

一行, 一個(gè)整數(shù)表示答案。

樣例說(shuō)明

選擇第?1、2、4塊磚, 從上到下按照?2、1、4 的順序堆成一座塔, 總價(jià)值 為?4+1+5=10

評(píng)測(cè)用例規(guī)模與約定

對(duì)于?20%?的數(shù)據(jù), 保證 0n≤10;

對(duì)于?100%?的數(shù)據(jù), 保證 n≤1000;wi?≤20;vi?≤20000?。

樣例輸入

5
4 4
1 1
5 2
5 5
4 3

樣例輸出

10

明確排序指標(biāo)很關(guān)鍵，這是數(shù)學(xué)，要推導(dǎo)和多做題

然后剩下就是01背包問(wèn)題了，直接套模板

j <= 2000 因?yàn)轭}目范圍文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-407744.html

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

到了這里，關(guān)于藍(lán)橋杯刷題第二十五天的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！