网易互娱2020校招在线笔试－游戏研发第二批 个人题解
A
看见很多人先二进制分解然后反向比较，我觉得这一点都不优美
我们可以利用栈的后进先出特点和队列的先进先出特点
#include<bits/stdc++.h>
using namespace std;
stack<int>st;
queue<int>que;
int main() {
int _;cin>>_;
while(_--) {
int x;cin>>x;
while(x) {
st.push(x%2);
que.push(x%2);
x>>=1;
}
bool flag = 0;
while(!st.empty()) {
if(st.top() != que.front()) flag = 1;
st.pop();que.pop();
}
if(flag) cout<<"NO\n";
else cout<<"YES\n";
}
}B
- 我们没有必要建树，只需要存下读入给的内容，因为读入就是给的一个节点的信息
- 关于找根节点，可以利用所有的节点都有父亲节点这个特点，那么标记一下每个点有没有父亲节点，唯一一个没有父亲节点的点就是根节点
- 我们依然没有必要去层序遍历，由题意可知，如果遍历到某个点x的深度为d,那么sum[d] += val[x],这样的话只需要正常的DFS,就可以记录下每层的和，d一定不会超过节点数量
- 记得初始化
#include<bits/stdc++.h> using namespace std; const int N = 1005; bool du[N]; int n; int sum[N],m; struct Node{ int val,l,r; void input(){ scanf("%d%d%d",&val,&l,&r); if(l >=0) du[l] = 1; if(r >=0) du[r] = 1; } }tree[N]; void dfs(int now,int dep) { m = max(m,dep); sum[dep] += tree[now].val; if(tree[now].l >=0) dfs(tree[now].l,dep+1); if(tree[now].r >=0) dfs(tree[now].r,dep+1); } int main() { int _;scanf("%d",&_); while(_--) { scanf("%d",&n); memset(du,0,n+1); memset(sum,0,(n+1)<<2); m = 0; for(int i=0;i<n;i++) { tree[i].input(); } int s = -1; for(int i=0;i<n;i++) { if(du[i] == 0) { s = i;break; } } m = 0; dfs(s,1); bool flag = 0; for(int i=2;i<=m;i++) { if(sum[i] <= sum[i-1]) { flag = 1; break; } } if(flag == 0) cout<<"YES\n"; else cout<<"NO\n"; } }
C
喝咖啡，一共就30天
如果某一天能喝咖啡，那它距离上一次喝过咖啡的时间>=d，距离下一次必须喝咖啡的时间也>=d
所以我们从１号开始枚举，如果满足上面的条件，我们就让他喝咖啡，更新上一次喝咖啡的时间为今天，如果到了下一次必须喝咖啡的时间，更新到再下一次必须喝咖啡的时间
具体看代码
#include<bits/stdc++.h>
using namespace std;
int k,m,a[35];
int main() {
int _;scanf("%d",&_);
while(_--) {
scanf("%d%d",&k,&m);
for(int i=1;i<=m;i++) {
scanf("%d",&a[i]);
}
int ans = 0;
a[0] = 1-k-1;a[m+1] = 30+k+1;
int pre = a[0],pos = 1,nex = a[1];
for(int i=1;i<=30;i++) {
if(i == nex) {
pre = i;
nex = a[++pos];
ans++;
continue;
}
if(i - pre - 1 >=k && nex - i - 1 >= k) {
ans++;
pre = i;
}
}
cout<<ans<<"\n";
}
}D
观察这个图形，我们会发现如果一个正方形是合法的，他中间的黑块，他的左上角的点
一定是白色，右下角的点
也一定是白色,那我们可以
枚举每个点，看看它能不能作为
,如果可以，找到
,去判断一下九个块是不是满足题目给的条件
判断一个块是不是全0或者全1,我们可以预处理出来矩阵前缀和，求子矩阵和可以差分一下，那我们只需要判断一下子矩阵和是不是０或者是不是矩阵面积即可，具体看代码
(我在枚举９块的那里写得太丑了)
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[2005][2005];
int sum[2005][2005];
int a,b,c,d,ans=0;
bool cal(int a,int b,int c,int d,bool flag) {
int tot = sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1];
if(flag == 0) return tot==0;
return tot == (c-a+1)*(c-a+1);
}
void solve(int bx,int by) {
int nowx = bx+1,nowy = by+1;
while(nowx<=n && nowy <= m && s[nowx][nowy] == '1') nowx++,nowy++;
int ex = nowx-1,ey = nowy-1;
int lenth = ex - bx + 1;
if(!cal(bx,by,ex,ey,1)) return;
int aa = bx-lenth,bb = by-lenth,cc = ex+lenth,dd = ey+lenth;
ex-=lenth;ey-=lenth;bx-=lenth;by-=lenth;
if(bx <1 || by < 1 || !cal(bx,by,ex,ey,0)) return;
by+=lenth;ey+=lenth;
if(!cal(bx,by,ex,ey,1)) return;
by+=lenth;ey+=lenth;
if(ey>m || !cal(bx,by,ex,ey,0)) return;
bx+=lenth;ex+=lenth;
if(!cal(bx,by,ex,ey,1)) return;
bx+=lenth;ex+=lenth;
if(ex>n || !cal(bx,by,ex,ey,0)) return;
by-=lenth;ey-=lenth;
if(!cal(bx,by,ex,ey,1)) return;
by-=lenth;ey-=lenth;
if(!cal(bx,by,ex,ey,0)) return;
bx-=lenth;ex-=lenth;
if(!cal(bx,by,ex,ey,1)) return;
if(ans < lenth) {
ans = lenth;
a = aa;b = bb;c = cc;d = dd;
}
else if(ans == lenth) {
if(aa<a ||(aa == a && bb < b))
a = aa;b = bb;c = cc;d = dd;
}
return;
}
int main() {
int _;scanf("%d",&_);
while(_--) {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
sum[i][j] = s[i][j]-'0'+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
ans = 0;
a = b = c = d = -1;
for(int i = 2;i<n;i++) {
for(int j=2;j<m;j++) {
if(s[i][j]=='1' && s[i-1][j-1] == '0') {
solve(i,j);
}
}
}
cout<<a<<" "<<b<<" "<<c<<" "<<d<<"\n";
}
}不理解的地方欢迎留言！！求赞！！！#题解##笔试题目##网易互娱##游戏研发工程师#
