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