codeforces _ 补题

C. Ball in Berland

传送门：Problem - C - Codeforces

题意：

 思路：容斥原理

考虑 第 i 对情侣组合  ，男生为 a ，女生为 b ，那么考虑与之匹配的情侣 必须没有 a | b

，一共有 k 对情侣， a | b 可以表示为 k - cnt[a] - cnt[b] + 1 ( cnt[a] 表示为有男生 a 的方案数 )

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n , m , k; cin >> n >> m >> k;vector<int> cnta( n + 1 ) , cntb( m + 1 ) , a( k + 1 ) , b( k + 1 );for( int i = 1 ; i <= k ; i++ ) cin >> a[i] , cnta[a[i]]++;for( int i = 1 ; i <= k ; i++ ) cin >> b[i] , cntb[b[i]]++;int ans = 0;for( int i = 1 ; i <= k ; i++ ){ans += k - cnta[a[i]] - cntb[b[i]] + 1;}cout << ans / 2 << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}

B. Sifid and Strange Subsequences

传送门：Problem - B - Codeforces

题意：

 思路：

我们要保证 | a[i] - a[j] | 的最小值 要 >= MAX （ MAX为 a[i] 中的某一个值 ）

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n; cin >> n;vector<int> a(n + 1);for( int i = 1 ; i <= n ; i++ ) cin >> a[i];int cnt = 0; sort( a.begin() + 1 , a.end() );for( int i = 1 ; i <= n ; i++ )if( a[i] <= 0 )cnt++; // 此时的 cnt 表示 a[i] <= 0 的个数int mn = 2e18;for( int i = 1 ; i < cnt ; i++ )mn = min( mn , a[i + 1] - a[i] );for( int i = cnt + 1 ; i <= n ; i++ ){// 考虑 a[i] > 0 的情况mn = min( mn , a[i] - a[i-1] );if( mn >= a[i] )cnt++;else break;}cout << cnt << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}

传送门：Problem - A - Codeforces

A. Bestie

题意：

 思路：

首先有一个结论 gcd( n , n - 1 ) == 1

所以这个题的答案一定 <= 3 

分情况讨论即可 答案为 1 2 3时的情况

#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd( int a , int b )
{return b ? gcd( b , a % b ) : a;
}
void solve()
{int n; cin >> n;vector<int> a( n + 1 );for( int i = 1 ; i <= n ; i++ ) cin >> a[i];int g = 0;for( int i = 1 ; i <= n ; i++ )g = gcd( g , a[i] );int temp1 = 0 ;for( int i = 1 ; i <= n; i++ )temp1 = gcd( temp1 , a[i] );int temp2 = 0;for( int i = 1 ; i <= n ; i++ ){if( i == n - 1 )continue;temp2 = gcd( temp2 , a[i] );}if( g == 1 ){cout << 0 << endl;}else if( gcd( temp1 , gcd( n , a[n] ) ) == 1 ){cout << 1 << endl;}else if( gcd( temp2 , gcd( n - 1 , a[n - 1] ) ) == 1 ){cout << 2 << endl;}else cout << 3 << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}