08.12 网易互娱笔试

1 2 3 AC 第四题 写完没时间调了
第一题 模拟
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
int w[10],b[10],t[10];
int tb[6][9]={
	{1,4,7,2,5,8,3,6,9},
	{1,4,7,3,6,9,2,5,8},
	{2,5,8,3,6,9,1,4,7},
	{3,6,9,2,5,8,1,4,7},
	{3,6,9,1,4,7,2,5,8},
	{2,5,8,1,4,7,3,6,9}
};
int wcnt=0,bcnt=0,tcnt=0;
int read(){
	char ch=getchar();int f=1,t=0;
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
	return t*f;
}
int getType(int x){
	if (x==1||x==4||x==7) return 1;
	if (x==2||x==5||x==8) return 2;
	if (x==3||x==6||x==9) return 3;
	return 0;
}
bool judge(){
	for (int i=0;i<=5;i++){
		int cnt=0;
		for (int j=0;j<=8;j++){
			int x=tb[i][j];
			if (j<=2){
				if (w[x]) cnt++;
			}else if (j<=5){
				if (b[x]) cnt++;
			}else{
				if (t[x]) cnt++;
			}
		}
		if (cnt>=7){
			return true;
		}
	}
	return false;
	
}
int main(){
	int T=read();
	while (T--){
		bool pd=true;
		wcnt=0,bcnt=0,tcnt=0;
		memset(w,0,sizeof w);
		memset(b,0,sizeof b);
		memset(t,0,sizeof t);
		for (int i=1;i<=7;i++){
			int x;char c;
			scanf("%d%c",&x,&c);
			if (getType(x)==0) {
				pd=false;
			}
			if (c=='W'){
				wcnt++;
				w[x]++;
			}else if (c=='B'){
				bcnt++;
				b[x]++;
			}else {
				tcnt++;
				t[x]++;
			}
		}
		if (!judge()){
			pd=false;
		}
		if (!pd){
			printf("NO\n");
		}else{
			printf("YES\n");
		}
	}
}
第二题 链表暴力
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
struct Point{
	int x,y;
	Point* nex=NULL;
	Point* bef=NULL;
};
Point* st,*ed;
Point* id[505][505];
int n,a[505][505],ind=0,sumX[505],sumY[505];
int recX[505],recY[505];
int read(){
	char ch=getchar();int f=1,t=0;
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
	return t*f;
}
bool del(Point* p){
	if (p==NULL) return false;
	Point* bf=p->bef;
	Point* nx=p->nex;
	if (bf!=NULL){
		bf->nex=nx;
	}
	if (nx!=NULL){
		nx->bef=bf;
	}
	p=NULL;
	return true;
}
int main(){
	n=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++){
			ind++;
			Point* now=new Point();
			now->x=i;
			now->y=j;
			if (ind==1){
				now->bef=NULL;
				now->nex=NULL;
				st=now;
				ed=now;
			}else{
				ed->nex=now;
				now->bef=ed; 
				ed=now;
			}
			id[i][j]=now;
			a[i][j]=read();
			sumX[i]+=a[i][j];
			sumY[j]+=a[i][j];
		}
	for (int round=1;round<=n;round++){
		if (round==n){
			printf("1 1\n");
			break;
		}
		int ansX=0,ansY=0,mx=0;
		Point * now=st;
		while (now!=NULL){
			int val =sumX[now->x]+sumY[now->y]-a[now->x][now->y];
			if (mx<val){
				mx = val;
				ansX = now->x;
				ansY = now->y;
			}
			now=now->nex;
		}
		recX[round]=ansX;
		recY[round]=ansY;
		int delX=0,delY=0;
		for (int j=1;j<round;j++){
			if (recX[j]<ansX) delX++;
			if (recY[j]<ansY) delY++;
		}
		printf("%d %d\n",ansX-delX,ansY-delY);
		for (int i=1;i<=n;i++){
			int x=i,y=ansY;
			if (del(id[x][y])){
				sumX[x]-=a[x][y];
				sumY[y]-=a[x][y];
				id[x][y]=NULL;
			}
			
			x=ansX;y=i;
			if (del(id[x][y])){
				sumX[x]-=a[x][y];
				sumY[y]-=a[x][y];
				id[x][y]=NULL;
			}
		}
	}
}
第三题 应该算是模拟吧...
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
struct Node{
	ll tm;
	int id;
	int state;
	ll cnt;
}q[2000005];
int read(){
	char ch=getchar();int f=1,t=0;
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
	return t*f;
}
int main(){
	int T=read();
	while (T--){
		int qnum=0;
		int n=read();
		ll mx=0;
		int mxId=0;
		for (int i=1;i<=n;i++){
			ll t=(ll)read();
			int id=read(),s=read();
			qnum++;
			q[qnum].tm=t;
			q[qnum].id=id;
			q[qnum].state=s;
			q[qnum].cnt=0;
			while (qnum>0&&q[qnum].state==1){
				if (q[qnum-1].state==0){
					
					ll val=q[qnum].tm-q[qnum-1].tm-q[qnum-1].cnt;
					if (val>mx){
						mx=val;
						mxId=q[qnum].id;
					}else if (val==mx){
						if (q[qnum].id<mxId){
							mx=val;
							mxId=q[qnum].id;
						}
					}
				
				
					ll cost=q[qnum].tm-q[qnum-1].tm;
					qnum--;
					qnum--;
					if (qnum==0) continue;
					if (q[qnum].state==0){
						q[qnum].cnt+=cost;
					}
				}
			}
		}
		printf("%d\n",mxId);
	}
}
第四题我的思路是 对每个宝藏做最短路 然后每个时刻 主角每次循环都判断     判断脚下是否有宝藏 有就吃掉  判断距离哪个宝藏最小 判断4个方向往哪可以走  判断有没有走过重复的路
时间原因没法调试 也没有写判断是否走过重复的路
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
char mp[55][55];
int id[55][55],ind,n,m,treasureNum;
int d[6][4];
int posX[10],posY[10],hasGet[10];
int dis[10][55*55];
int q[6000],vis[6000],hasVis[6000];
int pd[55][55][5],stPosX,stPosY;
//void insert(int x,int y){
//	tot++;
//	go[tot]=y;
//	next[tot]=first[x];
//	first[x]=tot;
//	val[tot]=1;
//}
int read(){
	char ch=getchar();int f=1,t=0;
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
	return t*f;
}
void bfs(int key,int tmpX,int tmpY){
	int st=1;
	int ed=1;
	q[1]=id[tmpX][tmpY];
	vis[key]=1;
	for (int i=0;i<=ind;i++) vis[i]=0;
	for (int i=0;i<=ind;i++) dis[key][i]=99999999;
	dis[key][id[tmpX][tmpY]]=0;
	while (st<=ed){
		int now=q[st++];
		int nowX=0,nowY=0;
		if (now%m==0){
			nowX=now/m;
			nowY=m;
		}else{
			nowX=(now/m)+1;
			nowY=(now%m);
		}
		for (int i=1;i<=4;i++){
			int x=nowX+d[i][0],y=nowY+d[i][1];
			int toId=id[x][y];
			if (vis[toId]) continue;
			if (!pd[nowX][nowY][i]) continue;
			vis[toId]=1;
			dis[key][id[x][y]]=dis[key][id[nowX][nowY]]+1;
			ed++;
			q[ed]=toId;
		}
	}
}
int main(){
	d[1][0]=-1;
	d[1][1]=0;
	d[2][0]=1;
	d[2][1]=0;
	
	d[3][0]=0;
	d[3][1]=-1;
	d[4][0]=0;
	d[4][1]=1;
	
	
	int T=read();
	while (T--){
		n=read(),m=read();
		treasureNum=0;
		for (int i=0;i<=9;i++)
			posX[i]=posY[i]=hasGet[i]=0;
		ind=0;
		for (int i=1;i<=n;i++){
			scanf("%s",mp[i]+1);
		}
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++){
				id[i][j]=++ind;
				hasVis[ind]=0;
				pd[i][j][0]=pd[i][j][1]=pd[i][j][2]=pd[i][j][3]=pd[i][j][4]=0;
				if (mp[i][j]=='*'){
					stPosX=i;
					stPosY=j;
				}
				if (mp[i][j]<='9'&&mp[i][j]>='0'){
					treasureNum++;
					int num=mp[i][j]-'0';
					posX[num]=i;
					posY[num]=j;
				}
			}
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++){
				if (mp[i][j]=='#') continue;
				for (int k=1;k<=4;k++){
					int x=i+d[k][0],y=j+d[k][1];
					if (x<1||y<1||x>n||y>m) continue;
					if (mp[x][y]=='#') continue;
					pd[i][j][k]=1;
				}
			}
		for (int i=0;i<=9;i++){
			if (posX[i]!=0&&posY[i]!=0){
				bfs(i,posX[i],posY[i]);
			}
		}
		int cnt=0;
		while (treasureNum>0){
			int mx=0,mxId=0;
			if (mp[stPosX][stPosY]<='9'&&mp[stPosX][stPosY]>='0'){
				treasureNum--;
				for (int i=0;i<=9;i++){
					if (stPosX==posX[i]&&stPosY==posY[i]){
						hasGet[i]=1;
					}
				}
				for (int i=0;i<=ind;i++) hasVis[i]=0; 
				if (treasureNum==0) break;
			} 
			for (int i=0;i<=9;i++){
				if (posX[i]!=0&&!hasGet[i]){
					if (mx<std::abs(stPosX-posX[i])+std::abs(stPosY-posY[i])){
						mx=std::abs(stPosX-posX[i])+std::abs(stPosY-posY[i]);
						mxId=i;
					}
				}
			}
			bool step=false;
			for (int i=1;i<=4;i++){
				int x=stPosX+d[i][0],y=stPosY+d[i][1];
				if (!pd[stPosX][stPosY][i]) continue;
				if (dis[mxId][id[stPosX][stPosY]]>dis[mxId][id[x][y]]){
					cnt++;
					stPosX=x;
					stPosY=y;
					step=true;
					break;
				}
			}
			if (!step){
				cnt=-1;
				break;
			}
		}
		printf("%d\n",cnt);
	}
}





#笔试题目##网易互娱#
全部评论
巨佬tql
点赞 回复
分享
发布于 2020-08-12 22:18
您第二题的复杂度是O(n^3)吗?
点赞 回复
分享
发布于 2020-08-12 22:58
阿里巴巴
校招火热招聘中
官网直投
我第一题的时候用cout<<"YES"<<endl; 而不是printf("YES\n"),然后一直报输出不符合格式。能高速我一下为什么吗?谢谢!!!!
点赞 回复
分享
发布于 2020-08-12 23:10

相关推荐

头像
03-13 15:53
Java
点赞 评论 收藏
转发
点赞 1 评论
分享
牛客网
牛客企业服务