百度笔试 10.15 题解 麻将卷

百度麻将笔试 10.15 题解
后端卷

第一题 贪心
n选k 如果选择的数的下一个数没被选，积分+1
所以最后一个数一定能拿一分，而在 n/2的转折处
1 (2) 3 (4) 5 (6)(n = 6, k = 3) 可以拿三分
k = 4 时
(1) (2) 3 (4) 5 (6) 仍然可以拿三分，也就是选择了这个1 不会得分但也不会丢分
然后注意数字范围取long long 
while(t --){
        long long int n;
        long long int k;
        cin>>n>>k;
        //n个数里最多可以得n/2 ……
        //1 - n里假如 n 是奇数 1,2,3可以选2两个数
        //假如是偶数那可以选
        long long int res = 0;
        if(n % 2 == 1) res = n/2 + 1;
        else res = n/2;
        //到这里是最多能拿多少分，之后每选一个还得扣
        if(k <= res) cout<<k<<endl;
        else{
            long long int tmp = n + 1;
            cout<<tmp - k << endl;
        }
    }

第二题 约瑟夫环问题
注意到每一次选择一个数，都能确定下来结果的一位数
比如 1 2 3 4
第一次1到队尾，我们就能确定2是结果里的第一位，并且每一次都能确定下来一位
所以本质是约瑟夫环问题
代码就不放了，我是用队列模拟的

第三题 麻将
想了半天dp想不出来，那就搜索一下试试，刚好过了
——————
//dp想破头想不出来
//试一下搜索
//广度优先搜索
//每一轮找刻子或者顺子
//然后四轮后找雀头
//找得到就res ++
//数据量应该支持
//哈希表记录一下string

unordered_set<string> uset;
void dfs(vector<int> &amp;amp;v,int round){
    if(round == 4){
        for(int i = 0;i<v.size();i++){
            if(v[i] >= 2){
                v[i] -=2;
                string tmp;
                for(int j = 0;j < v.size();j++){
                    tmp.push_back(v[j] + '0');
                    tmp.push_back(j + '0');
                }
                v[i] += 2;
                uset.insert(tmp);
            }
        }
        return;
    }
    //dfs
    //先搜刻子，再搜顺子
    for(int i = 0;i<v.size();i++){
        if(v[i] >= 3){
            v[i] -= 3;
            dfs(v, round + 1);
            v[i] += 3;
        }
    }
    for(int i = 1;i < v.size()-1;i++){
        if(v[i-1] >= 1 &amp;amp;&amp;amp; v[i] >= 1 &amp;amp;&amp;amp; v[i + 1] >= 1){
            v[i - 1] --;
            v[i] --;
            v[i + 1] --;
            dfs(v,round + 1);
            v[i - 1] ++;
            v[i] ++;
            v[i + 1] ++;
        }
    }
}
int main() {
    int n;
    cin>>n;
    if(n <= 3) cout<<0;
    else{
        vector<int> vo(n);
        fill(vo.begin(),vo.end(),4);
        dfs(vo, 0);
        cout<<uset.size()<<endl;
    }
    
}