Codeforces Round #435 (Div. 2)

A. Mahmoud and Ehab and the MEX

题目链接：http://codeforces.com/contest/862/problem/A

题目意思：现在一个数列中有n个数，每个数小于等于100，现在要让这个数列的met=k，意思是如果从1-100中第一个未出现的数字为met。

题目思路：在[0,k)区间内所有在数列中不存在的数的数量+check(k),check()表示判断k是否存在，如果存在返回1，不存在返回0；

代码：

//Author: xiaowuga
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX INT_MAX
#define mem(s,ch) memset(s,ch,sizeof(s))
const long long N=100000; 
const long long mod=1e9+7; 
typedef long long LL;
typedef int II;
typedef unsigned long long ull;
#define nc cout<<"nc"<<endl
#define endl "
"
II a[101]={0};
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    II n,x;
    cin>>n>>x;
    for(II i=0;i<n;i++){
        II t;
        cin>>t;
        a[t]++;
    }
    II ans=0;
    for(II i=0;i<x;i++){
        if(a[i]==0) ans++;
    }
    if(a[x]) ans++;
    cout<<ans<<endl;
    return 0;
}

B. Mahmoud and Ehab and the bipartiteness

题目链接：http://codeforces.com/contest/862/problem/B

题目意思： 给定一个n 个节点  n-1 条边的图，求最多还能加几条边，保证 这个图不存在重边，自环，并且是一个二分图

题目思路：首先一个树是一个二分图，我们可以通过dfs可以把一个树的节点push进两个vector中，这样就构造了一个二分图，那么答案就是size1×size2-n+1.

代码：

//Author: xiaowuga
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX INT_MAX
#define mem(s,ch) memset(s,ch,sizeof(s))
const long long N=100000; 
const long long mod=1e9+7; 
typedef long long LL;
typedef int II;
typedef unsigned long long ull;
#define nc cout<<"nc"<<endl
#define endl "
"
II n;
vector<int>G[100000+10];
vector<int>a[2];
void dfs(II u,II fa,II s){
    a[s].push_back(u);
    for(II i=0;i<G[u].size();i++){
        II v=G[u][i];
        if(v==fa) continue;
        dfs(v,u,s^1);
    }
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    if(n==1){cout<<0<<endl;return 0;}
    for(II i=0;i<n-1;i++){
        II x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,0,0);
    LL sz1=a[1].size();
    LL sz2=a[0].size();
    cout<<sz1*sz2-n+1<<endl;
    return 0;
}