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