【题解】牛客小白月赛25

感想：有一说一这次的小白月赛还真的挺舒服的了，代码量小，而且大部分题如果做过类似的题其实很容易就想出来怎么做了，除了B感觉是一个组合数学不是那么好想（数学太差啦），感觉这套题对小白而言是一套挺有意思的题，喜欢这套题。

A AOE还是单体？
三分的模板题，用三分枚举使用多少次第二个技能，然后输出最后的最优值即可。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=2e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

ll a[maxn];
int n,x;
ll val(ll mid){
    ll sum=mid*x;
    for(int i=1;i<=n;i++){
        if(a[i]>mid) sum+=a[i]-mid;
    }
    return sum;
}

int main(){
    scanf("%d%d",&n,&x);
    ll sum1=0,sum2=0;
    ll mx=1e18;
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
        sum1+=a[i];
        mx=min(mx,a[i]);
    }
    ll l=0,r=1e9;
    while(l<r){
        ll lmid=(2*l+r)/3,rmid=(2*r+l+2)/3;
        if(val(lmid)<val(rmid)){
            r=rmid-1;
        }
        else l=lmid+1;
    }
    printf("%lld",min(sum1,val(l)));
    return 0;
}

B k-size字符串
有空去想了，就是一个组合数学题，是小球放到盒子那种类型的。
对于k，我们可以先放好这个k，也就是说：可以先abab……,baba……，相当于把盒子放好，让你往里面填小球。
那么对于k是奇偶分为两种情况：（因为奇数除2向下取整）
k是奇数: $图片说明$
k是偶数: $图片说明$
$图片说明$ 是，b个剩余的球放到a个盒子里面。
那 $图片说明$ 怎么算呢？
我们知道如果盒子不为空可以用隔板法来算，那么同理，现在盒子为空，我们就默认盒子都有一个球，那就是一共有n+m个球，有n+m-1个空隙，插入n-1个板隔开，所以答案就是 $图片说明$ 。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

ll qPow(ll a,ll b){
    ll ans=1;
    while(b>0){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

ll C(ll a,ll b){
    ll ans=1;
    for(int i=1;i<=b;i++){
        ans=(ans*(a-i+1)%mod*qPow(i,mod-2))%mod;
    }
    return ans;
}

ll CC(ll a,ll b){
    if(a<=0||b<0) return 0;
    return C(a+b-1,a-1);
}

int main(){
    ll n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    if(k&1){
        printf("%lld",(CC(k/2+1,n-k/2-1)*CC(k/2,m-k/2)+CC(k/2,n-k/2)*CC(k/2+1,m-k/2-1))%mod);
    }
    else{
        printf("%lld",2*CC(k/2,n-k/2)*CC(k/2,m-k/2)%mod);
    }
    return 0;
}

C 白魔法师
树上DP，dp[i][0]表示整个以i为根子树一次都没有用过技能能得到的连通值,dp[i][1]表示整个以i为根子树使用了一次技能能得到的连通值。
然后根据当前点是W还是B来分类讨论一下：
如果当前点是W，那么:
$图片说明$
更新完dp[i][0]后
$图片说明$
其中mx为dp[to][1]-dp[to][0]里面的最大值，因为只能用一次技能，所以要找到自己孩子子树里面用一次技能获得收益最多的点。

如果当前点是B，那么:
$图片说明$
$图片说明$

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

VI edge[maxn];
char s[maxn];

int dp[maxn][2];

void dfs(int u,int fa){
    int mx=0;
    for(int i=0;i<edge[u].size();i++){
        int to=edge[u][i];
        if(to==fa) continue;
        dfs(to,u);
        if(s[u]=='B'){
            dp[u][1]+=dp[to][0];
        }
        else{
            mx=max(dp[to][1]-dp[to][0],mx);
            dp[u][0]+=dp[to][0];
        }
    }
    if(s[u]=='B'){
        dp[u][0]=0;
        dp[u][1]++;
    }
    else{
        dp[u][0]++;
        dp[u][1]=dp[u][0]+mx;
    }
}

int main(){
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        edge[x].pb(y);
        edge[y].pb(x);
    }
    dfs(1,0);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i][0]);
        ans=max(ans,dp[i][1]);
    }
    printf("%d",ans);
    return 0;
}

D 抽卡
逆元应用题，因为只需要抽到一张或以上就行，那么概率就是100%减去一张都抽不到的概率。
因为要取模，所以只需要把下面的除数用费马小定理，用快速幂qPow(x,mod-2)就好了。

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

ll qPow(ll a,ll b){
    ll ans=1;
    while(b>0){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

ll a[maxn],b[maxn];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",b+i);
    }
    ll tmp1=1,tmp2=1;
    for(int i=1;i<=n;i++){
        tmp1=(tmp1*(a[i]-b[i]))%mod;
        tmp2=(tmp2*a[i])%mod;
    }
    printf("%lld\n",(1-tmp1*qPow(tmp2,mod-2)%mod+mod)%mod);
    return 0;
}

E 点击消除
栈的模板题，就用栈模拟一下，从左往右扫一遍字符串，如果栈顶和当前枚举到的字符相同就把pop栈顶，否则就把字符存入栈中，最后把栈内元素倒出来逆序输出就好了。

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=3e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

string s;

int main(){
    cppio;
    cin>>s;
    int n=s.length();
    stack<char> sta;
    for(int i=0;i<n;i++){
        if(!sta.empty()){
            if(sta.top()==s[i]) sta.pop();
            else sta.push(s[i]);
        }
        else{
            sta.push(s[i]);
        }
    }
    if(sta.empty()) cout<<0;
    string ss;
    while(!sta.empty()){
        ss+=sta.top();
        sta.pop();
    }
    reverse(ss.begin(),ss.end());
    cout<<ss;
    return 0;
}

F 疯狂的自我检索者
最小平均分就是未知的都是1分，最大平均分就是未知的都是5分。
答案就是：
$图片说明$
$图片说明$

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e3+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    double sum=0;
    for(int i=1;i<=n-m;i++){
        double x;
        scanf("%lf",&x);
        sum+=x;
    }
    printf("%.5lf ",(sum+m*1)/n);
    printf("%.5lf ",(sum+m*5)/n);
    return 0;
}

G 解方程
因为方程 $图片说明$
可以写成 $图片说明$
因为 $图片说明$ 是单调的， $图片说明$ 也是单调的，所以f(x)就是一个单调函数，所以可以用二分来找到解。
但是要用long double，因为1e-7这个精度太高了，double没有这么高的精度。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int main(){
//    printf("%lf\n",exp(1));
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    long double l=0,r=1e9;
    while(r-l>eps){
        long double mid=(r+l)/2;
        long double tmp=pow(mid,a)+b*log(mid);
        if(tmp<c) l=mid;
        else r=mid;
    }
    printf("%.7Lf\n",l);
    return 0;
}

H 神奇的字母（二）
模拟一下算一下出现次数最多的字母就好了。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e3+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

char s[maxn];
int num[maxn];

int main(){
    int mx=0;
    while(gets(s)){
        int n=strlen(s);
        if(n==0) break;
        for(int i=0;i<n;i++){
            num[s[i]-'a']++;
            if(num[mx]<num[s[i]-'a']) mx=s[i]-'a';
        }
    }
    printf("%c",'a'+mx);
    return 0;
}

I 十字爆破
先算一下二维前缀和，然后对于每个点的答案就是
$图片说明$
也就是取一行和取一列然后去掉重复取的那个点。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

vector<ll> mp[maxn];
vector<ll> sum[maxn];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    sum[0].resize(m+2,0); 
    for(int i=1;i<=n;i++){
        mp[i].resize(m+20,0);
        sum[i].resize(m+20,0);
        for(int j=1;j<=m;j++){
            scanf("%lld",&mp[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+mp[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ll summ=sum[n][j]-sum[n][j-1]+sum[i][m]-sum[i-1][m];
            printf("%lld%c",summ-mp[i][j]," \n"[j==m]);
        }
    }
    return 0;
}

J 异或和之和
一般这种二进制求和的题很多都是求每一位的贡献的，这题当然也不例外了。
先算在所有数里面，每一位为1出现多少次，为0出现多少次。
然后每一位的贡献就是：
$图片说明$
也就是：如果这一位是1，那么如果要有贡献，其他两个数要么都是1要么都是0，对于其他两个数都是0，只需要用组合数C(0的数量,2)就好，对于其他两个数都是1，我们就算3个都是1有多少种情况，也就是C(1的数量,3)。
最后把贡献加起来就好了。

代码:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

ll num[100][2];

ll qPow(ll a,ll b){
    ll ans=1;
    while(b>0){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        ll x;scanf("%lld",&x);
        for(int j=0;j<62;j++){
            if((1ll<<j)&x){
                num[j][1]++;
            }
            else num[j][0]++;
        }
    }
    ll sum=0;
    for(int i=0;i<62;i++){
        ll tmp=0;ll one=num[i][1],zero=num[i][0];ll k=(1ll<<i)%mod;
        tmp=(tmp+k*one%mod*zero%mod*(zero-1)%mod*qPow(2,mod-2))%mod;
        tmp=(tmp+k*one%mod*(one-1)%mod*(one-2)%mod*qPow(6,mod-2)%mod)%mod;
        sum=(sum+tmp)%mod;
    }
    printf("%lld\n",sum);
    return 0;
}