【题解】牛客小白月赛25

写在题解前面的话

本次比赛相对难度不大(毕竟是小白月赛),没有刻意去出防ak题(因为自己太菜了出不了)。整场比赛没有难度高的算法,代码量也很小,希望给大家带来了不错的比赛体验~
这场比赛的题目与其说是考算法,不如说是考语法和程序设计中的一些其他知识更多一些,大家在学算法的时候往往会忽视一些细节问题,以后能重视起来会比较好。
E题的测试用例出弱了,放过了部分的错误算法。样例已经加强(但不会rejudge)
,大家可以重新提交试试,不影响成绩。

A

知识点:贪心
思路:显然aoe伤害打的怪物越多是越赚的,临界值是消耗 正好打 个怪物,这时aoe和单体伤害的效率是相同的。所以可以采用以下思路:先用aoe击杀到正好剩x个怪,然后剩下的全部用单体击杀即可。
私货:aoe(Area of effect),范围型技能。
标程:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[222222];
int main(){
    ll n,x,i,j,k;
    cin>>n>>x;
    for(i=0;i<n;i++)cin>>a[i];
    if(x>=n){
        ll sum=0;
        for(i=0;i<n;i++)sum+=a[i];
        cout<<sum;
        return 0;
    }
    sort(a,a+n);
    ll sum=a[n-x]*x;
    for(i=n-x+1;i<n;i++)sum+=a[i]-a[n-x];
    cout<<sum;
}

B

知识点:组合数学
思路:对于 是偶数和奇数的情况分别判断:
如果k是偶数,那么字符串一定是a....b或者b....a的形式。我们可以拿出 个a 以及 个b先摆好:
ababab...abab
然后还剩下的a和b往里面插入,就变成了很经典的整数划分问题: 个物品放进 个格子里,有多少多方法(或者一个整数 拆分成 k/2 个非负整数之和的拆分方式,不同位置视为不同拆法)。
设将整数 拆成 个非负整数的方案数为
假设第一个数为 ,那么这相当于把 拆成 个非负整数的方案数为
假设第一个数不是 ,那么相当于把 拆成 个非负整数的方案数为
也就是说
发现了什么?是不是联想到了杨辉三角,也就是对应的组合数。
我们可以列几个简单的例子,
然后假设
用数学归纳法可以证明:
那么有



故假设成立,可由 推至全部整数。
解决了整数划分问题,这种情况就解决了。
b....a形式同理。

如果k是奇数,那么字符串一定是a....a或者b....b的形式。解决方式和上面类似。但要注意的是这时两种计数的个数是不等的。请同学们自行思考解决。
私货:这道题应该是本场比赛中难度最大的了。之所以放在了第二个位置仅仅因为题目是按字符顺序排序的(才不是想故意卡大家做题顺序)。这道题的idea在半年前就有了,这一次终于出成了题目也算了却了一个心愿w
标程:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1,a=a*a%mod;
    }
    return res;
}
ll inv(ll x){return power(x,mod-2);}
ll C(ll a,ll b){
    ll t=1;
    for(int i=1;i<=b;i++)t=t*(a-i+1)%mod*inv(i)%mod;
    return t;
}
ll f(ll n,ll m){
    if(n<=0||m<0)return 0;
    return C(n+m-1,m);
}
int main(){
    ll n,m,k;
    cin>>n>>m>>k;
    if(k&1)
        cout<<(f(k/2+1,n-k/2-1)*f(k/2,m-k/2)+f(k/2,n-k/2)*f(k/2+1,m-k/2-1))%mod;
    else cout<<2*f(k/2,n-k/2)*f(k/2,m-k/2)%mod;
}

C

知识点:图论、并查集
思路:如果将一个黑色点染成白色,那么将得到一个白色连通块,这个连通块由和这个黑色点连结的所有白色连通块组成。
如果将一个白色点染成白色,那么不会有任何变化。
所以我们可以先并查集预处理一下,把所有白色连通块的大小求出来,并把所有白色点对应的连通块表示一下。连通块的大小可以dfs或者统计并查集根的孩子总数得出。
然后统计所有黑色点的邻点连通块大小即可。要注意特判全部是白色点的情况。
私货:如果做过寒假集训营(第一场)的maki和tree那道题的话,这道题做起来会相对比较轻松,因为思路类似。另外又白又膜,这种危险的出题人还是打死好了(不
(放一下寒假集训营1的链接吧,也是我出的:https://ac.nowcoder.com/acm/contest/3002 如果没有购买也可以通过点别人的代码来看题,这是牛客网的漏洞,悄悄透露给大家,清楚妹妹不要打我qwq)
代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>g[200020];
string s;
ll fa[200020],kdm[200020],sz[200020];
ll f(ll x){
    if(fa[x]==x)return x;
    return f(fa[x]);
}
void uni(ll x,ll y){
    ll p=f(x),q=f(y);
    if(p!=q){
        if(kdm[p]<kdm[q]){
            fa[p]=q;
            kdm[q]+=kdm[p]+1;
        }
        else{
            fa[q]=p;
            kdm[p]+=kdm[q]+1;
        }
    }
}
int main(){
    ll n,i,j,k,x,y;
    cin>>n>>s;
    for(i=1;i<=n;i++)fa[i]=i;
    for(i=1;i<n;i++){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
        if(s[x-1]=='W'&&s[y-1]=='W')uni(x,y);
    }
    for(i=1;i<=n;i++)
        if(s[i-1]=='W')sz[i]=kdm[f(i)]+1;
    ll ma=0;
    for(i=1;i<=n;i++){
        if(s[i-1]=='B'){
            ll sum=1;
            for(j=0;j<g[i].size();j++)
                if(s[g[i][j]-1]=='W')sum+=sz[g[i][j]];
            ma=max(ma,sum);
        }
    }
    if(ma==0)cout<<n;
    else cout<<ma;
}

D

知识点:概率论
思路:其实这题根本没有什么概率论知识,想考察大家更多的是逆元的知识(相信有很多萌新是不知道或者不会求逆元的)
概率论方面,求抽到想要的卡的概率,直接先求出全部抽完都没有想要的卡的概率,显然是
其中
然后用1减去这个概率就可以了。
这里给萌新们讲讲逆元的知识(会的大佬可以跳过了)
所谓逆元,即在模 意义下的值。设该值为 ,即 ,也就是满足 的那个a
怎么求这个数呢?其实很简单。由费马小定理知, 互素时,
那么
也就是说, 就是 在模 意义下的逆元了。
现在这道题要求 ,相当于求 乘以 的逆元。逆元的知识很重要,可以把分数当成整数进行各种运算。
私货:ue对不起~(>=<)
标程代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){return power(x,mod-2);}
ll a[100010],b[100010];
int main(){
    ll n,k,i,j;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    for(i=0;i<n;i++)cin>>b[i];
    ll res=1;
    for(i=0;i<n;i++){
        res=res*(a[i]-b[i])%mod*inv(a[i])%mod;
    }
    cout<<(mod+(1-res))%mod;
}

E

知识点:字符串
思路:这道题解法很多,这里分享两种解法。
第一个解法是用栈,相对容易理解。遍历字符串,遇到相同字母出栈,否则入栈即可。
另外一个解法是,开一个标记数组去记录哪些被消除过了,再用另外一个数组记录目前存活的字符串里,每个字符的左字符位置。然后用一个变量维护消除的左端点位置,遍历时如果能消除就让这个变量左移,并同时更新两个数组的情况,否则重置到右边的位置。详细见标程代码。
标程代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int lf[300030],mk[300030];
int main(){
    ll n,i,j,k,x=0;
    string s;
    cin>>s;
    n=s.length();
    for(i=0;i<n;i++)lf[i]=i-1;
    for(i=0;i<n-1;i++){
        int l=i,r=i+1;
        if(s[i]==s[i+1]){

            while(l>=0&&r<n&&s[l]==s[r]){
                mk[l]=mk[r]=1;
                l=lf[l];
                r++;
            }
            lf[r]=l;
        }
        i=r-1;
    }
    for(i=0;i<n;i++){
        if(!mk[i])cout<<s[i],x=1;
    }
    if(!x)cout<<0;
}

F

知识点:概率、贪心
签到题。假设所有隐藏的分数为1或5即可。
标程代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){

    ll n,m;
    double sum=0;
    cin>>n>>m;
    n-=m;
    for(int i=0;i<n;i++){
        double x;
        cin>>x;
        sum+=x;
    }
    printf("%.5lf %.5lf",(sum+m)/(n+m),(sum+5*m)/(n+m));
}

G

知识点:二分
很容易发现左边是一个单调增的函数,所以二分求解即可。值得注意的是如果用double可能出现tle的情况(实测double精度有问题,导致后面无限不动)。解决方法有两种,一种是换long double,另外一种是进行足够多次二分即可(例如1000次二分),可以避免tle的出现。
标程:

#include<bits/stdc++.h>
using namespace std;
#define ld long double
int a;
ld b,c;
ld bs(ld l,ld r){
    if(r-l<=1e-8)return l;
    ld mid=(r+l)/2;
    ld res=1;
    for(int i=0;i<a;i++)res*=mid;
    res+=b*log(mid);
    if(res<c)return bs(mid,r);
    return bs(l,mid);
}
int main(){
    cin>>a>>b>>c;
    printf("%.7Lf",bs(1,c));
}

H

知识点:无
思路:这道题想更多的考察大家对“若干组输入”的处理方式。主要的解决方法有以下几种:
①while(cin>>str)
②while(scanf("%s",str)!=EOF) //EOF可以用-1代替。
③while(gets(str)!=NULL)
第一个是c++写法,后两个是C语言写法。注意对应的头文件即可(或使用万能头文件)
标程代码:

#include<bits/stdc++.h>
using namespace std;
string s;
int t[26];
int main(){
    int i;
    while(cin>>s){
        for(i=0;i<s.length();i++)t[s[i]-'a']++;
    }
    int ma=0,m1=0;
    for(i=0;i<26;i++){
        if(ma<t[i])ma=t[i],m1=i;
    }
    cout<<char('a'+m1);
}

I

知识点:预处理。
思路:开两个数组分别处理每一行的和以及每一列的和。之后对应顶点输出(对应行+对应列-该顶点)即可。
这道题更难的地方是n和m大小未定。解决方法有两种,一个是动态内存(malloc或者vector),另一种方法是用一维数组代替二维数组(a[i][j]和a[i*m+j]等价)。这里标程用的是第二种方法。
标程代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1000010];
ll sr[1000010],sc[1000010];
int main(){
    int n,m,i;
    cin>>n>>m;
    for(i=0;i<n*m;i++)scanf("%lld",&a[i]);
    for(i=0;i<n*m;i++){
        sr[i/m]+=a[i];
        sc[i%m]+=a[i];
    }
    for(i=0;i<n*m;i++){
        printf("%lld ",sr[i/m]+sc[i%m]-a[i]);
        if(i%m==m-1)printf("\n");
    }
}

J

知识点:位运算
思路:做这一类题有个技巧,就是每一位分别去处理,1e18对应二进制的64位。
可以先统计出每一位的1的个数和0的个数,那么异或和就可以用组合数学的方式求出来了,因为异或为1一定是:


或者


这两种情况中的一种,分别处理即可。(别忘了对应位最后乘以
标称代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1000000007;
ll a[1000010];
ll t[64];
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1,a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
ll f(ll x,ll y){
    if(x<y)return 0;
    ll res=1;
    for(ll i=0;i<y;i++)res=res*(x-i)%mod,res=res*inv(i+1)%mod;
    return res;
}
int main(){
    ll n,m,i,j,x;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>x;
        j=0;
        while(x){
            if(x&1)t[j]++;
            j++,x>>=1;
        }
    }
    ll sum=0;
    for(i=0;i<64;i++){
        sum+=(1LL<<i)%mod*(f(t[i],3)+f(n-t[i],2)*t[i]%mod)%mod;
        sum%=mod;
    }
    cout<<sum;
}
全部评论
小声,出题人码字变成了"标称代码",应该没有人发现吧
1 回复
分享
发布于 2020-05-18 12:17
E题我拿string的erase从后往前删,不知道啥复杂度,但是还是过了加强的数据emm
点赞 回复
分享
发布于 2020-05-17 22:54
淘天集团
校招火热招聘中
官网直投
兰子哥哥
点赞 回复
分享
发布于 2020-05-18 10:54
感觉是对萌新很不错的一套题!
点赞 回复
分享
发布于 2020-05-18 20:58
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786077之前寒假集训营这道题 uni函数里面为什么要kdm[p]>kdm[q]来决定谁是父节点,为啥倒过来就不对呢?弱鸡没太懂
点赞 回复
分享
发布于 2020-05-18 21:24
所以今天的小白月赛不简单啊
点赞 回复
分享
发布于 2020-05-18 22:01
B题的n个物品放进m个格子,那么种类数不是C(n + m - 1, m - 1), 为什么是C(n +m - 1, m)
点赞 回复
分享
发布于 2020-05-19 03:04
楼主您好,B题您分析的整数划分 感觉跟这句话有点类似:(把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?poj1664) 但是你分析得dp方程和poj这道题的dp方程有点不太一样。还是说你的这种分析也能写poj的这题?
点赞 回复
分享
发布于 2020-05-22 15:52
大佬,小白想问一下,D题为什么输出要那样?T^T
点赞 回复
分享
发布于 2020-07-24 14:13
这个G,我一直T ,我以为是x*x*x上界会爆掉double,看到很多人的上界都是1e9 ,1e9/2第一次二分,a = 3时绝对会爆掉的呀,是没有这种数据嘛?建议加个注释😀,一直在想怎么比较~
点赞 回复
分享
发布于 2020-12-30 14:03

相关推荐

13 5 评论
分享
牛客网
牛客企业服务