luckcul's blog

越努力，越幸运

0%

微软2016校园招聘4月在线笔试

Posted on Edited on In

做了一下微软2016校园招聘4月在线笔试的题目, 一共3个题目， 2.5h.下面是笔试题目的思路和代码。

1. Font Size

　　阅读电子书，屏幕大小为W*H， 一本电子书有N段， 每段字数ai。我们可以设置一个字符的大小x*x,使得电子书的显示出来的页数不超过P。我们来求满足条件取得最大的x。一行显示的字符个数W/x，一页显示的行数H/x，分别取下整。
　　我们可以想到用二分字符大小的方法，来找到最大的x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std; 
#define INF 1000000000
//typedef __int64 LL; 
int casenum, n, p, w, h; 
int num[1011];
bool binary(int x){
	int a = w / x; 
	int b = h / x; 
	if(a == 0 || b == 0) return false;
	int L = 0; 
	for(int i = 1; i <= n; i++) {
		L += ((num[i] + a-1) / a);
	}
	return L <= b * p;
}
int main() {
	while(scanf("%d", &casenum) != EOF) {
		while(casenum --) {
			scanf("%d%d%d%d", &n, &p, &w, &h); 
			for(int i = 1; i<=n;i++){
				scanf("%d", &num[i]); 
			}
			int low, high, mid, ans; 
			low = 0, high = 1000;
			while(low <= high) {
				mid = (low + high) / 2; 
				bool flag = binary(mid); 
				if(flag) {
					low = mid+1; 
					ans = mid; 
				}
				else {
					high = mid-1; 
				}
			}
			printf("%d\n", ans); 
		}
	}
	return 0; 
}

2.403 Forbidden

　　背景是给出一个网站若干个允许访问和拒绝访问的IP地址和掩码位数。之后给出询问的IP地址，从他给出的allow或者deny中匹配，匹配到第一个就返回，如果限制条件中没有，就返回allow。
　　但是要注意几个trick.

  • 要从上到下依次匹配，匹配到第一个就返回。
  • 如果有多个一样的匹配，实现的时候一定不要覆盖掉，要保存第一个。

　　可以用字典树（这里也就是二叉树）来实现，考虑上面提到的trick，所以在询问的时候，要询问到底，不能碰到第一个符合条件的就返回，要返回次序最小的限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std; 
#define INF 1000000000
//typedef __int64 LL; 
const int N = 1123456; 
int n, m, d = 0, And[10]; 
struct node {
	int l, r, id; 
	bool allow; 
}p[N]; 
char s1[111], s2[111]; 
void gao(int *ip, int mask, bool allow, int id) {
	int times = 0, now = 0; 
	if(mask == 0) {
		if(p[now].id != -1) return;
		p[now].id = id; p[now].allow = allow; 
		return ;
	}
	for(int i = 0; i < 4; i++) {
		for(int j = 1; j <= 8; j++){
			int tmp = ip[i] & And[j]; 
			if(tmp) {// 1
				if(p[now].r == -1) {
					d ++; 
					p[now].r = d; 
					p[d].l = p[d].r = p[d].id = -1; 
				}
				now = p[now].r; 
			}
			else {
				if(p[now].l == -1) {
					d++; 
					p[now].l = d; 
					p[d].l = p[d].r = p[d].id = -1; 
				}
				now = p[now].l ;
			}
			times ++; 
			if(times == mask) {
				if(p[now].id == -1) {
					p[now].id = id; 
					p[now].allow = allow; 
				}
				return;
			}
		}
	}
}
bool solve(int *ip){
	int now = 0, times = 0; 
	int id = INF; 
	bool ret;
	if(p[now].id != -1) {
		id = p[now].id; ret = p[now].allow; 
	}
	for(int i = 0; i < 4; i++ ){
		for(int j = 1; j <= 8; j++) {
			int tmp = ip[i] & And[j]; 
			if(tmp) {// 1
				if(p[now].r == -1) {
					if(id >= INF) return true; 
					return ret;
				}
				now = p[now].r; 
			}
			else {
				if(p[now].l == -1) {
					if(id >= INF) return true; 
					return ret;
				}
				now = p[now].l; 
			}
			if(p[now].id != -1) {
				if(id > p[now].id) {
					id = p[now].id; 
					ret = p[now].allow;
				}
			}
		}
	}
	if(id >= INF) return true; 
	return ret; 
}
int main() {
	for(int i = 1; i <= 8; i++) {
		And[i] = 1<<(8-i);
	}

	while(scanf("%d%d", &n, &m) != EOF) {
		d = 0;
		p[0].l = p[0].r = p[0].id = -1;
		int ip[5]; 
		for(int i = 1; i <= n; i++) {
			scanf("%s%s", s1, s2); 
			int mask_ = 0; 
			bool have = false; 
			for(int j = 0; s2[j]; j++) {
				if(s2[j] == '/') {
					have = true; s2[j] = 0;continue; 
				}
				if(have) {
					mask_ = mask_*10 + (s2[j] - '0'); 
				}
			}
			sscanf(s2, "%d.%d.%d.%d", &ip[0], &ip[1], &ip[2], &ip[3]); 
			int mask = have ? mask_ : 32; 
			gao(ip, mask, s1[0] == 'a', i);
		}
		for(int i = 1; i <= m; i++) {
			scanf("%s", s2); 
			sscanf(s2, "%d.%d.%d.%d", &ip[0], &ip[1], &ip[2], &ip[3]); 
			bool ans = solve(ip); 
			printf("%s\n", ans ? "YES":"NO");
		}
	}
	return 0; 
}

3.Demo Day

　　给你一个N*M大小的图，里面只有.和b两种，.代表可以走，b代表有障碍。机器人只能从左上出发，开始向右走，碰到障碍或者到了图的最右面就往 下走，然后碰到障碍或者到了图的最下面就往右走…………出口在右下角。
　　现在你可以把某个.换成b或者把b换成.。问最少进行几次这样的操作，可以使得机器人可以顺利的从入口走到出口。
　　1<= N, M <= 100.可以考虑动态规划。dp[i][j][k] 表示到达第i行第j列当前方向为k(右或下)采用的最少操作。
　　在(i, j)时候方向为右，要么从(i,j-1)方向为右的状态转移过来；要么从(i-1,j)方向为下的状态转移过来，这时候如果(i+1,j)不为b要把它置为b。同理,(i, j)方向为下时，要么从(i-1,j)方向为下的状态转移过来；要么从(i,j-1)方向为右的状态转移过来，这时候如果(i,j+1)不为b，要把它置为b。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std; 
#define INF 1000000000
//typedef __int64 LL; 
const int N = 111; 
int n, m, num[N][N]; 
char D[N][N];
int dp[N][N][3]; 
int main() {	
	while(scanf("%d%d", &n, &m) != EOF) {
		for(int i = 1; i <= n; i++) {
			scanf("%s", D[i]+ 1); 
		}
		for(int i = 0; i <= n+1; i++) {
			for(int j = 0; j <= m + 1; j++) dp[i][j][0] = dp[i][j][1] = INF; 
		}
		dp[1][0][0] = 0; 
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m ;j++) {
				int add = (D[i][j] == 'b');
				if(dp[i][j-1][0] < INF) dp[i][j][0] = min(dp[i][j][0], dp[i][j-1][0] + add);//
				if(dp[i-1][j][1] < INF) dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][1] + add + (D[i+1][j] == '.') );
				if(dp[i-1][j][1] < INF) dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][1] + add);//
				if(dp[i][j-1][0] < INF) dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][0] + add + (D[i][j+1] == '.') );
			}
		}
		printf("%d\n", min(dp[n][m][0], dp[n][m][1]));
	}
	return 0; 
}

4.Building in Sandbox

　　在一个三维空间里面建造东西，每次摆一个方块。每次摆的时候满足两个条件：
　　*每摆放一个方块要么和地面相邻，要么和之前摆放好的方块相邻

　　*可以从外面(可以考虑为(1000, 1000, 1000))不通过其他木块，不通过地面，能够走到当前摆放的位置。每次走有UP,DOWN,LEFT,RIGHT,FORWARD,BACKWARD留个方向。
　　题目给定一个摆放顺序和位置。问这个顺序摆放是否合理。
　　对于第一个限制条件，比较好检测，每次摆放的时候检查一下周围留个方向就可以；对于第二个限制条件，就不能考虑依次摆放的顺序了。要考虑逆序，对于最后一个是否可以到达比较远的点(101, 101，101)，如果可以到达，把这个方块去掉，考虑倒数第二个方块是否可以到达比较远的点…………如果其中有一个不可到达，结果就是NO。对于如何判断是否可以到达(101, 101, 101)这个点，我们可以用并查集解决。如果用不加优化的BFS 或 DFS应该会TLE。实现的时候注意最下面一排（地面）的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std; 
#define INF 1000000000
//typedef __int64 LL; 
const int ux = 102, uy = 102, uz = 102, M = 100111, N = 121; 
int t, n, par[2123456]; 
int dir[6][3] = {0, 0, 1, 0, 0, -1, 0, 1, 0, 0, -1, 0, 1, 0, 0, -1, 0, 0};
bool vis[N][N][N]; 
struct node {
	int x, y, z; 
}p[M]; 
void init(){
	for(int i = 0; i <= ux; i++) {
		for(int j = 0; j <= uy; j++) {
			for(int k = 0; k <= uz; k++) {
				int id = ((i*(ux+3) + j)*(uy+3)) + k;
				par[id] = id; 
			}
		}
	}
}
int find(int x) {
	if(x != par[x]) par[x] = find(par[x]); 
	return par[x]; 
}
int merge(int x1, int y1, int z1, int x2, int y2, int z2) {
	int id1 = (( x1 *(ux+3) + y1 )*(uy+3)) + z1; 
	int id2 = (( x2 *(ux+3) + y2 )*(uy+3)) + z2; 
	int par1 = find(id1); 
	int par2 = find(id2); 
	if(par1 != par2) {
		par[par1] = par2; 
		return false; 
	}
	return true;
}
int main() {
	scanf("%d", &t); 
	while(t--) {
		memset(vis, 0, sizeof(vis)); 
		scanf("%d", &n); 
		bool ans = true; 
		for(int i = 1; i <= n; i++) {
			scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
			if(!ans) continue;
			vis[p[i].x][p[i].y][p[i].z] = true; 
			if(p[i].z == 1) continue; 
			int cou = 0; 
			for(int j = 0; j < 6; j++) {
				if(vis[p[i].x + dir[j][0]][p[i].y + dir[j][1]][p[i].z + dir[j][2]]) cou ++; 
			}
			if(cou == 0) ans = false;
		}
		if(!ans) {
			puts("No"); 
			continue; 
		}
		init(); 
		for(int i = 0; i <= ux; i++) {
			for(int j = 0; j <= uy; j++) {
				for(int k = 1; k <= uz; k++) if(!vis[i][j][k]) {
					for(int ii = 0; ii < 6; ii++){
						int nx = i + dir[ii][0];
						int ny = j + dir[ii][1]; 
						int nz = k + dir[ii][2]; 
						if(nx < 0 || nx > ux || ny < 0 || ny > uy || nz <= 0 || nz > uz) continue; 
						if(!vis[nx][ny][nz]) merge(i, j, k, nx, ny, nz); 
					}
				}
			}
		}
		bool ok = true;
		for(int i = n; i >= 1; i--) {
			int x = p[i].x; 
			int y = p[i].y; 
			int z = p[i].z; 
			vis[x][y][z] = false; 
			for(int j = 0; j < 6; j++) {
				int nx = x + dir[j][0]; 
				int ny = y + dir[j][1]; 
				int nz = z + dir[j][2]; 
				if(nx < 0 || nx > ux || ny < 0 || ny > uy || nz < 0 || nz > uz) continue; 
				if(vis[nx][ny][nz]) continue; 
				merge(x, y, z, nx, ny, nz); 
			}
			if(!merge(x, y, z, ux, uy, uz) ) {
				puts("No"); 
				ok = false;
				break; 
			}
		}
		if(ok) puts("Yes"); 
	}
	return 0; 
}

小结

　　这些题目并不是太太难，并没有复杂的数据结构，没有思路上或者实现上非常难的算法。但是如果要在2.5h内完美的解决还是需要比较好的代码能力和清晰的思路。而这些都需要自己不断的锻炼和保持的。