首页 > 网易互娱秋招笔试8.12非官方完整题解
头像
〢ヽ夜╰︶ ̄太美
编辑于 2020-08-18 13:35
+ 关注

网易互娱秋招笔试8.12非官方完整题解

这场题意和做法应该都比较明确,比较偏考验代码功底,算法的细节其实不多,所以讲解比较少,基本在代码中,代码中有比较详细的注释。如果还不能明白,可以私信问我或者回复。

Problem A:
给7张麻将牌(长度为2的字符串),问除花牌部分能不能组成"七星不靠"(这个可以自行百度)。
做法:应该挺显然的,处理下万饼条分别属于147,258,369的哪一类,再检查下类间是否互斥即可,具体看代码吧。
AC代码:
#include<bits/stdc++.h>
using namespace std;

int main() {
	int T; scanf("%d", &T); while(T--) {
		vector<int> v[3];//存放万饼条的数字 
		//输入 
		for(int i = 0; i < 7; i++) {
			char p[5]; scanf("%s", p);
			if(p[1] == 'T')v[0].push_back(p[0] - '0');
			if(p[1] == 'B')v[1].push_back(p[0] - '0');
			if(p[1] == 'W')v[2].push_back(p[0] - '0');
		}
		int fl = 1;
		//特判缺门的情况 
		for(int i = 0; i < 3; i++)if(v[i].empty()) {
			puts("NO");
			fl = 0;
			break;
		}
		if(!fl)continue;
		//排序 
		for(int i = 0; i < 3; i++)sort(v[i].begin(), v[i].end());
		//判断万饼条内部是否满足隔3或者隔6的条件 
		for(int i = 0; i < 3; i++)for(int j = 1; i < v[i].size(); j++) {
			if(v[i][j] - v[i][j - 1] == 3 || v[i][j] - v[i][j - 1] == 6);
			else fl = 0;
		}
		//判断万饼条间元素对3取模是否互相独立
		int cc[3] = {0}; 
		for(int i = 0; i < 3; i++)cc[v[i][0] % 3]++;
		for(int i = 0; i < 3; i++)if(!cc[i])fl = 0;
		puts(fl ? "YES" : "NO");
	}
	return 0;
}

Problem B:
给个n*n矩阵,每次消除一行一列,要求消除的行列和尽可能大,如果有多个方案可选,选择行号尽量小的,同行就选列号尽量小的。
消除后矩阵会变为(n-1)*(n-1)矩阵,继续消除操作。
问n次操作选择的行列方案分别是多少?
n范围500。
做法:预处理每行每列的和,每次消除枚举行列,计算方案的和,选出最佳的。
消除后将矩阵暴力的合并起来,并更新行列和的数组。
总体复杂度控制在立方级别就可以。
#include<bits/stdc++.h>
using namespace std;

const int N = 505;
int ph[N], pl[N]; //ph表示每列的和,pl表示每行的和 
int a[N][N]; //存放矩阵元素 
int main() {
	int n; scanf("%d", &n);
	for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){
		//输入矩阵元素 
		scanf("%d", &a[i][j]);
		//顺带处理每行每列的和
		pl[i] += a[i][j], ph[j] += a[i][j];
	}
	for(int _ = 0; _ < n; _++) {
		//计算每个坐标丢十字斩的的得分,求出题目要求的坐标 
		int x = 1, y = 1;
		for(int i = 1; i <= n - _; i++)for(int j = 1; j <= n - _; j++) {
			int pre = pl[x] + ph[y] - a[x][y];
			int now = pl[i] + ph[j] - a[i][j];
			if(now > pre)x = i, y = j;
		}
		printf("%d %d", x, y);
		//处理当前每行每列的和 
		for(int i = 1; i <= n - _; i++)ph[i] -= a[x][i];
		for(int i = 1; i <= n - _; i++)pl[i] -= a[i][y];
		//将矩阵移位,处理的两个数组也移位 
		for(int i = 1; i < n - _; i++)for(int j = 1; j < y; j++)a[i][j] = a[i + 1][j];
		for(int i = 1; i < x; i++)for(int j = y; j < n - _; j++)a[i][j] = a[i][j + 1];
		for(int i = x; i < n - _; i++)for(int j = y; j < n - _; j++)a[i][j] = a[i + 1][j + 1];
		for(int i = x; i < n - _; i++)pl[i] = pl[i + 1];
		for(int i = y; i < n - _; i++)ph[i] = ph[i + 1];
	}
}

Problem C:
有若干个任务,每个任务可能有子任务,给出每个任务的开始与结束时间,保证某个任务的子任务一定在那个任务期间完成,且每个任务期间不会有其他非子任务的任务插入。
问哪个任务的纯用时(任务时间减去所有子任务时间)最大。
做法:可以看出任务在这样的限制下,可以用一个栈来处理,并计算总时长,那么只需要再处理所有任务的子任务时长,就可以得出答案了。
AC代码:
#include<bits/stdc++.h>
using namespace std;

int main() {
	int T; scanf("%d", &T);
	while(T--) {
		map<int, int> M; //存放子任务的时长和 
		stack<pair<int, int> > S; //存放当前父任务序列 
		int n; scanf("%d", &n);
		int id = -1, maxtime = 0;
		for(int i = 0; i < n; i++) {
			int t, e, s; scanf("%d%d%d", &t, &e, &s);
			if(s == 0) S.push(make_pair(t, e));//如果任务是开始,丢入栈中 
			else {
				//任务结束,栈顶必定是这个任务的开始状态 
				
				//计算任务时长 
				int nowtime = t - S.top().first;
				//判断当前任务的自身用时是否大于当前最大值 
				if(nowtime - M[e] > maxtime || nowtime - M[e] == maxtime && id > e)maxtime = nowtime - M[e], id = e;
				S.pop();
				//更新父任务的子任务时长和 
				if(!S.empty())M[S.top().second] += nowtime;
			}
		}
		//输出答案 
		printf("%d", id);
	}
	return 0;
}

Problem D:
给定一个地图,规模最大50*50,有10个以内的宝箱,在地图0-9的位置上,主人公位置在*号处。
主人公每一步的行动逻辑如下:
找出离他曼哈顿距离最近的宝箱。
枚举方向,优先级上下左右,如果枚举到的方向可以让离那个宝箱的最短路缩短,那么就走那个方向,其他方向不再枚举。
如果这样的行动逻辑可以拿走所有的宝箱,输出步长,否则输出-1。
做法:直接看代码吧,注释里写的很详细了。
-1的情况有两种,一种是死循环了,这个可以通过加tag判断。
一种是宝箱不可达,这个在处理最短路的过程中是可以发现的。
AC代码:
#include<bits/stdc++.h>
using namespace std;

const int N = 55;

const int pos[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1}; //预处理上下左右 
char Map[N][N]; //存放地图 
int Box[N][2]; //存放宝箱坐标 
int dis[N][N][N]; //存放每个宝箱到地图其他点的最短路 
int pick[N]; //标记宝箱是否已经被拿过 
int fl[N][N]; //标记地图中某个点是否被走过 
int sx, sy; //人物当前的坐标 
void init() {
	memset(Map, 0, sizeof Map);
	memset(pick, 0, sizeof pick);
	memset(fl, 0, sizeof fl);
}
int main() {
	int T; scanf("%d", &T); while(T--) {
		//初始化全局数组 
		init();
		
		//读入地图 
		int n, m; scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; i++)scanf("%s", Map[i] + 1);
		
		//搜索地图,查看宝箱坐标和起始点坐标 
		int cnt = 0;
		for(int i = 1; i <= n; i++)for(int j = 1; i <= m; i++) {
			if(Map[i][j] == '*')sx = i, sy = j, Map[i][j] = '.';
			else if(isdigit(Map[i][j]))Box[Map[i][j] - '0'][0] = i, Box[Map[i][j] - '0'][1] = j, cnt++, Map[i][j] = '.';
		}
		
		//bfs处理出每个宝箱的点到地图中所有格子的最短路 
		for(int i = 0; i < cnt; i++) {
			memset(dis[i], -1, sizeof dis[i]);
			int x = Box[i][0], y = Box[i][1];
			dis[i][x][y] = 0;
			queue<pair<int, int> > Q; Q.push(make_pair(x, y));
			while(!Q.empty()) {
				int nowx = Q.front().first, nowy = Q.front().second;
				for(int p = 0; p < 4; p++) {
					int nextx = nowx + pos[p][0];
					int nexty = nowy + pos[p][1];
					if(Map[nextx][nexty] == '.' && dis[i][nextx][nexty] == -1) {
						dis[i][nextx][nexty] = dis[i][nowx][nowy] + 1;
						Q.push(make_pair(nextx, nexty));
					}
				}
				Q.pop();
			}
		}
		int ccnt = 0, len = 0; //分别表示当前拿走的宝箱数和步长 
		//开始行动
		while(ccnt < cnt) {
			int x = -1, mindis = 1e9;
			//计算目标宝箱 
			for(int i = 0; i < cnt; i++) {
				if(pick[i])continue;
				int mdis = abs(Box[i][0] - sx) + abs(Box[i][1] - sy);
				if(mdis < mindis)x = i, mindis = mdis;
			}
			//判断目标宝箱是否可达,或者当前这个格子曾经走过 
			if(dis[x][sx][sy] == -1 || fl[sx][sy]) {
				puts("-1");
				break;
			}
			fl[sx][sy] = 1;//标记当前格子已被走过
			//枚举上下左右方向,找出下一步坐标 
			for(int p = 0; p < 4; p++) {
				int nx = sx + pos[p][0];
				int ny = sy + pos[p][1];
				if(Map[nx][ny] != '.')continue;
				if(dis[x][nx][ny] < dis[x][sx][sy]) {
					len++, sx = nx, sy = ny;
					break;
				}
			}
			//判断是否已经到达宝箱 
			if(sx == Box[x][0] && sy == Box[x][1]) {
				ccnt++, pick[x] = 1;
				//将标记清空 
				memset(fl, 0, sizeof fl);
			}
		}
		//输出答案 
		if(ccnt == cnt)printf("%d\n", len);
	}
	return 0;
}

全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐