网易互联网笔试（3.27）
网易互联网笔试（3.27）
网易互联网3.27日笔试，四道笔试题一道简答题，四道笔试题AK，简答题考察设计模式不会。
创新互联建站专注为客户提供全方位的互联网综合服务，包含不限于成都网站建设、做网站、米脂网络推广、小程序定制开发、米脂网络营销、米脂企业策划、米脂品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联建站为所有大学生创业者提供米脂建站搭建服务，24小时服务热线：18980820575，官方网址：www.cdcxhl.com
第一道题模拟使用单体技能和群体技能攻击怪物的场景、第二题字符串处理、第三题构造具有限制条件的完全二叉树、第四题动态规划问题。
题目
第一题
- 题意
给定两个怪，分别具有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;
}
第四题
#include "bits/stdc++.h"
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector> board(n, vector(m));
vector> dp(n, vector(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;
}
新闻名称：网易互联网笔试（3.27）
网址分享：http://scjbc.cn/article/dsoihsg.html
