【网易笔试】【2022.3.27】

傷城~ 2023-09-30 11:43 15阅读 0赞

这场挺简单，AK人挺多，我的解答放下面了，全100%AC  
题目不记得了 牛客搜到的题目来源。

> 作者：牛客408632512号  
> 链接：https://www.nowcoder.com/discuss/916037?type=post&order=time&pos=&page=1&ncTraceId=&channel=-1&source\_id=search\_post\_nctrack  
> 来源：牛客网

> 1、第一题是打怪游戏，给A,B,X,Y四个值，其中A和B分别代表两个怪物的血量，X和Y分别代表两个技能对怪物造成的伤害，不同的是，X是单体伤害，Y是群体伤害（对A和B都造成Y伤害），求杀死（A和B小于等于0）两只怪物所需的最小技能数

#include "algorithm"
    #include "iostream"
    #include "unordered_map"
    #include "vector"
    using namespace std;
    // 100%
    int main() {
        
      int a, b, x, y;
      cin >> a >> b >> x >> y;
      int count = 0;
    
      while (a > 0 || b > 0) {
        
        count++;
        int sum = 0;
        if (a > 0)
          sum += a;
        if (b > 0)
          sum += b;
    
        int nextAoeSum = 0;
        if (a - y > 0)
          nextAoeSum += (a - y);
        if (b - y > 0)
          nextAoeSum += (b - y);
    
        int nextA = a - x;
        if (nextA < 0)
          nextA = 0;
        int nextB = b - x;
        if (nextB < 0)
          nextB = 0;
        int nextsoloA = b > 0 ? nextA + b : nextA;
        int nextsoloB = a > 0 ? nextB + a : nextB;
    
        if (nextAoeSum == min(nextAoeSum, min(nextsoloA, nextsoloB))){
        
          a -= y;
          b -= y;
        } else if (min(nextAoeSum, min(nextsoloA, nextsoloB))== nextsoloA) {
        
          a -= x;
        }else{
        
          b -= x;
        }
      }
    
      cout << count << endl;
    }

> 2、第二题是给出一个字母字符串，如果相邻两个字母相同或者在字母表中相邻，则标记这两个字母，并把这两个字母的分数加到你获得的分数中，‘a’等于1，‘b’等于2，以此类推，要求被标记过的不能再使用

#include "algorithm"
    #include "iostream"
    #include "unordered_map"
    #include "vector"
    using namespace std;
    //100%
    inline int score(char ch){
        
      return ch - 'a' + 1;
    }
    inline bool canLable(char a,char b){
        
      return a == b || a + 1 == b || a - 1 == b;
    }
    int main() {
        
      string s;
      cin >> s;
    
      int dp[200005][2] = {
        0};
      for (int i = 1; i < s.length(); i++)
      {
        
        //计算s[i]与前一个标记、不标记的值,存入dp[i][0]\dp[i][1]
        
        //do not lable
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);
    
        //lable 
        if(!canLable(s[i],s[i-1])){
        
          dp[i][0] = -1;
        }else{
        
          // dp[i][0] = max(dp[i][1], dp[i - 1][1] + score(s[i]) + score(s[i - 1]));
          dp[i][0] = dp[i - 1][1] + score(s[i - 1]) + score(s[i]);
        }
      }
      cout << max(dp[s.length() - 1][0], dp[s.length() - 1][1]) << endl;
    }

> 3、第三题是给出一个数字n，要求利用1~n这n个数字构建一个完全二叉树，它有这样一个要求，父节点和子节点的乘积为偶数，返回这棵树层序遍历的结果

#include "algorithm"
    #include "iostream"
    #include "unordered_map"
    #include "vector"
    using namespace std;
    // int tree[100005];
    //100%
    int main(){
        
      int n;
      cin >> n;
    
      for (size_t i = 2; i <= n; i += 2)
      {
        
        if(i==2)
          cout << i ;
        else
          cout << " " << i;
      }
      
      for (int i = 1; i <= n; i += 2)
      {
        
        cout<< " " << i;
      }
      cout << endl;
    }

> 4、第五题是一个经典dp沼泽问题，一个人在地图的左上方，要求走到右下方，这个地图其中有沼泽有平地，给定一个二维数组，0代表平地，1代表沼泽，规定，从沼泽到平地或平地到沼泽耗时为2，从平地到平地，沼泽到沼泽耗时为1，从左上方出发，每次可以向左，右，下走一格，要求算出从左上到右下获得分数最少的走法的步数

#include "algorithm"
    #include "iostream"
    #include "unordered_map"
    #include "vector"
    // 100%
    using namespace std;
    inline int move(int a, int b) {
        
      return a == b ? 1 : 2;
    }
    int main() {
        
      int n, m;
      cin >> n >> m;
      int map[505][505];
      int dp[505][505];
      for (int i = 0; i < n; i++) {
        
        for (size_t j = 0; j < m; j++) {
        
          cin >> map[i][j];
        }
      }
    
      for (int i = 0; i < n; i++) {
        
        for (size_t j = 0; j < m; j++) {
        
          if (i == 0 && j == 0) {
        
            dp[i][j] = 0;
          } else if (i == 0) {
        
            dp[i][j] = dp[i][j - 1] + move(map[i][j - 1], map[i][j]);
          } else if (j == 0) {
        
            dp[i][j] = dp[i - 1][j] + move(map[i - 1][j], map[i][j]);
          } else {
        
            dp[i][j] = min(dp[i][j - 1] + move(map[i][j - 1], map[i][j]),
                           dp[i - 1][j] + move(map[i-1][j], map[i][j]));
          }
    
      cout << dp[n - 1][m - 1] << endl;
    }