牛客小白月赛25题解

现场A题是不可能A多少题的，只能靠赛后补补题这样维持生活~
A:AOE还是单体？
思路：贪心，只有人数 > x 我们才会选择团体技能，<= x就直接单体技能就好了。
人数 > x的时候，先排个序，前面n - x个人全部团体技能，后面的全部单体技能。
代码：

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

const int maxn = 2e5 + 10;
typedef long long int ll;
ll a[maxn];
void solved(){
    int n,x;cin>>n>>x;
    ll s = 0;
    for(int i = 1; i <= n; i++)cin>>a[i],s+=a[i];
    if(n <= x){
        cout<<s<<endl;
    }else{
        sort(a + 1, a + 1 + n);
        ll ans = a[n - x] * x;
        for(int i = n - x + 1; i <= n; i++)ans += a[i] - a[n - x];
        cout<<ans<<endl;
    }
}
int main(){
    solved();
    return 0;
} 

C:白魔法师
思路：先用并查集把白色的联通块并起来并且计算这个联通块的个数，然后用邻接表存树(方便我们对黑色的点求联通块)。然后遍历顶点，对于黑色顶点遍历它的所有边，把相邻的白色联通块个数加起来找最大值。
代码：

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

const int maxn = 1e5 + 10;
char s[maxn << 1];
int f[maxn << 1];//f[i]:i的父节点编号 
int siz[maxn << 1];//siz[i]:i的联通块大小 
vector<int>G[maxn];
int find(int x){
    if(f[x] != x){
        return f[x] = find(f[x]);
    }
    return f[x];
}
void unio(int u,int v){
    int fa = find(u),fb = find(v);
    if(fa != fb){
        if(siz[fa] > siz[fb]){
            f[fb] = fa;
            siz[fa] += siz[fb];
        } else{
            f[fa] = fb;
            siz[fb] += siz[fa];
        }
    }
}
void solved(){
    int n;cin>>n; 
    scanf("%s", s + 1);
    for(int i = 1; i <= n; i++)siz[i] = 1;
    for(int i = 1; i <= n; i++)f[i] = i;
    for(int i = 1; i <= n - 1; i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
        if(s[u] == s[v] && s[u] == 'W')unio(u,v);
    }
    for(int i = 1; i <= n; i++)
        if(s[i] == 'W')
            siz[i] = siz[find(i)];
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(s[i] == 'B'){
            int mm = 1;
            for(int j = 0; j < G[i].size(); j++){
                if(s[G[i][j]] == 'W'){
                    mm += siz[G[i][j]];
                }
            }
            ans = max(ans,mm);
        }
    }
    if(ans == 0)
    cout<<n<<endl;
    else cout<<ans<<endl;
}
int main(){
    solved();
    return 0;
} 

D:抽卡
思路：正着计算概率比较复杂，考虑用。 其中 .因为最终结果是
代码：

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

typedef long long int ll;
const ll mod = 1e9 + 7;

const int maxn = 1e5 + 10;
ll a[maxn],b[maxn];
ll fastpow(ll a,ll b){
    ll ans = 1;
    while(b){
        if(b & 1){
            ans = ans * a % mod;
        }
        b >>= 1;
        a = a * a% mod;
    }
    return ans;
}
ll inv(ll a){
    return fastpow(a,mod - 2);
}
void solved(){
    int n;cin>>n;
    for(int i = 1; i <= n; i++)cin>>a[i];
    for(int i = 1; i <= n; i++)cin>>b[i];
    int ans = 1;
    for(int i = 1; i <= n ;i++) {
        ans = ans * (a[i] - b[i]) % mod * inv(a[i]) % mod;
    }
    cout<<(1 - ans + mod) % mod<<endl;
}
int main(){
    solved();
    return 0;
}

E:点击消除
思路：模拟，这个题其实就是括号匹配用栈去模拟就好了。
代码：

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

void solved(){
    string s;cin>>s;
    stack<char>st;
    for(int i = 0; i < s.size(); i++){
        if(st.empty())st.push(s[i]);
        else if(st.top() == s[i]){
            st.pop();
        }else{
            st.push(s[i]);
        }
    }
    string ans;
    while(!st.empty()){
        ans += st.top();st.pop();
    }
    reverse(ans.begin(),ans.end());
    if(ans == "")
        cout<<"0"<<endl;
    else cout<<ans<<endl;
}
int main(){
    solved();
    return 0;
}

F:疯狂的自我检索者
思路：签到题~直接求和最高取5最低取1。。。。
代码：

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

const int maxn = 2e5 + 10;
typedef long long int ll;
int a[maxn];
void solved(){
    int n,m;cin>>n>>m;
    ll s = 0;
    for(int i = 1; i <= n - m; i++){
        cin>>a[i];s += a[i];
    }
    printf("%.5lf %.5lf\n",(s + m) * 1.0 / n,(s + m * 5) * 1.0 / n);
}
int main(){
    solved();
    return 0;
} 

G:解方程
思路：容易发现这个函数是一个单调递增的函数，所以用二分求。(参考兰子姐姐的写法
代码:

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

int a;
long double b,c;
long double check(long double l,long double r){
    if(r - l <= 1e-8)return l;
    long double mid = (r + l) / 2;
    long double temp = 1;
    for(int i = 1; i <= a; i++) temp *= mid;
    if(temp + b * log(mid) < c)return check(mid,r);
    else return check(l,mid); 
}
void solved(){
    cin>>a>>b>>c;
    printf("%.7Lf\n",check(1,c));
}
int main(){
    solved();
    return 0;
}

H:神奇的字母(二)
思路：签到题，直接map统计一下每个字符出现最多次数就好了。
代码：

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

const int maxn = 1e4;

int main(){
    string s;
    while(cin>>s);
    map<char,int>mp;
    for(int i = 0; i < s.size(); i++){
        mp[s[i]]++;
    }
    map<char,int>::iterator it = mp.begin();
    char ss;
    int ans = 0;
    for(;it!=mp.end();it++){
        if(it->second > ans){
            ans = it->second;
            ss = it->first;
        }
    }
    cout<<ss<<endl;
    return 0;
}

I:十字爆破
思路：这个题寒假集训出过一次，统计每行每列的增量，然后计算a(i,j)就是这一行的所有值+这一列的所有值-a(i,j)就好了，不过这题会卡空间，所以用一维数组存，怎么二维转一维呢(i - 1) * m + j就好了。
代码：

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

typedef long long int ll;
const int maxn = 1e6 + 100;
ll a[maxn],b[maxn],c[maxn];
void solved(){
    ll n,m;scanf("%lld%lld",&n,&m);
    ll tot = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ll x;scanf("%lld",&x);
            c[tot++] = x;
            a[i] += x;b[j] += x; 
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ll v = c[(i - 1) * m + j];
            printf("%lld ",v + (a[i] - v) + (b[j] - v));
        }
        printf("\n");
    }
}
int main(){
    solved();
    return 0;
}