牛客小白月赛96 D 最小连通代价

题意: 加边是所有点连通，没有重边和自环,问最小代价加边规则：两点权值奇偶性相同代价为a,否则为b $- 100 \leq a, b \leq 100$

分析： 这题就是一个分类讨论,先读进来统计奇数点和偶数点记 $na$ 为奇偶性相同的点的连边， $nb$ 为奇偶性不同的点的连边, $ji$ 为奇数点, $o u$ 为偶数点 $1. a \leq 0$ and $b \leq 0 :$ 所有可以连的边都连上 $na = C (ji 2) + C (o u 2)$ $nb = ji * o u$

$2. a \leq 0$ and $b > 0 :$ $na = C (ji 2) + C (o u 2)$ 如果全是技术点或者偶数点，则不需要奇数点和偶数点连一条边 $i f (min (ji, o u)) nb = 1;$

$3. a > 0$ and $b \leq 0 :$ 如果既有奇数点又有偶数点，则它们之间的所有边都要，否则我只要n-1条边因为代价大于0 $i f (min (ji, o u))$ $nb = ji * o u;$ $e l se$ $na = n - 1;$

$4. a > 0$ and $b > 0 :$ 如果全是奇数或者偶数点，只取n-1条边即可否则: 如果a<=b: $na = n - 2;$ $nb = 1$ 如果a>b: $nb = n - 1$ 即可

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int n,a,b;
void solve(){
    cin>>n>>a>>b;
    long long ji = 0,ou = 0;
    for(int i = 1;i<=n;++i){
        int x;cin>>x;
        ji+=(x%2==1);
        ou+=(x%2==0);
    }
    long long na = 0,nb =0;
    if(a<=0&&b<=0){
        na = ji*(ji-1)/2+ou*(ou-1)/2;
        nb = ji*ou;
    }else if(a<=0){
        na = (ji-1)*ji/2+ou*(ou-1)/2;
        if(min(ji,ou)) nb = 1;
    }else if(b<=0){
        if(min(ji,ou)) nb = ji*ou;
        else na = n-1;
    }else{
        if(min(ji,ou)==0){
            na = n-1;
        }else{
            if(a<=b){
                na = n-2;
                nb = 1;
            }else nb = n-1;
        }
    }
    cout<<na*a+nb*b<<"\n";
}

int main(){
    ios;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

没开long long WA了好几发