0%

网易2018校园招聘编程题真题集合题解

这套题题意比较难转化,耐心思考加上以前的练习ak不是问题。


A

题面

小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。
魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币
魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币
小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。

时间复杂度$O(\log(n))$

题解

显然,从机器1出来的结果肯定是奇数,从机器2出来的结果肯定是偶数。那么就可以倒推一下,直到魔法币的结果等于0。

得出来的字符串记得要reverse一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Main();
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie();
Main();
return 0;
}

void Main() {
int n; cin >> n;
string s;
while(n) {
if(n & 1) {
s += "1";
n = (n - 1) / 2;
} else {
s += "2";
n = (n - 2) / 2;
}
}
reverse(s.begin(), s.end());
cout << s << '\n';
}

B

题面

为了得到一个数的”相反数”,我们将这个数的数字顺序颠倒,然后再加上原先的数得到”相反数”。例如,为了得到1325的”相反数”,首先我们将该数的数字顺序颠倒,我们得到5231,之后再加上原先的数,我们得到5231+1325=6556.如果颠倒之后的数字有前缀零,前缀零将会被忽略。例如n = 100, 颠倒之后是1.

时间复杂度$O(\log(n))$

题解

模拟一下就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Main();
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie();
Main();
return 0;
}

int rev(int x) {
int ret = 0;
while(x) {
ret = ret * 10 + x % 10;
x /= 10;
}
return ret;
}

void Main() {
int n;
cin >> n;
cout << rev(n) + n << '\n';
}

C

题面

一个由小写字母组成的字符串可以看成一些同一字母的最大碎片组成的。例如,”aaabbaaac”是由下面碎片组成的:’aaa’,’bb’,’c’。牛牛现在给定一个字符串,请你帮助计算这个字符串的所有碎片的平均长度是多少。

时间复杂度$O(n)$

题解

模拟一下就可以了。(好像我上面也是这么说的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#ifdef ConanYu
#include "E:\yuzining\code\local.hpp"
#else
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) do { } while(false)
void Main();
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie();
Main();
return 0;
}
#endif

void Main() {
string s; cin >> s;
const int n = s.size();
int cnt = 0;
for(int i = 0; i < n;) {
int j = i;
while(j < n && s[i] == s[j]) j++;
cnt++;
i = j;
}
cout << fixed << setprecision(2) << 1.0 * n / cnt << '\n';
}

D

题面

魔法王国一共有n个城市,编号为0~n-1号,n个城市之间的道路连接起来恰好构成一棵树。
小易现在在0号城市,每次行动小易会从当前所在的城市走到与其相邻的一个城市,小易最多能行动L次。
如果小易到达过某个城市就视为小易游历过这个城市了,小易现在要制定好的旅游计划使他能游历最多的城市,请你帮他计算一下他最多能游历过多少个城市(注意0号城市已经游历了,游历过的城市不重复计算)。

题解

这题比较有意思。

如果考虑每一条边只走一次,那么最多只能走到以0为根深度最大的节点。

已经考虑完这一条最长的链之后,如果需要走多一个点,这个时候肯定只需要走两次即可(除非点太少了,$l$太大了)。

这样就很容易找到最优解了。

画下图会更好理解一点。

时间复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#ifdef ConanYu
#include "E:\yuzining\code\local.hpp"
#else
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) do { } while(false)
void Main();
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie();
Main();
return 0;
}
#endif

vector<int> edg[55];
int dep[55];
void dfs(int u) {
for(int i = 0; i < int(edg[u].size()); i++) {
const int v = edg[u][i];
dep[v] = dep[u] + 1;
dfs(v);
}
}

void Main() {
int n, l; cin >> n >> l;
for(int i = 1; i <= n; i++) {
int fa; cin >> fa;
edg[fa].push_back(i);
}
dep[0] = 1;
dfs(0);
int ans = 1;
for(int i = 0; i < n; i++) {
ans = max(ans, dep[i] + (l - dep[i] + 1) / 2);
}
cout << min(ans, l + 1) << '\n';
}

E

题面

小易有一个长度为$N$的正整数数列$A = {A[1], A[2], A[3]…, A[N]}$。
牛博士给小易出了一个难题:
对数列A进行重新排列,使数列A满足所有的$A[i] \cdot A[i + 1](1 \le i \le N - 1)$都是$4$的倍数。
小易现在需要判断一个数列是否可以重排之后满足牛博士的要求。

时间复杂度$O(n)$

题解

将数组里面的每一个数分成3类——奇数、偶数但不是4的倍数、4的倍数。

那么结果就只和这三类数各自的数量有关。

于是第二类的旁边一定是第二类或者是第三类,第一类的旁边一定是第三类。

显然贪心地想,第一个位置放第二类的数,然后第二个位置也放第二类的数,这样消耗的第三类的数就会少,然后第三类的数和第一类的数轮流存放即可(因为别无办法)。

当然如果没有第二类的数,那么第一个位置就可以放第一类的数,这样消耗的第三类的数就会少,然后又可以轮流存放。

如果一直放发现没有第三类数的情况下,那么就不能满足要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Main();
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie();
Main();
return 0;
}

void Main() {
int T; cin >> T;
while(T--) {
int a = 0, b = 0, c = 0;
int n; cin >> n;
for(int i = 0; i < n; i++) {
int t; cin >> t;
if(t % 2) a++;
else if(t % 2 == 0 && t % 4 != 0) b++;
else c++;
}
bool ok = true;
bool res = true;
for(int i = 0; i < n; i++) {
if(b) {
b--;
ok = false;
} else if(ok && a) {
a--;
ok = false;
} else if(c) {
c--;
ok = true;
} else {
res = false;
break;
}
}
cout << (res ? "Yes\n" : "No\n");
}
}

F

题面

一个合法的括号匹配序列被定义为:

  1. 空串””是合法的括号序列
  2. 如果”X”和”Y”是合法的序列,那么”XY”也是一个合法的括号序列
  3. 如果”X”是一个合法的序列,那么”(X)”也是一个合法的括号序列
  4. 每个合法的括号序列都可以由上面的规则生成

例如””, “()”, “()()()”, “(()())”, “(((()))”都是合法的。
从一个字符串S中移除零个或者多个字符得到的序列称为S的子序列。
例如”abcde”的子序列有”abe”,””,”abcde”等。
定义LCS(S,T)为字符串S和字符串T最长公共子序列的长度,即> 一个最长的序列W既是S的子序列也是T的子序列的长度。
小易给出一个合法的括号匹配序列s,小易希望你能找出具有以下特征的括号序列t:
1、t跟s不同,但是长度相同
2、t也是一个合法的括号匹配序列
3、LCS(s, t)是满足上述两个条件的t中最大的
因为这样的t可能存在多个,小易需要你计算出满足条件的t有多少个。

如样例所示: s = “(())()”,跟字符串s长度相同的合法括号匹配序列有:
“()(())”, “((()))”, “()()()”, “(()())”,其中LCS( “(())()”, “()(())” )为4,其他三个都为5,所以输出3.

题解

仔细一考虑就会发现,每一个字符串$s$中满足条件的字符串$t$,$LCS(s,t)$最大为$len(s)-1$或者不存在。

那么很显然字符串$s$其中的$len(s)-1$不需要移动,而让其中一个字符串向左或者向右移动,这样得到的字符串$t$有$LCS(s,t)\ge len(s)-1$。当$LCS(s,t)=len(s)$时代表$s=t$,不符合题意去掉即可。

这样这种字符串最多只有$O(len(s)^{2})$个。

然后对于这些字符串检查一下是否是合法的括号序列,并且进行去重操作。

去重操作我使用了set,复杂度稳定,能过,省事。也可以用vector存起来所有符合条件的字符串,然后将字符串排序之后使用unique函数,常熟比set小,但是这样不太省事。

时间复杂度$O(n^3\log(n))$,$n$代表字符串$s$的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Main();
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie();
Main();
return 0;
}

bool chk(const string& s) {
const int n = s.size();
int cnt = 0;
for(int i = 0; i < n; i++) {
if(s[i] == '(') cnt++;
else {
cnt--;
if(cnt < 0) return false;
}
}
return cnt == 0;
}

void Main() {
string s; cin >> s;
set<string> Set;
const int n = s.size();
for(int i = 0; i < n; i++) {
string rest = s.substr(0, i) + s.substr(i + 1);
for(int j = 0; j < n - 1; j++) {
const string cur = rest.substr(0, j) + s[i] + rest.substr(j);
if(s == cur) continue;
if(chk(cur)) {
Set.insert(cur);
}
}
}
cout << Set.size() << '\n';
}

G

题面

小Q和牛博士合唱一首歌曲,这首歌曲由n个音调组成,每个音调由一个正整数表示。
对于每个音调要么由小Q演唱要么由牛博士演唱,对于一系列音调演唱的难度等于所有相邻音调变化幅度之和, 例如一个音调序列是8, 8, 13, 12, 那么它的难度等于|8 - 8| + |13 - 8| + |12 - 13| = 6(其中||表示绝对值)。
现在要对把这n个音调分配给小Q或牛博士,让他们演唱的难度之和最小,请你算算最小的难度和是多少。
如样例所示: 小Q选择演唱{5, 6}难度为1, 牛博士选择演唱{1, 2, 1}难度为2,难度之和为3,这一个是最小难度和的方案了。

题解

这题很像求两个字符串的最长公共子序列的长度。

$dp[i][j]$表示第一个人最后唱的音是第$i$个,第二个人最后唱的音是第$j$个的最小难度和。

令$k=max(i,j)+1$,则很容易得到转移方程
$$
dp[k][j]=min(dp[k][j],dp[i][j]+|a[k]-a[i]|)
$$
$$
dp[i][k]=min(dp[i][k],dp[i][j]+|a[k]-a[j]|)
$$

然后最终答案就是
$$
\min(\min\limits_{i=0}^{n}{dp[i][n]},\min\limits_{i=0}^{n}{dp[n][i]})
$$

当然首先要将全部值置为inf。

时间复杂度$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Main();
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie();
Main();
return 0;
}
int a[2005];
ll dp[2005][2005];
void Main() {
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
const int nxt = max(i + 1, j + 1);
if(i == 0) dp[nxt][j] = dp[i][j];
else dp[nxt][j] = min(dp[nxt][j], dp[i][j] + abs(a[nxt] - a[i]));
if(j == 0) dp[i][nxt] = dp[i][j];
else dp[i][nxt] = min(dp[i][nxt], dp[i][j] + abs(a[nxt] - a[j]));
}
}
ll res = INT_MAX;
for(int i = 0; i <= n; i++) {
res = min({res, dp[i][n], dp[n][i]});
}
cout << res << '\n';
}

H

题面

小易正在玩一款新出的射击游戏,这个射击游戏在一个二维平面进行,小易在坐标原点(0,0),平面上有n只怪物,每个怪物有所在的坐标(x[i], y[i])。小易进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。
小易是这个游戏的VIP玩家,他拥有两项特权操作:
1、让平面内的所有怪物同时向任意同一方向移动任意同一距离
2、让平面内的所有怪物同时对于小易(0,0)旋转任意同一角度
小易要进行一次射击。小易在进行射击前,可以使用这两项特权操作任意次。
小易想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮小易。

题解

转化题意:能否用两条相互垂直的直线使得这上面有最多的点。

那么枚举两个点连一条直线,然后再枚举第三个点,这样这两条相互垂直的直线就唯一确定了。

然后check一下每一个点是不是在这两条直线上。用向量来解决会很合适而且没有精度误差。

即两个向量的点积为0表示两个向量垂直,两个向量的叉积为0表示两个向量平行。

时间复杂度$O(n^4)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Main();
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie();
Main();
return 0;
}

struct node {
ll x, y;
};
ll dj(const node& a, const node& b) {
return a.x * b.x + a.y * b.y;
}
ll cj(const node& a, const node& b) {
return a.x * b.y - a.y * b.x;
}
void Main() {
int n; cin >> n;
vector<node> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i].x;
}
for(int i = 0; i < n; i++) {
cin >> v[i].y;
}
int ans = -1;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(v[i].x == v[j].x && v[i].y == v[j].y) continue;
const node A = {v[j].x - v[i].x, v[j].y - v[i].y};
for(int k = 0; k < n; k++) {
int cur = 0;
for(int l = 0; l < n; l++) {
if(v[k].x == v[l].x && v[k].y == v[l].y) cur++;
else {
node B = {v[l].x - v[k].x, v[l].y - v[k].y};
node C = {v[l].x - v[j].x, v[l].y - v[j].y};
if(dj(A, B) == 0 || cj(A, C) == 0) {
cur++;
}
}
}
ans = max(ans, cur);
}
}
}
if(ans == -1) ans = n;
cout << ans << '\n';
}

回到开头