2022.3.27网易后端暑期实习笔试题解（转载）
原地址：
个人加注释：
1.编程题第一题：小红杀怪
方法一：枚举
思路：枚举使用烈焰风暴（群体技能）的次数，然后可以O(1)算出需要使用火球术（单体技能）的次数。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x, y, a, b, i; // 这里x和y是血量，a和b是技能伤害
cin >> x >> y >> a >> b;
int ma = 1e9;
for (i = 0; i <= 1e6; i++)
{
int c1 = 0, c2 = 0;
if ((x - i * b) > 0)
c1 = max(c1, (x - i * b) / a + ((x - i * b) % a != 0));
if ((y - i * b) > 0)
c2 = max(c2, (y - i * b) / a + ((y - i * b) % a != 0));
ma = min(ma, i + c1 + c2);
}
cout << ma;
}
方法二：贪心（根据x和y的大小关系进行分类讨论）
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x, y, a, b, i;
cin >> a >> b >> x >> y; // 这里a和b是血量，x和y是技能伤害
if (y >= max(a, b))
cout << 1;
else if (y > x) // 群体技能比单体技能伤害还要高
{
a = max(a, b);
// (a % y != 0) == 0 表示a / y除尽了，加0；== 1 表示还需要用一次技能，则加1（下同）
cout << a / y + (a % y != 0);
}
else if (x > 2 * y) // 单体技能伤害量超过群体伤害的两倍（两个怪），此时分别使用数次单体技能
{
cout << a / x + b / x + (a % x != 0) + (b % x != 0);
}
else // y <= x <= 2 * y
{
if (a > b) swap(a, b); // 使得下叙的a <= b
int cnt = a / y + (a % y != 0); // 首先对较少血量的a使用多少次群体技能
b -= y * cnt; // 因为是群体技能，所以b也减少了这么多血量
cout << b / x + (b % x != 0) + cnt; // b剩下了的血量用单体技能，加上cnt就是答案
}
return 0; // 本人加上
}
2.编程题第二题：字符串得分
思路：使用动态规划，f[n]表示字符串前n个字符所能得到的最大得分。
#include <iostream>
#include <vector>
using namespace std;
string s;
int main() {
cin >> s;
int n = s.size();
vector<int> f(n, 0);
if (n < 2) {
cout << 0 << endl;
return 0;
}
// f[0] = 0, 初始化f[1]
if (s[1] == s[0] || abs(s[1] - s[0]) == 1) {
f[1] = s[1] - 'a' + s[0] - 'a' + 2;
}
int ans = f[1];
for (int i = 2; i < n; i ++ ) {
f[i] = f[i - 1]; // 先更新f[i]
if (s[i] == s[i - 1] || abs(s[i] - s[i - 1]) == 1) { // 如果s[i]和s[i - 1]之间有故事
// 更新s[i]，不需要状态数组
f[i] = max(f[i], f[i - 2] + s[i] - 'a' + s[i - 1] - 'a' + 2);
}
ans = max(ans, f[i]);
}
cout << ans << endl;
return 0;
}
4.编程题第四题：小红闯沼泽地
思路：求最短路（dijkstra算法），难点在于怎么构建图。
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int dx[] = {1, 0, 0}; // 定义dx，dy偏移量;
const int dy[] = {0, 1, -1}; // {1, 0}为下，{0, 1}为右，{0, -1}为左
const int N = 503;
struct Node
{
int x, y, w;
bool operator<(const Node &b) const { return w > b.w; } // 比较函数
};
int n, m;
int a[N][N];
priority_queue<Node> q; // 优先队列是按w小的优先出队
int d[N][N];
bool vis[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cin >> a[i][j]; // 构造地图
}
}
memset(d, 0x3f, sizeof(d));
d[1][1] = 0;
q.push({1, 1});
while (q.size())
{
int x = q.top().x, y = q.top().y;
q.pop();
if (vis[x][y])
continue;
vis[x][y] = true;
for (int i = 0; i < 3; ++i)
{
int tx = dx[i] + x, ty = dy[i] + y;
int w = (a[x][y] ^ a[tx][ty]) ? 2 : 1; // 用异或操作得到跨越两块区域所花的时间
if (tx && ty && tx <= n && ty <= m) // 点{tx, ty}没有出界
{
if (d[tx][ty] > d[x][y] + w) // dijstra中的更新距离方法，贪心保证最短距离
{
d[tx][ty] = d[x][y] + w;
q.push((Node){tx, ty, d[tx][ty]});
}
}
}
}
cout << d[n][m] << endl;
return 0;
}
