Visits: 628

今天晚上是微软的笔试，有点难，做出 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 题，不会。