网易互娱2020秋招笔试真题

1、二进制计数

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

输入描述

输入的第一行是一个正整数T（0<T<=10），表示样例个数。对于每一个样例，第一行是一个正整数N（0<N<=100），表示有多少个数字。接下来一行是N个由空格分隔的非负整数，大小不超过2^31–1。

输出描述

对于每一组样例，输出一个正整数，表示输入的数字一共有几类。

示例1

输入

1
5
8 3 5 7 2

输出

【解题思路】

用二进制1的个数作为hash的key统计答案即可。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
 
int get_bits(int num) {
    if (num == 0)
        return 0;
    return num % 2 + get_bits(num / 2);
}
 
int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        unordered_map<int, int> mp;
        scanf("%d", &n);
        int num, bits;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &num);
            bits = get_bits(num);
            if (mp.find(bits) == mp.end())
                mp[bits] = 1;
            else
                mp[bits]++;
        }
        printf("%d\n", mp.size());
    }
}

2、游泳池

【题目描述】小明作为一个游泳池管理员，以玩弄给水管和排水管为乐，也因此产生了很多数学题考验小朋友。

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

输入描述

输入第一行为一个正整数T，表示有T组数据。
每组数据的为一行包含六个整数，分别表示m, t, m1, t1, m2, t2。
数据范围：
对于所有数据，满足1<=T<=10, 1<=m<=100000, 1<=t<=86400, 1<=m1,m2<=100, 1<=t1,t2<=10。

输出描述

对于每一个数据，输出一行，包括一个整数，为在t分钟后游泳池中的水量。

示例1

输入

5
10 2 1 5 2 5
10 2 10 5 2 5
10 2 3 5 2 5
100 100 3 4 4 3
10000 1000 10 5 5 3

输出

【解题思路】

模拟实现即可。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
 
static inline void assert_range(int x, int l, int r) {
    assert(x >= l && x <= r);
}
 
static bool is_open(int t, int t1) {
    if (t % (2 * t1) < t1) {
        return true;
    } else {
        return false;
    }
}
void cal() {
    int m, t, x1, x2, t1, t2;
    scanf("%d %d %d %d %d %d", &m, &t, &x1, &t1, &x2, &t2);
    assert_range(m, 1, 100000);
    assert_range(t, 1, 86400);
    assert_range(x1, 1, 100);
    assert_range(x2, 1, 100);
    assert_range(t1, 1, 10);
    assert_range(t2, 1, 10);
    int x = 0;
    for (int i = 0; i < t; i++) {
        if (is_open(i, t1)) {
            x += x1;
        }
        if (is_open(i, t2)) {
            x -= x2;
        }
        if (x < 0) {
            x = 0;
        } else if (x > m) {
            x = m;
        }
    }
    printf("%d\n", x);
    return;
}
int main() {
    int t;
    scanf("%d", &t);
    assert_range(t, 1, 10);
    while (t > 0) {
        t--;
        cal();
    }
    return 0;
}