【题解】牛客小白月赛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(){
    freopen("6.in","r",stdin);
    freopen("6.out","w",stdout);
    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(){
    freopen("8.in","r",stdin);
    freopen("8.out","w",stdout);
    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;
}