网易互娱 游戏研发工程师 暑期实习 笔试+一面

打ACM的蒟蒻一个。

笔试

题目的全貌没有，把记得到的题意写一下。

T1

题意

给一个矩阵，有一个人站在某一个点上，一开始他有一把长度为的大刀，每个格点有个点权，且。如果大刀能砍到这个格点（欧几里得距离小于大刀长度），大刀长度加。问最后大刀的最长长度。

Solution

如果某个时刻大刀能砍到某个位置，大刀加长后还是能砍得到那个位置。

那我们不妨先砍离站的位置最近的格点，如果近的格点都砍不到那远的格点就更加砍不到。非常简单的贪心思想。

Code

#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 mze[505][505];

void Main() {
  int T; cin >> T;
  while(T--) {
    int n, m; cin >> n >> m;
    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        cin >> mze[i][j];
        v.emplace_back(i, j);
      }
    }
    int x, y; cin >> x >> y;
    sort(v.begin(), v.end(), [&](const pair<int, int>& a, const pair<int, int> &b) {
      const int A = (a.first - x) * (a.first - x) + (a.second - y) * (a.second - y);
      const int B = (b.first - x) * (b.first - x) + (b.second - y) * (b.second - y);
      return A < B;
    });
    for(int i = 0; i < n * n; i++) {
      const int X = v[i].first, Y = v[i].second;
      if((X - x) * (X - x) + (Y - y) * (Y - y) > m * m) break;
      m += mze[X][Y];
    }
    cout << m << '\n';
  }
}

T2

题意

现有中个数，一开始每个数分别在不同的集合里，每一个集合中只有一个数，有三种操作：

• 把和所在两个集合合并。
• 把从当前集合拿出来并独立成为一个集合。
• 输出所在集合大小。
  共进行次操作。

数据范围忘了，只记得。

Solution

一开始以为是写个并查集，但这个不仅需要合并还需要从集合中抽元素出来。

而暴力的话才的复杂度，那直接暴力就可以了。

记录一下每一个数所在的集合的编号。

对于询问一将两个集合的编号合并成一个即可；询问二而言开一个新的集合编号，让这个数的集合编号变成这个；询问三直接扫一遍数组看下有多少个集合和的集合编号相同即可。

Code

#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 st[11111];
int pos[11111];
void Main() {
  int T; cin >> T;
  while(T--) {
    int n, m; cin >> n >> m;
    for(int i = 0; i < 11111; i++) st[i] = 0;
    for(int i = 1; i <= n; i++) {
      pos[i] = i;
      st[i]++;
    }
    int cnt = n + 1;
    for(int i = 0; i < m; i++) {
      int op; cin >> op;
      if(op == 1) {
        int x, y; cin >> x >> y;
        const int cur = pos[x];
        st[cur] = 0;
        for(int i = 1; i <= n; i++) {
          if(pos[i] == pos[x] || pos[i] == pos[y]) {
            st[cur]++;
            pos[i] = cur;
          }
        }
      } else if(op == 2) {
        int x; cin >> x;
        st[pos[x]]--;
        pos[x] = cnt++;
        st[pos[x]]++;
      } else {
        int x; cin >> x;
        cout << st[pos[x]] << '\n';
      }
    }
  }
}

T3

题意

给定一个到的个数的排列A，构造一个A的错排序列B。

然后给定一个长度为的数组V。

令为在排列A的第几个位置，为在排列B中的第几个位置。

使得最小，问这个最小值是多少。

其中

Solution

一看到，我就感觉这是一道状压dp的题。事实上有人用贪心也能过。

令表示第个位置现在的状态是所能得到的最小值。其中状态指的是是否已经使用过了某个数，如果使用过则在该位上为1，否则为0。这样总共有的状态的总数是。

那么转移方程也很容易得到，还需要使用滚动数组避免内存超限。

最终总的复杂度是，虽然我的代码中看上去的复杂度是，但if(dp[~i & 1][j] == 0x3f3f3f3f) continue;过滤掉状态中的个数不是个的，均摊下来复杂度是。

Code

#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[2][1 << 25];
int a[25], v[25], p[25];
void chkmin(int &x, int y) {
  if(x > y) x = y;
}
void Main() {
  int T; cin >> T;
  while(T--) {
    int n; cin >> n;
    for(int i = 0; i < n; i++) {
      cin >> a[i];
      a[i]--;
      p[a[i]] = i;
    }
    for(int i = 0; i < n; i++) {
      cin >> v[i];
    }
    for(int j = 0; j < (1 << n); j++) dp[1][j] = 0x3f3f3f3f;
    dp[1][0] = 0;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < (1 << n); j++) dp[i & 1][j] = 0x3f3f3f3f;
      for(int j = 0; j < (1 << n); j++) {
        if(dp[~i & 1][j] == 0x3f3f3f3f) continue;
        for(int k = 0; k < n; k++) {
          if(((j >> k) & 1) || a[i] == k) continue;
          chkmin(dp[i & 1][j | (1 << k)], dp[~i & 1][j] + v[k] * abs(p[k] - i));
        }
      }
    }
    cout << dp[(n + 1) & 1][(1 << n) - 1] << '\n';
  }
}

这套题难度还行，一个小时不到AK了。

一面

凉凉的感觉。跟我队友问的完全不一样啊。

没有自我介绍。

• 你想做的是前端还是后端？（后端）
• 了解过游戏研发吗？游戏研发当中需要处理什么东西？（强行答）
• 讲一下虚函数的实现（虚函数表）
• 虚函数表是一个类一个还是一个对象一个？（一个类一个）
• 讲一下拷贝构造函数（balabala）
• 两个对象a和b，先声明a在声明b，但是先初始化b，再初始化a，会有什么问题？（有可能会有相互调用的情况，然后b调用了未初始化的a，导致空指针的出现，属于undefined behavior。）
• Python的类里添加一个变量可以用什么数据结构实现？（哈希表）
• 哈希冲突的解决方法？（线性探测，链表，再哈希，公共溢出区，……）
• 线性探测时如何知道是不是自己想要的位置？（不仅要记录哈希后的key，还要记录哈希前的key）
  下面是我的噩梦时间
• UDP怎么解决发包时接收顺序与发送顺序不一致的问题？（每个包加个序号）
• 除了游戏什么东西会用到UDP？（……）
• 有没有面试其他公司，结果如何？

括号里面是我自己答的而且不一定对仅供参考。还有很多其实不会，但是被引导地会了。。二十几分钟就结束了，凉凉。

没有手撕代码。代码框没用过。

对比一下我的队友的面经，我怀疑我们面的不是同一个东西。

后续

网易游戏给我发感谢信了。可喜可贺。继续加油。