3.27 网易互联网笔试

网易互联网笔试（3.27）网易互联网3.27日笔试，四道笔试题一道简答题，四道笔试题AK，简答题考察设计模式不会。
第一道题模拟使用单体技能和群体技能攻击怪物的场景、第二题字符串处理、第三题构造具有限制条件的完全二叉树、第四题动态规划问题。
题目第一题

题意

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

临场思路

问题的关键在于什么时候使用单体技能、什么时候使用群体技能？
临场没有思考清楚这一问题，直接暴力比较三种策略（答案出自这三种策略之一）：

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

第二题

题意

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

临场思路

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

长度为1：无法标记。
长度为大于1的偶数：可全部标记，获取所有分数。
长度为大于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;}

第四题【3.27 网易互联网笔试】

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