网易互联网笔试（3.27）

网易互联网3.27日笔试，四道笔试题一道简答题，四道笔试题AK，简答题考察设计模式不会。

第一道题模拟使用单体技能和群体技能攻击怪物的场景、第二题字符串处理、第三题构造具有限制条件的完全二叉树、第四题动态规划问题。

题目

第一题

• 题意

给定两个怪，分别具有a，b血量；给定两个技能，单体技能伤害为x，群体技能伤害为y。单体技能同时只能攻击一个怪物，群体技能可同时攻击两个怪物。问给定a、b、x、y时，最少的攻击次数。

• 临场思路

问题的关键在于什么时候使用单体技能、什么时候使用群体技能？

临场没有思考清楚这一问题，直接暴力比较三种策略（答案出自这三种策略之一）：

1. 仅使用单体技能
2. 仅使用群体技能
3. 先使用群体技能消耗直到一只怪死亡、再使用单体技能带走另一只怪。

第二题

• 题意

给定一个只包含小写字母的字符串。用户可以不限次标记连续的两个字符，要求标记的两个字符相同或者是大小相邻（值相差1）。标记字符后，可以获取字符具有的分数，a-z分别有1-26分，问最高得分是多少。

• 临场思路

顺序处理字符串，每次截取一个可标记连续子串，子串任意相邻的两个字符相同或者值大小相差1。子串存在三种情况：

1. 长度为1：无法标记。
2. 长度为大于1的偶数：可全部标记，获取所有分数。
3. 长度为大于1的奇数：需要选择一个字符放弃标记，选择的原则是该字符左右两边子串长度为偶数，且为满足这一条件的最小值。最后获取所有标记字符的分数。

第三题

• 题意

给定1-n编号的n个节点，要求构造完全二叉树，但存在一个限制条件。限制条件是，每个节点（除父节点）编号与其父节点编号的乘积为偶数。

• 临场思路

经模拟3节点、4节点、5节点等简单情况，发现内节点编号均为偶数，叶子节点均为奇数。然后直接两遍遍历1-n，第一遍输出所有偶数，第二遍输出所有奇数。

第四题

• 题意

给定一片n*m的矩阵沼泽地，需要从（0,0）位置移动到（n，m）位置，运行向左、下、右三个方向移动，并且移动会有代价，问最小代价是多少？移动代价计算方式为，若相同地型之间移动，代价为1；若在不同地形之间移动，代价为2。

• 临场思路

典型的dp问题。

定义二维数组dp[n][m]，dp[i][j]表示移动到位置（i，j）的最小代价。

可以从左、上、右三个相邻格子移动到（i，j）位置，考虑到从右边移动到（i，j）代价必定高于从上方移动，还剩下两种情况。递推公式为：dp[i][j]=min(dp[i-1][j]，dp[i][j-1]）（此公式仅表示状态之间的依赖关系）。

代码

第一题

#include "bits/stdc++.h"

using namespace std;

int method1(int a, int b, int x, int y);
int method2(int a, int b, int x, int y);
int method3(int a, int b, int x, int y);

int main()
{
	int a, b;
	int x, y;
	cin >> a >> b >> x >> y;

	int cnt = INT_MAX;
	cnt = min(cnt, method1(a, b, x, y));
	cnt = min(cnt, method2(a, b, x, y));
	cnt = min(cnt, method3(a, b, x, y));

	cout << cnt << endl;
	return 0;
}

int method1(int a, int b, int x, int y)
{
	int cnt = (a + x - 1) / x + (b + x - 1) / x;
	return cnt;
}

int method2(int a, int b, int x, int y)
{
	int cnt = 0;
	int low = min(a, b);
	int high = max(a, b);
	cnt += (low + y - 1) / y;
	cnt += (high - cnt * y + x - 1) / x;
	return cnt;
}

int method3(int a, int b, int x, int y)
{
	int cnt = max((a + y - 1), (b + y - 1)) / y;
	return cnt;
}

第二题

#include "bits/stdc++.h"

using namespace std;

int main()
{
	string str;
	cin >> str;

	int score = 0;
	int i = 0;
	while (i < str.size()) {
		int j = i + 1;
		while (j < str.size() && (str[j] == str[j - 1] || abs(str[j] - str[j - 1]) == 1))
			j++;
		for (int k = i; k < j; k++)
			score = score + str[k] - 'a' + 1;

		if ((j - i) % 2 == 1) {
			char min_char = 'z';
			for (int k = i; k < j; k++) {
				if ((k - i) % 2 == 0 && str[k] < min_char)
					min_char = str[k];
			}
			score = score - (min_char - 'a' + 1);
		}
		i = j;
	}

	cout << score << endl;

	return 0;
}

第三题

#include "bits/stdc++.h"

using namespace std;

int main()
{
	int n;
	cin >> n;
	for (int i = 2; i <= n; i += 2) {
		cout << i << ' ';
	}
	for (int i = 1; i <= n; i += 2) {
		cout << i << ' ';
	}

	return 0;
}

第四题

#include "bits/stdc++.h"

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<int>> board(n, vector<int>(m));
	vector<vector<int>> dp(n, vector<int>(m, INT_MAX));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}

	dp[0][0] = 0;
	for (int j = 1; j < m; j++) {
		dp[0][j] = dp[0][j - 1] + (board[0][j] == board[0][j - 1] ? 1 : 2);
	}
	for (int i = 1; i < n; i++) {
		dp[i][0] = dp[i - 1][0] + (board[i][0] == board[i - 1][0] ? 1 : 2);
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + (board[i - 1][j] == board[i][j] ? 1 : 2));
			dp[i][j] = min(dp[i][j], dp[i][j - 1] + (board[i][j - 1] == board[i][j] ? 1 : 2));
		}
	}

	cout << dp[n - 1][m - 1] << endl;

	return 0;
}