模考集训DAY3.py

经验分享区
1

模考集训DAY3

题解

T1(第k小)：

image

这道题是一道 STL+模拟 的题，这道题一看就比较像搜索，但是dfs会超时，所以我们要考虑bfs。

一般的bfs是要用队列进行存储，但是这里我们需要找到第k小的数，所以我们需要一个能自动排序的容器，我们一下就能想到大根堆，但是我们也要处理重复的情况，那有没有既能去重又会排序的容器呢？撕……还真有，STL简直是全能战神啊，set既可以排序又会去重，简直是这道题的最佳人选，这样我们就可以用bfs进行搜索。

这样整体的思路就出来了，就是将 a 数组排序并去重，保证每一次bfs得到的结果都是剩下中最小的，然后进行bfs，但是这里bfs的结束条件从判断他是否为空变为他的长度有没有到达k这样就搞定了。

部分代码：

    while(s1.size()<k){
        ll x=*s.begin();
        s.erase(x);
        s1.insert(x);
        for(ll i=1;i<=n;i++){
            s.insert(x+a[i]);
        }
    }

T2(扑克欺诈)：

image
这道题是一道典型的数学题+模拟，这道题需要用到概率论，小学奥数应该都学过的吧，所有可能数除目标可能数就是这件事在这个大事件里发生的概率。
当然，我不太懂这些东西，我只知道这次得到的结论就是：
先根据给定的数据求出最后的位置，然后倒着推概率，将概率相加，除以10即为所求

而因为其中已经到过的位置，到达最终位置的概率为1，其他的则有九种可能性，所以每一种位置i的概率是i*j（j取所有值）的概率的平均值。

所以可以得到部分代码：

    for(ll i=idx;i>=1;i--){
        // cout << p[i];
        if(p[i]==0){
            for(ll j=2;j<=11;j++){
                ll t=(j==10?4:1);
                p[i]+=t*p[i+j];
            }
            p[i]=p[i]/13;
        }
        if(i<=10){
            ans+=p[i];
        }
    }

T3(候选人)：

这是一道 二分答案 这道题很容易就能想到枚举 x，但是时间复杂度会超市，所以我们需要用二分优化

部分代码：

bool check(ll i, ll x){
    ll pos=lower_bound(b+1, b+n+1, i+x+1)-b-1;
    if(pos<n-m)return 0;
    return (i+x+1)*(pos-n+m)-(sum[pos]-sum[n-m-1]-max(i, b[n-m]))>k-x;
    
}

T4(小信的积木)：

这道题是一道纯暴力，dfs遍历整个棋盘，然后枚举每个棋盘的数字，只要枚举完一种棋盘就ans++，最后输出ans就可以了，非常简单，感觉不应该做为最后一题。

部分代码：

void dfs(ll x, ll y){
    if(x>k+1){
        ans++;
        return;
    }
    if(y>a[x]){
        dfs(x+1, 1);
        return;
    }
    for(ll i=1;i<=n;i++){
        if(i>g[x-1][y]&&i>=g[x][y-1]){
            g[x][y]=i;
            dfs(x,y+1);
        }
    }
}

做题情况

T1：这道题想了半天感觉像是搜索，调了很久样例过了，但是因为没算时间复杂度的原因只拿到了10分，其实正解也不咋么难，很可惜
TLE 10pt

T2：这道题算是比较难的，需要数学推理和概率论，感觉应该放在第四题，这道题我也用dfs搞了半天，但是样例美国，真的很惨。
WA 0pt

T3：这道题也很难，所以我没做。
WA 0pt

T4：这道题正解感觉好简单，但是后来没时间了，导致只能骗分，把 k=1 的情况用dfs写了出来，拿了20分
WA 20pt

总结

预期得分：120pt
实际得分：30pt
啊啊啊，这次实在是太失误了，还是内句话
\huge第一题不要想的太复杂，第二题不要想的太简单
ε=(´ο｀*)))唉，祝我明天模考
\Huge AK！！！！

1 个赞