C. Delete Two Elements

题意

删去两个数，使原数组平均值不变，问有多少种不同的删法

分析

先算出平均数，再哈希一下求组合数即可。

$ans+=\sum_{i=1}^{n}num[a[i]]num[2avr-a[i]],a[i]\neq avr \&\& a[i]<avr,$

$ans+=C_{num[avr]}^{2}$.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
  * @file    :deb.cpp
  * @brief   :
  * @date    :2021-10-12
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
int n;
const int maxn = 2e5 + 10;
map<double,int> mp;
signed main() {
    DDLC_ESCAPE_PLAN_FAILED;
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        int rhs;
        double sum = 0;
        fors (i, 1, n) { cin >> rhs; mp[rhs]++; sum += rhs;}
        sum /= n;
        int ans = 0;
        for(auto &x:mp){
            if(x.first > sum) break;
            if(x.first == sum) ans += (x.second * (x.second - 1)) / 2;
            else ans += x.second * (mp[2 * sum - x.first]);
        }
        cout << ans << endl;
        mp.clear();
    }
    return 0;
}

D. Training Session

分析

要求的事件为：3个标题都不同 或 3个标题难度都不同

考虑对立事件：3个有的标题相同 且 3个有的难度相同

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
  * @file    :deb.cpp
  * @brief   :
  * @date    :2021-10-12
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
int n;
int ab[maxn], ba[maxn];
int a[maxn], b[maxn];
signed main() {
    DDLC_ESCAPE_PLAN_FAILED;
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        fors(i , 1, n) cin >> a[i] >> b[i], ab[a[i]]++, ba[b[i]]++;
        int ans = n * (n - 1) * (n - 2) / 6;
        fors(i, 1, n) {
            int res = ab[a[i]] - 1;
            res *= ba[b[i]] - 1;
            ans -= res;
        }
        cout << ans << endl;
        fors(i, 1, n) ab[a[i]]--, ba[b[i]]--;
    }
    return 0;
}