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=;

 const long long mod=1e9+;

 typedef long long LL;

 typedef int II;

 typedef unsigned long long ull;

 #define nc cout<<"nc"<<endl

 #define endl "\n"

 II a[]={};

 int main() {

     ios::sync_with_stdio(false);cin.tie();

     II n,x;

     cin>>n>>x;

     for(II i=;i<n;i++){

         II t;

         cin>>t;

         a[t]++;

     }

     II ans=;

     for(II i=;i<x;i++){

         if(a[i]==) ans++;

     }

     if(a[x]) ans++;

     cout<<ans<<endl;

     return ;

 }

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=;

 const long long mod=1e9+;

 typedef long long LL;

 typedef int II;

 typedef unsigned long long ull;

 #define nc cout<<"nc"<<endl

 #define endl "\n"

 II n;

 vector<int>G[+];

 vector<int>a[];

 void dfs(II u,II fa,II s){

     a[s].push_back(u);

     for(II i=;i<G[u].size();i++){

         II v=G[u][i];

         if(v==fa) continue;

         dfs(v,u,s^);

     }

 }

 int main() {

     ios::sync_with_stdio(false);cin.tie();

     cin>>n;

     if(n==){cout<<<<endl;return ;}

     for(II i=;i<n-;i++){

         II x,y;

         cin>>x>>y;

         G[x].push_back(y);

         G[y].push_back(x);

     }

     dfs(,,);

     LL sz1=a[].size();

     LL sz2=a[].size();

     cout<<sz1*sz2-n+<<endl;

     return ;

 }