二道大众点评笔试题最后两题题解

问题1：

这是一道动态规划的问题，状态转移方程为
dp[i] = dp[i-3] + dp[i-1] , i>= 3(i<3时dp[i]=1,只有1种情况)
我这里直接开了一个dp数组解决这个问题。在init方法中进行了初始化。
另外，考虑到为了方便测试，我用了一个递归函数dfs(m,n,str)来进行对所有情况的输出。具体见代码：dfs函数的功能就是输出所有的可行方案。
如：当我输入5的时候，输出：
4
所有方案：
11111
211
121
112
同时我设定了数n的范围，当n<0时或n大于我设定的范围时，会提示出错。
下面是C++代码：

    #include <cstdio>  
    #include <cstring>  
    #include <iostream>  
    #include <algorithm>  
    #include <string>  
    using namespace std;  
    const int maxn = 1010;  
    int dp[maxn];  
    void init() {  
        dp[0] = dp[1] = dp[2] = 1;  
        for(int i=3;i<maxn;i++) dp[i] = dp[i-1] + dp[i-3];  
    }  
    void dfs(int m,int n,string str) {  
        if(m == 0) {  
            cout << str << endl;  
            return;  
        }  
        if(m >= 1)  
            dfs(m-1 , n , "1"+str);  
        if(m >= 3)  
            dfs(m-3 , n , "2"+str);  
        return;  
    }  
    int main() {  
        int n;  
        init();  
        while(scanf("%d" , &n) != EOF) {  
            if(n < 0) {  
                puts("这段路的长度不能为负数！\n");  
                continue;  
            }  
            if(n >= 1010) {  
                puts("我这里设定的最大长度是1009,如果需要改变长度，请联系相关人员！");  
                continue;  
            }  
            int ans = dp[n];  
            printf("%d\n" , ans);  
            printf("所有方案：\n");  
            dfs(n , n , "");  
        }  
        return 0;  
    } 

问题2：

首先通过代码得到二进制数：

    #include <cstdio>  
    #include <cstring>  
    #include <iostream>  
    #include <algorithm>  
    using namespace std;  
    void get(int n) {  
        if(n == 0) return;  
        get(n/2);printf("%d" , n%2);  
    }  
    int main() {  
        get(3593);  
        return 0;  
    } 

1）至少需要开12个线程。
首先我把3593表示成二进制数，为111000001001，一共有12位，然后我开十二个进程，第i个进程中包含所有二进制表示中第i位为0的用户的 集合，如果算法能够检测到违规用户，那么违规用户的第i位二进制数就是0，否则为1.这样开12个线程就能得到第i位用户的所有二进制位的数字，以此得到 该违规用户的数字。

2）至少需要开6个。
第一秒先判断3593的前6个二进制位；
第二秒判断3593的后6个二进制位。
方法同1）。

注：2）的解答不一定对。