【牛客训练记录】牛客小白月赛105

训练情况

赛后反思

看十佳歌手去了，比较晚回来，只开了A题，B题不看数据范围直接一眼丁真直接WA了一发

A题

两个数相乘进行比较，再判断即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

void solve(){
    int a1,b1,a2,b2; cin>>a1>>b1>>a2>>b2;
    if(a1*b1<a2*b2) cout<<"lz"<<endl;
    else cout<<"gzy"<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}

B题

刚开始想直接扔到 double 里面，然后乘 \(10^6\) 再取 int，但是数字的长度为 \(2\times 10^5\) 用 double 存会炸，所以我们选择字符串做法，对于只有整数部分的，我们直接在后面补 .000000，如果有小数部分（防止小数位不足 6 位）就补 000000，最后取到小数后六位，直接进行比较即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

void solve(){
    string a,b; cin>>a>>b;
    if(a.find('.') == string::npos) a+=".000000";
    else a+="000000";
    if(b.find('.') == string::npos) b+=".000000";
    else b+="000000";
    a.erase(a.find('.') + 7);
    b.erase(b.find('.') + 7);
    if(a == b) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}

D题

题目有 \(m\) 种限制 \(i,j\) 花的颜色要相同，我们使用DSU（并查集）维护联通块中的颜色，我们只需要把联通块中出现次数最多的颜色留下来，其他的颜色全部染成出现次数最多的颜色，所以答案就是联通块大小 - 出现次数最多的颜色求个和即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 2e5 + 3;

int n,m;
int a[N];
int fa[N];

int Find(int x){
    if(fa[x] == x) return x;
    return fa[x] = Find(fa[x]);
}

void Union(int x,int y){
    x = Find(x); y = Find(y);
    if(x == y) return;
    fa[y] = x;
}

void solve(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++) fa[i] = i;
    for(int i = 1;i<=n;i++) cin>>a[i];
    for(int i = 1;i<=m;i++){
        int x,y; cin>>x>>y;
        Union(x,y);
    }
    map<int,map<int,int>> cnt;
    for(int i = 1;i<=n;i++){
        int x = Find(i);
        cnt[x][a[i]]++;
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        if(!cnt[i].size()) continue;
        int siz = 0;
        int ma = 0;
        for(auto j:cnt[i]){
            siz += j.second;
            ma = max(ma,j.second);
        }
        ans+=siz-ma;
    }
    cout<<ans<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}