网易2023春招-通用技术（第一批）3-27 笔试

第一题打怪

题意：有两个怪，血量分别是 a 、 b 。你一次可以选择攻击其中一个造成 x 伤害，或者同时对两个造成 y 伤害。

这个题应该有O（1）的贪心做法，但是数据范围只有 20，所以直接dfs开剪~

#include<bits/stdc++.h>
using namespace std;

int res = 1000000000;

void dfs(int a , int b ,int x ,int y,int cnt) {
    if (a <= 0 && b <= 0) {
        res = min(res,cnt);
        return;
    }
    if (cnt >= res) return;
    if ((a > 0) && (b > 0)) {
        dfs(a-y,b-y,x,y,cnt+1);
    }
    if (!(x <= y)) {
        if (a > 0) {
            dfs(a-x,b,x,y,cnt+1);
        }
        if (b > 0) {
            dfs(a,b-x,x,y,cnt+1);
        }
    }
}

int main() {
    int a , b , x , y ;
    scanf("%d%d%d%d",&a,&b,&x,&y);
    dfs(a,b,x,y,0);
    printf("%d\n",res);
}

第二题字符串得分

题意：有一个字符串，你可以选择两个相邻的字符串（需要满足字典序也相邻或相等）然后得到他俩的积分，积分计算规则是 $s_i-a+1$ 。

这个看数据范围（好像是2e5记不清了）和题意，一眼动态规划。
设

$dp[i][0]$ 从 $str_0$ 到 $str_i$ 且不消除 $str_i$ 的最高得分。
$dp[i][1]$ 从 $str_0$ 到 $str_i$ 且消除 $str_i$ 的最高得分（实际上需要同时消除 $str_i$ 和 $str_{i-1}$ ）。

$str_i$ 和 $str_{i-1}$ 字典序相邻\相等，可以选择是否消除 $str_i$ ，则有状态转移方程式 $dp[i][0] = max(dp[i-1][0],dp[i-1][1])$
$dp[i][1] = max(dp[i-1][0]+str[i]-'a'+1+str[i-1]-'a'+1,max(dp[i-2][1],dp[i-2][0])+str[i]-'a'+1+str[i-1]-'a'+1);$
$str_i$ 和 $str_{i-1}$ 字典序不相邻\相等，就不可以选择是否消除（无法消除） $dp[i][0/1] = max(dp[i-1][0],dp[i-1][1])$

#include<bits/stdc++.h>
using namespace std;

string str;
int dp[210000][2];

int main() {
    cin >> str;
    int n = str.length();
    if (abs(str[1]-str[0]) <= 1) {
        dp[1][1] = str[0]-'a'+1+str[1]-'a'+1;
    }
    for (int i = 2 ; i < n ; i ++) {
        if (abs(str[i]-str[i-1]) <= 1) {
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]); // 不选这个
            dp[i][1] = max(dp[i-1][0]+str[i]-'a'+1+str[i-1]-'a'+1,max(dp[i-2][1],dp[i-2][0])+str[i]-'a'+1+str[i-1]-'a'+1);
        } else {
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = max(dp[i-1][0],dp[i-1][1]);
        }
    }

    printf("%d\n",max(dp[n-1][0],dp[n-1][1]));
}

第三题构造树

题意：构造一棵节点值是 1~n 的完全树，其树上所有节点和父节点之积都是偶数。返回层序遍历结果

构造的思路：如果树的层数是偶数（如果叶子节点层不满就不算），就把所有的奇数层填满偶数，否则在偶数层填满偶数，由于前面没有考虑叶子节点，因此再把叶子节点的父节点都填为偶数即可，剩下的节点随意构造。这个构造思路应该是可以证明正确的（我没有进行严格的数学证明，只做了几个简单的样例测试）

-- 这个题居然一次a过了，难以置信

#include<bits/stdc++.h>
using namespace std;

int n;

int main() {
    scanf("%d",&n);
    int level = log2(n+1);
    int leaves = n-(1<<level)+1;
    vector<vector<int> > tree(level+1);
    int cnt = 1;
    for (int i = 0 ; i < level ; i ++) {
        vector<int> tmp(cnt,0);
        tree[i] = tmp;
        cnt <<= 1;
    }
    vector<int> _tmp(leaves,0);
    tree[level]=_tmp;
    int even = 0 , odd = 0;
    if (level%2 == 0) {
        for (int i = 0 ; i < level ; i += 2) {
            for (int j = 0 ; j < tree[i].size() ; j ++) {
                tree[i][j] = (++even)*2;
            }
        }
    } else {
        for (int i = 1 ; i < level ; i += 2) {
            for (int j = 0 ; j < tree[i].size() ; j ++)  {
                tree[i][j] = (++even)*2;
            }
        }
    }
    for (int i = 0 ; i < (leaves+1)/2 ; i ++) {
        if (tree[level-1][i] == 0) {
            tree[level-1][i] = (++even)*2;
        }
    }
    for (int i = 0 ; i < level ; i ++) {
        for (int j = 0 ; j < tree[i].size() ; j ++) {
            if (tree[i][j] == 0) {
                int tmp = (++even)*2;
                if(tmp > n) {
                    tmp = (++odd)*2-1;
                }
                tree[i][j] = tmp;
            }
        }
    }
    for (int i = 0 ; i < leaves ; i ++) {
        if (tree[level][i] == 0) {
            int tmp = (++even)*2;
            if(tmp > n) {
                tmp = (++odd)*2-1;
            }
            tree[level][i] = tmp;
        }
    }
    for (int i = 0 ; i < level ; i ++) {
        for (int j = 0 ; j < tree[i].size() ; j ++) {
            printf("%d ",tree[i][j]);
        }
    }
    for (int i = 0 ; i < leaves ; i ++) {
        printf("%d ",tree[level][i]);
    }
}

第四题沼泽（没有全部通过）

题意：有一个二维矩阵，上面只有 0 和 1，只能上下左右移动，如果移动前后的元素值相同，则耗费 1 ，否则耗费 2。问从左上到右下的最小耗费。

当时一眼觉得bfs能蒙过去（然后过了50%），交完后想可能是要拆边bfs。wa了之后想了一下dij（脑抽又给否掉了），这题应该就是一个最短路的裸题，可能是下午脑子不太清醒吧，没过完~~（总之就是非常后悔）~~ 。估计用网络流 mcmf 也能过，但是没法手写，所以当时也就没试。

这个代码仅通过50%

#include<bits/stdc++.h>
using namespace std;

int grid[510][510] , dis[510][510] , detx[4] = {-1,0,1,0} , dety[4] = {0,1,0,-1};
int n , m , res = 1000000000;
struct node
{
    int x , y , cnt;
    /* data */
};


int main() {
    scanf("%d%d",&n,&m);
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < m ; j ++) {
            scanf("%d",&grid[i][j]);
            dis[i][j] = 1000000000;
        }
    }
    queue<node> q;
    q.push({0,0,0});
    while(!q.empty()) {
        auto crt = q.front();
        q.pop();
        if (crt.cnt >= res) continue;
        if (crt.x == n-1 && crt.y == m-1) {
            res = crt.cnt;
            continue;
        }
        int x = crt.x , y = crt.y ;
        for (int i = 0 ; i < 4 ; i ++) {
            int xx = x + detx[i] , yy = y + dety[i];
            if (xx < n && xx >= 0 && yy < n && yy >= 0) {
                int cost = crt.cnt+1+abs(grid[xx][yy]-grid[x][y]);
                if (cost >= dis[xx][yy]) continue;
                dis[xx][yy] = cost;
                q.push({xx,yy,cost});
            }
        }
    }
    printf("%d\n",res);
}

总结

编程题整体难度不算高。
第一题虽然正解应该比较难想到，但是dfs还是很容易就剪过去了，感谢出题人高抬贵手。
第二题很明显的dp，想到了dp还是很容易的，之前笔试做过类似的题，在牛客的动态规划专栏也做过类似的，如果多刷刷动态规划的题单应该没啥问题，二十分钟之类就a掉了。
第三题构造如果数学功底和数据结构功底不太扎实应该是比较难想到，有时候写算法题也不用严格证明，简单的证明+一定的直觉+一点点码力交上去试试又不要钱。
第四题让我后悔交太早，如果写了个dij应该是满分了，可惜。~~总之就是非常后悔~~

#网易##笔试题目##实习##春招##C/C++##Java#