
今天晚上是微软的笔试,有点难,做出 2 题(第 1 题和第 3 题),估计不是太好,但是和身边的同学问了一圈,有做出 1.9 题的(第 3 题用树状数组做,复杂度测试超时),有做出 1.5 题的(第 1 题过了,第 3 题通过一半,又 WA 又 T,或者第 1 题没想出来随便搞了几个部分分,加第 3 题一个 9/10)。


动态规划,bead 只可以从自己的倍数或者因数手上拿来。
dp[i][j] 表示传 i 次能传到 j 这个人有多少种可能,边界数据是传 1 次只能传给 p 的倍数或者因数。
状态转移方程是双重循环计算所有的 i、j,每次用倍数和因数分别计算:传 i – 1 次能传给 j 有多少种可能,就意味着 j 可以花 1 次的时间把东西传给 j 所有的因数或者倍数,于是,dp[i][j / k] 和 dp[i][j * k] 就应该是所有对应的(符合条件的)dp[i – 1][j] 的累加。
最后的答案是不超过 k 次的(for int i = 1; i <= K; i++)的 dp[i][p] 的累加,p 表示回到 p 这个人手上。
import java.io.*; import java.util.*; // Read only region start class UserMainCode { public int maxCircles(int input1,int input2,int input3){ // Read only region end // Write code here... int n = input1; int p = input2; int x = input3; int[][] dp = new int[x + 1][n + 1]; for (int k = p; k > 1; k--) if (p / k > 0 && p % k == 0) dp[1][p / k] = 1; for (int k = 2; p * k <= n; k++) dp[1][p * k] = 1; for (int i = 2; i <= x; i++) { for (int j = 1; j <= n; j++) { for (int k = j; k > 1; k--) if (j / k > 0 && j % k == 0) dp[i][j / k] += dp[i - 1][j]; for (int k = 2; j * k <= n; k++) dp[i][j * k] += dp[i - 1][j]; } } int ans = 0; for (int i = 1; i <= x; i++) ans += dp[i][p]; return ans; } }

第 2 题,不会。



第 3 题,裸的队列。


直接模拟,实现一个队列。
搞不懂这题为什么会有人做错。
TLE 还情有可原。用了树状数组还 T 就有点奇怪。用二分思路好像没问题,但是又 WA 又 T 应该是边界数据没考虑对。
其实实现裸的队列就 OK 了。
如果使用 java.util.LinkedList 就非常简单,代码很短。
唯一需要注意,也是特别需要注意的地方是,remove(int index) 和 remove(Object o) 是两个重载了的方法,前一个方法是删除队列中第 index 个元素(下标从 0 开始),后者是删除队列中值为 o 的那个对象。
例如队列 1 2 3 4 5,如果做 remove(int 3),删掉的是 4,变成 1 2 3 5;如果做 remove(Object 3),删掉的是 3,变成 1 2 4 5。
由于链表保存的是 Integer,如果不能确定到底 remove(Integer i) 会被自动拆箱,变成 remove(int i),还是 Integer 被变成父类 Object,那就 explicit 一下。
import java.io.*; import java.util.*; // Read only region start class UserMainCode { public int findPosition(int input1,int input2,int[][] input3){ // Read only region end int ans = 0; int n = input1; int q = input2; int[][] A = input3; LinkedList<Integer> list = new LinkedList<>(); for (int i = 1; i <= n; i++) list.add(i); for (int i = 0; i < A.length; i++) { switch(A[i][0]) { case 1: list.pollFirst(); break; case 2: list.remove((Object) A[i][1]); // should be "remove(Object o)", not "remove(int index)" break; case 3: ans += list.indexOf(A[i][1]) + 1; break; } } return ans; } }

第 4 题,不会。


长老最终如愿进入微软实习,关于微软的工作体验,你可以参考: