网易游戏雷火2020春招游戏研发工程师笔试题0425 前三题题解
发布时间
阅读量：
阅读量
第一题大概题面：
思路：dfs/bfs，直接计算答案呢不好算，我们考虑先设ans=6*n，然后把多算的面(内部的面)减掉，考虑一个立方体的坐标为(x,y,z)，很容易得到与它相邻的6个面的坐标，如果这些坐标也有立方体，就减去相应的贡献即可，注意每次dfs/bfs的时候需要把一个连通块内的编号设置为统一的，防止死循环。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
int n,ans;
int x[maxn],y[maxn],z[maxn];
int d[6][3]={{-1,0,0},{1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int vis[21][21][21];
void dfs(int x,int y,int z,int ct)
{
vis[x][y][z]=ct;
int dx,dy,dz;
for(int i=0;i<6;i++)
{
dx=x+d[i][0];
dy=y+d[i][1];
dz=z+d[i][2];
if(dx<0||dx>20||dy<0||dy>20||dz<0||dz>20||!vis[dx][dy][dz])
continue;
ans--;
if(vis[dx][dy][dz]!=ct)
dfs(dx,dy,dz,ct);
}
}
//给出n块积木的坐标 n<=1e4 0<=x,y,z<=20
//积木为正方体 边长为1
//积木可以悬空
//求这个立体结构的表面积
//10分
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i]>>z[i];
vis[x[i]][y[i]][z[i]]=1;
}
ans=6*n;
int ct=2;
for(int i=0;i<n;i++)
{
if(vis[x[i]][y[i]][z[i]]==1)
dfs(x[i],y[i],z[i],ct++);
}
cout<<ans<<endl;
}第二题大概题面：
更详细的题解可以看这一篇：<>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n;
int a[maxn];
//求矩形的最大面积
//力扣原题 单调栈可解
//20分
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
a[n]=-1;
stack<int> s;
ll ans=0;
for(int i=0;i<=n;i++)
{
if(s.empty()||a[i]>=a[s.top()])
s.push(i);
else
{
int tmp;
while(!s.empty()&&a[i]<a[s.top()])
{
tmp=s.top();
s.pop();
ans=max(ans,(i-tmp)*1ll*a[tmp]);
}
s.push(tmp);
a[tmp]=a[i];
}
}
cout<<ans<<endl;
return 0;
}第三题大概题面：
思路：爆搜？O(10^n)即便加了剪枝也只能过百分之20左右的样例。显然不是正解。考虑用dp[i][a][b][j]表示前i位数字的和为j，第i位数字为b，第i-1位数字为a时的方案数，那么对于满足：(a*100+b*10+c)\%x=0的c，我们可以得到转移方程：dp[i][b][c][j]+=dp[i-1][a][b][j-c]显然还需要满足：a+b+c<=j<=s。最终答案是什么呢，显然就是所有的dp[n][a][b][s]之和，枚举a、b即可得到结果。总复杂度O(n*10*10*s)=O(100*n*s)，考虑n、s的取值范围，大概在5e^6，实际上应该会更快，因为加了剪枝。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e6+9;
int n,s,x;
int dp[51][10][10][1000];
//n位数字 可以有前导零
//满足所有数字加起来的和等于s
//任意三位连续数字构成的三位数可以被x整除
//这样的数字成为神奇数字 求神奇数字的个数
int main()
{
cin>>n>>s>>x;
for(int i=0;i<10;i++)
{
for(int j=0;j<10&&i+j<=s;j++)
dp[2][i][j][i+j]=1;
}
for(int i=3;i<=n;i++)
for(int a=0;a<10;a++)
for(int b=0;b<10;b++)
for(int c=0;c<10;c++)
{
if((a*100+b*10+c)%x)
continue;
for(int j=a+b+c;j<=s;j++)
dp[i][b][c][j]=(dp[i][b][c][j]+dp[i-1][a][b][j-c])%mod;
}
int ans=0;
for(int a=0;a<10;a++)
for(int b=0;b<10;b++)
ans=(ans+dp[n][a][b][s])%mod;
cout<<ans<<endl;
return 0;
}第四题：感觉算个大模拟吧，写了一半不想写了溜了orz。
全部评论 (0)
还没有任何评论哟~