牛客小白月赛25

A
题意:1个单体技能,1个群体技能,然后单体技能消耗1,群体技能消耗x,然后问kill掉所有的怪,需要消耗多少
题解:贪心,如果怪的数量小于x个是肯定不划算的,所以就是先排个序,然后对于倒数第x个,看看消耗多少,然后再加上前面的群体对于后面的怪攻击完剩余的血量用单体来打需要的消耗

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

B
题意:求满足的有多少种可能
题解:先按照要求来构成一个无非就是ababababab....或者bababababa.....这两种情况
然后对于剩下的数,可以用隔板法或者母函数来求多少种可能,(没想起这个.......)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;

int _pow(int a,int n)
{
    int res=1; a%=mod;
    while(n)
    {
        if(n&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        n>>=1;
    }
    return res;
}
int calc(int n,int m)
{
    if(n-1<0||m-1<0) return 0;
    if(n-1<m-1) return 0;
    n--; m--;
    int fm=1; int fz=1;
    for(int i=n,j=1;j<=m;j++,i--) fm=1ll*fm*i%mod;
    for(int i=1;i<=m;i++) fz=1ll*fz*i%mod;
    fz=_pow(fz,mod-2);
    return 1ll*fz*fm%mod;
}



int main(void)
{
    int n,m,k; scanf("%d%d%d",&n,&m,&k);
    int k1=k/2; int k2=k-k1;
    int res=1ll*calc(n,k1)*calc(m,k2)%mod+1ll*calc(m,k1)*calc(n,k2)%mod;
    res=(res%mod+mod)%mod;
    printf("%d\n",res);
    return 0;
}
//code:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43749429

C
题意:给定一棵树,然后每个节点都有颜色,现在可以有一次操作,就是把某一个黑节点变为白节点,然后问最多相连的白节点数能有多少
题解:连通块
对于一个白节点求与他相连的白节点的个数有多少,记录其个数,并把这些白节点标记为相同的一个数,然后下来就可以直接对于每个节点求值,然后取最大
如果是白色节点,可以直接查找与其相同的白色节点的个数(最后答案除了全是白色节点以外,不可能是这个答案)
对于每个黑色节点,求与之相连的白色节点的值,这个值是上面白色节点值的解释,然后求和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
vector<int> m[100005];
int n;
int flag[100005];
int sum[100005];
int cnt=1;
void dfs(int u,int er,int fl)
{
    flag[u]=fl;
    sum[fl]++;
    for(int i=0; i<m[u].size(); i++)
    {
        int v=m[u][i];
        if(s[v-1]=='W'&&v!=er)
            dfs(v,u,fl);
    }
}
signed main()
{
    cin>>n;
    cin>>s;
    for(int i=0; i<n-1; i++)
    {
        int a,b;
        cin>>a>>b;
        m[a].push_back(b);
        m[b].push_back(a);
    }
    for(int i=1; i<=n; i++)
    {
        if(!flag[i]&&s[i-1]=='W')
        {
            cnt++;
            dfs(i,0,i);
        }
    }
    int ans=-1;
    for(int i=1; i<=n; i++)
    {
        if(s[i-1]=='W')
            ans=max(ans,sum[flag[i]]);
        else
        {
            int cl=1;
            for(int j=0; j<m[i].size(); j++)
            {
                if(s[m[i][j]-1]=='W')
                    cl+=sum[flag[m[i][j]]];
            }
            ans=max(ans,cl);
        }
    }
    cout<<ans;
}

D
题意:求概率.....(被它要的那个x,给迷惑了,太菜了,然后就是求个 $图片说明$ 加上取模......... )
题解:抽到卡就算的话,那么我们求一张都抽不到的概率,最后再用1减去即可
再加上取模,取模的话用费马小定理即可
$图片说明$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1000000007;
int a[10000009];
ll inv(ll x,ll y)
{
    ll re=1;
    while(y)
    {
        if(y&1)
            re=1ll*re*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return re;
}
signed main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
    ll ans=1;
    for(int i=0; i<n; i++)
    {
        ll x;
        cin>>x;
        ans=(a[i]-x)*inv(a[i],mod-2)%mod*ans%mod;
    }
    ans=(1-ans+mod)%mod;
    cout<<ans;
}

E
题意:相连的两个字符相同直接消除,消除后的相连的两个字符再相同,接着消除,问最后剩下啥
题解:栈模拟题目,要压入的如果与栈顶相同,弹出,否则压入当前字符

#include<bits/stdc++.h>
using namespace std;
signed main()
{
    string s;
    cin>>s;
    stack<char> s1;
    char flag='#';
    for(int i=0; i<s.size(); i++)
    {
if(s1.empty()){s1.push(s[i]);continue;}
if(s1.top()==s[i])s1.pop();
else s1.push(s[i]);

    }
    string t;
    while(!s1.empty())
        t+=s1.top(),s1.pop();
    reverse(t.begin(),t.end());
    cout<<t;
    if(!t.size())cout<<0;
}

F
题意:求一个最大平均值,和最小平均值
题解:最大的全选5,最小的全选1

#include <iostream>
using namespace std;
int main(){
    int i,m,n;
    cin>>m>>n;
    double a,sum=0;
    for(i=0;i<m-n;i++)
        cin>>a,sum+=a;
    printf("%.5f %.5f",(sum+n)/m,(sum+5*n)/m);
    return 0;
}

G
题意:解方程
题解:这个函数是一个单调函数,单调函数求解,按照初中的二分值法....就是二分枚举每个值,然后求最接近的那个就是答案
补充点,如果是双调的要用三分
二分个几百次基本上得到的答案,精确度就满足题意了......

#include<bits/stdc++.h>
using namespace std;
int a,b,c;
double l=1,r=1e9,mid;
int main() {
    scanf("%d%d%d",&a,&b,&c);
    for(int i=1;i<=100;i++){
        mid=(l+r)/2;
        if(pow(mid,a)+b*log(mid)>=c)
            r=mid;
        else
            l=mid;
    }
    printf("%.8lf",l);
    return 0;
}

H
题意:查出现最多的字符,并输出
题解:数就完事了

#include<bits/stdc++.h>
using namespace std;
int m[128];
int main(){
    char c,ans;
    int mx=0;
    while(scanf("%c",&c)!=EOF)++m[c];
    for(int i='a';i<='z';++i)
    if(m[i]>mx)mx=m[i],ans=char(i);
    printf("%c",ans);
}

I
题意:对于每个i,j位输出其这一行加这里列所有的元素的值求和,并减去i,j元素位置的值
题解:预处理一下,然后直接输出

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
    cin>>n>>m;
    long long x[n+5][m+5];
    memset(x,0,sizeof(x));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>x[i][j];
            x[0][j]+=x[i][j];
            x[i][0]+=x[i][j];
        }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<x[0][j]+x[i][0]-x[i][j];
            if(j!=m)
                cout<<' ';
        }
        cout<<endl;
    }
    return 0;
}

J
题意:选取三个数求一个异或值,然后对于所有的情况,求异或值的和
题解:这个不会.......
官方的题解写的方法基本上都是那样做的
把二进制后能异或出1的情况进行求和,差不多就完了....

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll C1(ll x){return x*(x-1)*(x-2)/6;}
ll C2(ll x){return x*(x-1)/2;}
int cnt[65];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        ll x;cin>>x;
        for(int j=0;j<=64;j++){
            if((x>>j)&1)cnt[j]++;
        }
    }
    const ll mod=1e9+7;
    ll ans=0;
    for(int i=0;i<64;i++){
        ll z=cnt[i];
        ll f=n-cnt[i];
        ans=ans+(1ll<<i)%mod*(C1(z)%mod+C2(f)%mod*z%mod);
        ans%=mod;
    }
    cout<<ans<<endl;
}
//code:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43750830