0%

网易游戏(互娱)2020校招在线笔试-游戏研发第一批题解

难度中等,有一道离线处理的题。


A

题面

小A刚学了二进制,他十分激动。为了确定他的确掌握了二进制,你给他出了这样一道题目:给定N个非负整数,将这N个数字按照二进制下1的个数分类,二进制下1的个数相同的数字属于同一类。求最后一共有几类数字?

题解

直接数一下二进制下的位数就可以了。时间复杂度$O(T\cdot n\log(n))$。

但是int __builtin_popcount(unsign int)它不香吗?时间复杂度$O(T\cdot 4q)$。

因为省事所以用了set。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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--) {
set<int> st;
int n; cin >> n;
for(int i = 0; i < n; i++) {
int t; cin >> t;
st.insert(__builtin_popcount(t));
}
cout << st.size() << "\n";
}
}

B

题面

伞屉国是一个以太阳能为主要发电手段的国家,因此他们国家中有着非常多的太阳能基站,链接着的基站会组合成一个发电集群。但是不幸的是伞屉国不时会遭遇滔天的洪水,当洪水淹没基站时,基站只能停止发电,同时被迫断开与相邻基站的链接。你作为伞屉国的洪水观察员,有着这样的任务:在洪水到来时,计算出发电集群被洪水淹没后被拆分成了多少个集群。
由于远古的宇宙战争的原因,伞屉文明是一个二维世界里的文明,所以你可以这样理解发电基站的位置与他们的链接关系:给你一个一维数组a,长度为n,表示了n个基站的位置高度信息。数组的第i个元素a[i]表示第i个基站的海拔高度是a[i],而下标相邻的基站才相邻并且建立链接,即x号基站与x-1号基站、x+1号基站相邻。特别的,1号基站仅与2号相邻,而n号基站仅与n-1号基站相邻。当一场海拔高度为y的洪水到来时,海拔高度小于等于y的基站都会被认为需要停止发电,同时断开与相邻基站的链接。

题解

我们对于每一个询问都需要知道比这个询问海拔高度大的所有基站的位置。如果直接处理的话,复杂度达$O(n\cdot q)$,无法接受。

如果不考虑高度的情况,此时加入一个基站,集群加一,如果这个基站左边的旁边已经有基站了,则集群减一,右边同理。

而且如果某个基站不被淹没,则比他高或者和他一样高的基站也不会被淹没。

这样我们就可以离线操作,考虑最矮的基站最后加入,最高的基站的基站最先加入。同时也先询问询问大的,每一次询问都把比这个询问高的基站加入。这样在排序之后使用双指针的时间复杂度是$O(n+q)$。

所以总的复杂度是$O(n\log(n)+q\log(q))$

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
#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;
vector<int> v(n);
vector<bool> ok(n, false);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](const int &x, const int &y) {
return v[x] > v[y];
});
int q; cin >> q;
vector<int> que(q), idq(q), ans(q);
iota(idq.begin(), idq.end(), 0);
for(int i = 0; i < q; i++) {
cin >> que[i];
}
sort(idq.begin(), idq.end(), [&](const int &x, const int &y) {
return que[x] > que[y];
});
int j = 0, cur = 0;
for(int i = 0; i < q; i++) {
while(j < n && v[id[j]] > que[idq[i]]) {
ok[id[j]] = true;
cur++;
if(id[j] != 0 && ok[id[j] - 1]) cur--;
if(id[j] != n - 1 && ok[id[j] + 1]) cur--;
j++;
}
ans[idq[i]] = cur;
}
for(int i = 0; i < q; i++) {
cout << ans[i] << "\n";
}
}

C

题面

小明作为一个游泳池管理员,以玩弄给水管和排水管为乐,也因此产生了很多数学题考验小朋友。
现在小明想把这个行动升级,考验一下程序员,做了一个自动装置来控制给水管和排水管。在开始时,给水管和排水管都是打开状态的,并且游泳池里没有水。在自动装置的作用下,每经过t1分钟,给水管的状态都会改变,即从打开状态变为关闭状态或从关闭状态变为打开状态,而同时每经过t2分钟,排水管的状态也会改变。当给水管打开时,给水管每分钟会向游泳池里注入m1升水;当排水管打开时,排水管每分钟会把游泳池里水排走m2升;当给水管和排水管同时打开时,游泳池的水量变化为每分钟(m1-m2)升。当然泳池的水量不能变为负数,同时泳池也有个最大容量m,水量不能超过m升。那么经过t分钟后,游泳池里有多少升水?

题解

这个题只要读懂题目直接模拟就可以做了。

注意边界情况。

时间复杂度$O(T\cdot 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
#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 m, t, m1, m2, t1, t2; cin >> m >> t >> m1 >> t1 >> m2 >> t2;
bool a = true, b = true;
int cur = 0;
for(int i = 1; i <= t; i++) {
if(a) cur += m1;
if(b) cur -= m2;
if(i % t1 == 0) a ^= true;
if(i % t2 == 0) b ^= true;
cur = max(cur, 0);
cur = min(cur, m);
}
cout << cur << '\n';
}
}

D

题面

小A很喜欢字母N,他认为连续的N串是他的幸运串。有一天小A看到了一个全部由大写字母组成的字符串,他被允许改变最多2个大写字母(也允许不改变或者只改变1个大写字母),使得字符串中所包含的最长的连续的N串的长度最长。你能帮助他吗?

题解

很显然的动态规划。

令$dp[i][j]$表示的是第$i$个字符前面修改了$j$次所能得到的以第$i$个字符为结尾的连续N串的所能达到的最长值。

那么有

$$
dp[i][j]=max([s[i]=\text{‘N’}]\cdot(dp[i-1][j] + 1), [i\neq 0]\cdot dp[i-1][j-1] + 1,0)
$$

可以滚动数组优化内存,但没必要。

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 dp[50005][3];
char s[50005];
void Main() {
int T; cin >> T;
while(T--) {
cin >> (s + 1);
const int n = strlen(s + 1);
int mx = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 3; j++) {
if(s[i] == 'N') dp[i][j] = dp[i - 1][j] + 1;
else dp[i][j] = 0;
}
for(int j = 1; j < 3; j++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
mx = max(mx, dp[i][j]);
}
}
cout << mx << '\n';
}
}

回到开头