精华 WeBank2017实习生招聘425在线笔试编程题题解
发布于 2017-04-25 21:07 7531 次浏览 1 赞 最后一次编辑是 2017-04-25 21:19 来自 试题交流  

转载题解请联系WeBank及赛码网,版权所有违者必究。



分配:

枚举前两类员工数,计算判断第三类员工是否可满足

示例代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 10009
int main(){
	int n, a, b, c;
	scanf("%d%d%d%d", &n, &a, &b, &c);
	int ans=0;
	for(int i=0; i<=a; i++) for(int j=0; j<=b; j++) 
		if ((n-i*5-j*8)%10==0 && n-i*5-j*8>=0 && n-i*5-j*8<=c*10)
			ans++;
	printf("%d\n", ans);
	return 0;
}


矩形判断:

读取线段,按照题意判断,注意矩形要与坐标轴平行

示例代码:

import java.util.*;
import java.awt.Point;

public class Main {
	static Point array[];
	static boolean flag = true;

	public static void checker(Point a) {
		int cnt = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i].x == a.x && array[i].y == a.y)
				cnt++;
		}
		if (cnt != 2)
			flag = false;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			array = new Point[8];
			int ptr = 0;
			int slope[] = new int[4];
			for (int i = 0; i < 8; i += 2) {
				array[i] = new Point(in.nextInt(), in.nextInt());
				array[i + 1] = new Point(in.nextInt(), in.nextInt());
				if (array[i].x == array[i + 1].x)
					slope[ptr] = 1;
				else if (array[i].y == array[i + 1].y)
					slope[ptr] = -1;
				ptr++;
			}
			for (int i = 0; i < 8; i++) {
				checker(array[i]);
			}
			ptr = 0;
			int ptr1 = 0;
			for (int i = 0; i < 4; i++) {
				if (slope[i] == -1)
					ptr++;
				if (slope[i] == 1)
					ptr1++;
			}
			if (ptr == ptr1 && ptr == 2 && flag)
				System.out.println("YES");
			else
				System.out.println("NO");
		} //while
		in.close();
	}
}


装卸竞赛:

其实就是nim游戏,只是异或的数比较多。注意到0异或1异或2异或3等于0,4异或5异或6异或7等于零。用这个性质优化

示例代码:

import java.util.Scanner;

public class Main {

	public static long xor_fn(long val, long l) {
		long ans = 0;
		for (int i = 0; i < l; i++) {
			ans ^= (val + i);
		}
		return ans;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		while (scan.hasNext()) {
			int n = scan.nextInt();
			long grundy = 0;
			for (int i = 0; i < n; i++) {
				long ans = 0;
				long x = scan.nextLong();
				long m = scan.nextLong();
				if (m > 6) {
					long y = x + m - 1, var = 0, var1 = 0;
					if (x % 4 != 0) {
						long t = 0;
						if (x % 4 == 1)
							t = 3;
						else if (x % 4 == 2)
							t = 2;
						else if (x % 4 == 3)
							t = 1;
						var = xor_fn(x, t);
					}
					if (y % 4 != 3) {
						long k = y % 4 + 1;
						var1 = xor_fn(y - k + 1, k);
					}
					ans = var ^ var1;
				} else {
					ans = xor_fn(x, m);
				}
				grundy ^= ans;
			}
			System.out.println(((grundy > 0) ? "first" : "second"));
		}
		scan.close();
	}

}


城市建设:

预处理计算出以每个点为左上角时的代价,排序依次建设,并把建设过的点标记。

示例代码:

import java.io.*;
import java.util.*;

public class Main {

	static class LIPair implements Comparable<LIPair> {
		long a;
		int y, z;

		LIPair(long a, int y, int z) {
			this.a = a;
			this.y = y;
			this.z = z;
		}

		[@Override](/user/Override)
		public int compareTo(LIPair l) {
			if (this.a < l.a) {
				return -1;
			}
			if (this.a == l.a) {
				return 0;
			}
			return 1;
		}
	}

	public static void main(String[] args) throws java.lang.Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		long cur = System.currentTimeMillis();

		String line = in.readLine();
		while (line != null && line.trim().length() > 0) {
			ArrayList<LIPair> arr = new ArrayList<>();
			ArrayList<LIPair> res = new ArrayList<>();
			char[][] track = new char[1001][1001];
			long[][] sum1 = new long[1001][1001], sum2 = new long[1001][1001], grid = new long[1001][1001];
			int[] index = new int[1001];

			String[] input = line.split(" ");
			int N = Integer.parseInt(input[0]), M = Integer.parseInt(input[1]), A = Integer
					.parseInt(input[2]), B = Integer.parseInt(input[3]);

			int L = 0, R = 0;

			for (int i = 1; i <= N; i++) {
				String[] input2 = in.readLine().split(" ");
				for (int j = 1; j <= M; j++) {
					grid[i][j] = Integer.parseInt(input2[j - 1]);
				}
			}

			for (int i = 1; i <= N; i++) {
				L = 0;
				R = 0;
				for (int j = 1; j <= M; j++) {
					while (L != R && index[L] < j - B + 1) {
						L++;
					}
					while (L < R && grid[i][index[R - 1]] >= grid[i][j]) {
						R--;
					}

					index[R++] = j;
					if (j >= B) {
						sum1[i][j - B + 1] = grid[i][index[L]];
					}
				}
			}

			for (int j = 1; j <= M; j++) {
				L = 0;
				R = 0;
				for (int i = 1; i <= N; i++) {
					while (L != R && index[L] < i - A + 1) {
						L++;
					}
					while (L < R && sum1[index[R - 1]][j] >= sum1[i][j]) {
						R--;
					}
					index[R++] = i;
					if (i >= A) {
						sum2[i - A + 1][j] = sum1[index[L]][j];
					}
				}
			}

			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					sum1[i][j] = sum1[i - 1][j] + sum1[i][j - 1]
							- sum1[i - 1][j - 1] + grid[i][j];
				}
			}

			for (int i = 1; i <= N - A + 1; i++) {
				for (int j = 1; j <= M - B + 1; j++) {
					grid[i][j] = sum1[i + A - 1][j + B - 1]
							- sum1[i - 1][j + B - 1] - sum1[i + A - 1][j - 1]
							+ sum1[i - 1][j - 1] - sum2[i][j] * A * B;

					LIPair l = new LIPair(grid[i][j], i, j);
					arr.add(l);
				}
			}

			Collections.sort(arr);

			for (int i = 0; i < arr.size(); i++) {
				if (track[arr.get(i).y][arr.get(i).z] == 0) {
					int mm1 = Math.max(1, arr.get(i).y - A + 1);
					int mmin1 = Math.min(N + 1, arr.get(i).y + A);
					int mm2 = Math.max(1, arr.get(i).z - B + 1);
					int mmin2 = Math.min(M + 1, arr.get(i).z + B);
					for (int j = mm1; j < mmin1; j++) {
						for (int k = mm2; k < mmin2; k++) {
							track[j][k] = 1;
						}
					}
					res.add(arr.get(i));
				}
			}

			out.println(res.size());
			for (LIPair l : res) {
				out.println(l.y + " " + l.z + " " + l.a);
			}
			line = in.readLine();
		}
//		System.err.println(System.currentTimeMillis()-cur);
		in.close();
		out.close();
	}
}


转载题解请联系WeBank及赛码网,版权所有违者必究。

以上思路供同学们参考,也希望同学能分享自己的经验。

24 条回复

沙发

2017-04-25 21:11
1

有题可以练练吗?

2017-04-25 21:14

2017-04-25 21:15

第三题表示没有看懂

第二题我只过了40%,是因为我刚刚没看到要坐标轴平行?

2017-04-25 21:16

后面几题咋都是Java的,c++的呢?

2017-04-25 21:18
2

唉,0.2ac

2017-04-25 21:20

另外。。。我的只有三道题啊。。。

2017-04-25 21:21
小码快跑 回复 coder_qnwLYOqJ

都是做三道,总共四道,部分岗位的题是不一样的

2017-04-25 21:23

一直对装卸竞赛的样例感到奇怪,是最后一起输出结果还是算一组输出一组?

2017-04-25 21:25
1

装卸竞赛 一直时间超限...  求解上面的题解 x%4 那段是在干什么...

2017-04-25 21:26
1

装卸那个我全部输出“first”过20%

全部输出“second”就全错。。。。这测试用例是什么鬼。。。

2017-04-25 21:27
1

没看懂 题目 真悲伤

2017-04-25 21:32
coder_qnwLYOqJ 回复 coder_SIdonJXV

我也没看懂装载那题。。。

2017-04-25 21:35

weBank难度太高了

2017-04-25 21:37

感觉还差好多

2017-04-25 21:59

分配那题我一直认为暴力枚举太傻,没想到就是最傻的方法。

2017-04-25 22:26

微众银行的笔试已经过了吗?我还没有接到通知啊,是不是就挂了

2017-04-26 13:45

卸货那题我认为就两个有效操作吧,一个是把一辆车卸到只有一个货物,另一个是把这辆车上的所有货物都卸载,当然也存在其他合法操作比如卸到只剩下两个,只剩下三个,但假设A把货物卸到只剩下2个:那B再卸一个,A把最后一个卸掉,就相当于A一开始就把全部都卸了;如果B卸了两个,就等于A卸到剩下一个然后被B卸了,所以真正有效的操作就这两种,所以一开始货物大于2的全部设为2就好了。

当所有车上只有1个货物或者没有货物的时候,如果有奇数个1,那么此时到谁就是谁赢,如果有偶数个1,那么到谁就是谁输

昨晚没做出来,所以也没办法提交看思路对不对……求大神指点

2017-04-26 14:02

装卸那题直接输出first就过了80%

2017-04-26 15:26
coder_SYCZC2MF 回复 coder_qnwLYOqJ

多组测试用例

2017-04-26 15:27

第二题考虑线段退化成点的情况了吗,我用的用例测试不对,checker函数是用来判断什么

2017-04-26 17:07
coder_WV4KQ3YR 回复 coder_qnwLYOqJ

我也是

2017-04-26 17:10

微众怎么查笔试状态,感觉好像已经挂了

2017-05-03 17:46

师弟师妹,师兄帮你内推阿里巴巴

师兄微信号: alibabazp

师兄专门为你排忧解难,同时赠送相关学习资料。

内推贴:

https://discuss.acmcoder.com/topic/5d50cb6751f256de05b3dd5a


2019-08-15 19:21
添加回复
回到顶部