2021网易游戏研发岗笔试题解及感想
2021年4月1号19:00-22:00
据说网易游戏岗的笔试是最难的？不过难度也是分场次的，笔试过关也没有具体的分数界定。因为每一场收人，都会考虑很多的因素，不像高考成绩一样，对于一般人几乎就是几门分数定生死，不过能AK自然是妙不可言的。我经历的这一场是2道模拟题，1道DP，最后一道看样子像是直接模拟（处理出所有开关的状态然后暴力？）或者拓扑排序，事后也没得到机会去验证。但是这题，我认识的一位南邮ACM-ICPC金牌得主也没有去写…题面确实有点唬人哈（毕竟 “编程可视化”，题面害巨长 2333）！
一般游戏岗的题目都是模拟居多，毕竟游戏研发要实现现实问题嘛，感觉模拟题和现实最为贴合~废话不多说了，下面直接附上题面和AC的代码！
第一题“打扑克”：纯模拟（10分）
题目描述：
你和小伙伴共四人一起打扑克，使用了两副牌，包括2-10、J、Q、K、A四种花色(红桃、黑桃、红方、黑花)各两张，以及大王、小王各两张，每人手中有27张牌。请计算出你手中的牌可以组合成几种同花顺。
五张数值连续的牌称为顺子，如果花色也相同，则称为同花顺。同花顺的数量是指手中的牌可以组合出的数量，这些同花顺无需同时存在，例如均为红桃的2、3、4、5、6、7，可以组合出2个同花顺 (2.3、4、5、6和3、4、5、6、7)。相同大小和花色的五张牌组成的同花顺只算一种，例如均为红桃的2、3、.4、5、6各两张，只能组合出1个同花顺。特别地，A既可以在A、2、3、4、5中，也可以在10.J、Q、K、A中，大、小王不组成顺子。
输入描述：
27行,每行一张牌。每张牌用两个数字表示，第一个数字表示数值，其中J=11、0=12、K=13、J=14、小王=15、大王=16;第二个数字表示花色，红桃=1，黑桃=2，红方=3，黑花=4，小王的花色为1,大王的花色为2。
输出描述：
同花顺的数量。
输入输出样例如下：
AC_code如下：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=3e5+10;
typedef long long LL;
typedef pair<int,int> PII;
int e[M],w[M],ne[M],h[N],idx;
int dist[N];
bool vis[N];
int cnt[N];
struct f {
int num,id;
}s[N];
bool cmp(struct f x,struct f y) {
if(x.id==y.id) return x.num<y.num;
return x.id<y.id;
}
map<PII,int>mp;
int main()
{
int cnt=0;
for(int i=1; i<=27; i++)
{
int a,b;
cin >> a >> b;
if(a==14)
{
int aa = 1;
if(!mp[{aa,b}]) s[++cnt]={aa,b},mp[{aa,b}]=1;
}
if(mp[{a,b}]) continue;
mp[{a,b}] = 1;
s[++cnt] = {a,b};
}
//cout<<endl;
sort(s+1,s+cnt+1,cmp);
int ans=0;
//for(int i=1;i<=cnt;i++)
//cout<<s[i].num<<" "<<s[i].id<<endl;
for(int i=1; i<=cnt; i++)
{
//if(s[i].num>=11) break;
int flag=0;
if(i+4>cnt) continue;
for(int j=i+1; j<=i+4; j++)
if(s[j].id!=s[i].id||s[j].num!=s[i].num+j-i||s[j].num>14)
flag=1;
if(!flag) ans++;
}
cout << ans << endl;
return 0;
}
AI助手第二题“钱老板玩MMO”：纯模拟（20分）
题目描述：
钱老板玩MMO喜欢在二维的(X,Y)坐标系的场景内刷怪，钱老板一共有两个技能。
技能A：消灭一条直线上的怪，其中直线的方向只有横向(X轴方向)、竖向(Y轴方向)、斜45度和斜135度方向。
技能B：对一个怪M1释放一个AOE(群体伤害)，可以消灭以怪M1为中心,边长为2*N+1的正方形范围(包含正方形的边)内的所有怪，其中正方形的底边是与视野坐标x轴平行。
注意：不同怪物位置可以相同。
现在钱老板想知道某个时刻施放一个技能，最多能消灭的怪的数量。
输入描述：
技能s的正方形边长参数n(整数，0<= N<=30，边长为2*N+1)、怪物数量count（整数，0<=count<=200) 以及所有怪物的坐标(x，y)（x, y均为整数，0<=x<=300，0<=y<=300)。
输出描述：
输出一个整数，表示最多可以消灭的怪物数量。
输入输出样例如下：
AC_code如下：
#include <bits/stdc++.h>
using namespace std;
const int N=4e5+10;
typedef long long LL;
typedef pair<LL,LL> PLL;
int n,m;
struct f {
int x,y;
}s[N];
int check1(int u)
{
int cnt1=0,cnt2=0,cnt3=0,cnt4=0;
for(int i=1; i<=m; i++)
{
if(s[i].x==s[u].x) cnt1++;
if(s[i].y==s[u].y) cnt2++;
if(s[i].x-s[u].x==s[i].y-s[u].y) cnt3++;
if(s[u].x-s[i].x==s[i].y-s[u].y) cnt4++;
}
int res;
res=max(cnt1,cnt2);
res=max(res,cnt3);
res=max(res,cnt4);
//cout<<cnt1<<" "<<cnt2<<" "<<cnt3<<" "<<cnt4<<endl;
return res;
}
int check2(int u)
{
int cnt=0;
int lx=s[u].x-n,rx=s[u].x+n,ly=s[u].y-n,ry=s[u].y+n;
for(int i=1; i<=m; i++)
if(s[i].x<=rx&&s[i].x>=lx&&s[i].y<=ry&&s[i].y>=ly)
cnt++;
return cnt;
}
int main()
{
cin >> n >> m;
for(int i=1; i<=m; i++)
{
int a,b;
cin >> a >> b;
s[i]={a,b};
}
int ans=0;
for(int i=1; i<=m; i++)
{
int t = max(check1(i),check2(i));
ans = max(ans,t);
}
cout << ans << endl;
return 0;
}
AI助手第三题“接水果”：DP（30分）
题目描述：
接水果游戏是个非常简单有趣的电子游戏。在游戏中，水果从屏幕上方由上至下掉落，玩家控制的篮子则在屏幕下方左右任意移动。当玩家控制的篮子触碰到掉落的水果时则成功接住，反之如果水果超过了屏幕的下方底线则失败。如果接住失败的水果大于或等于一定次数限制m (m>0）或者所有水果都被接完，则游戏结束。游戏中有不同的水果，每个水果的总分值也各不相同。最终篮子中接到的水果的总分数之和就是一局游戏的分数。由于篮子移动的速度是有限的，玩家还需要有选择地放弃接一些水果才能最终拿到更高的分数。
所有水果的位置在一轮游戏开始之前就预先设定好，并以坐标的形式(xi.yi)给出，单位为m，xi>=0，yi>0，游戏中不会有两个或两个以上的水果处于同一水平线上。当游戏开始时，所有水果延y轴方向垂直向下以1 m/s的速度匀速移动。
玩家的篮子也有个初始位置,横坐标为x0 m,x0>=0，纵坐标固定为0。篮子的移动速度固定为v m/s，v>0.
现在需要写—个程序,来帮助我们选择最佳的接水果路线。
输入描述;
第一行为4个整数，分别为篮子横向移动的速度v(m/a)、玩家的初始位置x0（m)、所有水果的总数量n、会导致游戏结束的接落失败水果数量m；接下来的n行，每行包括3个整数，分别为水果的x坐标x（m)、y坐标yi(m)，以及水果的分值w1(0<wi<=10)。0<n<=1e4，0<v<=100，1<=m<=100，0<=xi<=1000，0<yi<=2e5。
输出描述：
一个整数，玩家以最优策略(之一)去接水果所能获得的最高分数。
输入输出样例如下：
Tips ：这题有一个限制，就是x和y组合起来的范围很大，需要建个图。建图可以少去很多无用转移。
AC_code如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn=10050;
const int maxm=105;
struct point{
int x,y,val;
point(int x=0,int y=0,int val=0):x(x),y(y),val(val){}
};
bool operator < (point a,point b){
return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
point p[maxn];
int dp[maxn][maxm];
int v,x0,n,m;
void solve() {
scanf("%d %d %d %d",&v,&x0,&n,&m);
for(int i=1; i<=n; i++)
scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].val);
sort(p+1,p+n+1);
p[0] = point(x0,0,0);
int res=0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m&&i-j>=0; j++) {
for(int k=j-1; k<=m-1; k++) {
int h = p[i].y-p[i-j].y;
int l = p[i-j].x-h*v,r=p[i-j].x+h*v;
if(p[i].x>=l&&p[i].x<=r)
dp[i][k] = max(dp[i][k],dp[i-j][k-(j-1)]+p[i].val);
}
}
for(int j=0; j<=m-1; j++)
res = max(res,dp[i][j]);
}
printf("%d\n",res);
}
int main()
{
solve();
return 0;
}
AI助手第四题“可视化编程”：（40分）
猜测是处理出所有开关的状态然后暴力，可能会得分QAQ
题目描述：
可视化编程是游戏常用技术之一，在游戏开发期可方便设计者快速实践想法;在游戏内也可让玩家发挥创造力,提升自由度。
现在要求你实现一套简化的可视化编程系统,模拟电路运行。
系统由两部分组成，元件和电线。元件是单独的功能部件，包含进口和出口;电线是联通两个元件进出口的连线。
定义以下元件的ID,及功能:
A：电源元件，包含0个进口1个出口。出口持续提供电源，即与其出口相联通的其他元件将通电。
B：额外电源元件，包含进口和出口各1个。出口默认不提供电源。若进口收到脉冲信号，则出口将持续提供电源;若进口再次收到脉冲信号，则出口将不提供电源;之后收到信号则如上循环。脉冲信号定义见下方。
C：开关，包含进口和出口各1个，可点击。进出口间默认不连通。若点击开关则联通进出口，再次点击则不联通进出口,之后点击如上循环。
D：计数器，包含进口和出口各1个。进出口之间持续联通。计数器可以显示数字，默认为0;进口每次收到脉冲信号时,计数器数值将加1，最大显示99.
E：分钱器，包含1个进口，和4个出口。进口与每一个出口之间都持续联通。
此外规定：
1.进口不能连接进口，1个进口可以连接0个或1个出口。同理，出口不能连接出口，1个出口可以连接0个或1个进口。
2.电能通过元件时消耗一定时间，规定电能通过每个元件的耗时相同。电能通过电线时不消耗时问。
3.与一个分线器的不同出口相连的元件，它们逻辑执行的先后顺序，与元件连接分线器时的先后顺序一致。即先连接上分线器出口的元件,先执行逻辑。
4.此处的脉冲信号，仅表示由"不通电"状态转变为"通电"状态。持续维持通电或不通电状态、或由通电变为不通电状态,都不产生脉冲信号。
5.所有元件都处于默认的状态。电路图初次联通瞬间，部分元件可能收到脉冲信号，改变元件状态。用户也可以在随后点击开关，改变电路状态。电路图的初次联通，以及点击开关的操作，均可以在有限的步骤内让电路图稳定,不能导致死循环。
输入描述：
第一行是1个整数N（O<N<=256),表示总共有N个元件；
第二行是N个字母,分别为N个元件的ID；
第三行是1个整数M(o<M<=N）,表示总共有M条电线；
第四行是2s个数字,其中第2i-1个数字j，和第2i个数字k (1<=i<=M,1<=j<=N,l<=k<=N),表示用一条电线,将第3个元件的出口和第k个元件的进口相连；
第五行是一个整数s(O<s<=1024）,表示共有s次点击开关元件操作；
第六行是s个整数,第1个整数j(1<=i<=S,l<=<=N)，表示点击第j个元件〈若第个元件不是开关，则这本次输入无效,不做处理)。
输出描述：
所有点击操作执行完毕后，按照序号从小到大，输出所有计数器当前的数值，用空格分隔。
输入：
6
A C E D B D
1 2 2 3 3 4 3 5 5 6
2 2 2 2 5
输出：
2 1
小旭琢磨着这场的这一题能AC，其他的也不用做了，因为觉得真的是题目都看不下去！
有大佬有兴趣的话可以试一试（抱拳了
