「LOJ 6065」「2017 山东一轮集训 Day3」第一题
LOJ 6065
题解
总的分为两种情况：\(1+1+2+2\) 和 \(1+1+1+3\)。
对于第一种情况，我们假设边长为 \(k\)，\(6\) 根棒子长度为 \(k,k,x_1,k-x_1,x_2,k-x_2\)，并且强制 \(x_1\ge x_2\ge k-x_2\ge k-x_1\)。
我们记 \(cnt_i\) 表示长度为 \(i\) 的棒子的数量，我们从小到大枚举 \(x_1\)，同时维护 \(cntt_i\) 表示在长度小于 \(x_1\) 的棒子中选出两根拼成长度为 \(i\) 的方案数。
具体计算的时候，为了避免算重，我们分三种情况进行计算：
- \(x_1 > x_2 > k-x_2 > k-x_1\)，枚举 \(k\)，方案数为 \(cnt_{x_1}\times cnt_{k-x_1}\times cntt_{k}\times C_{cnt_k}^2\)；
- \(x_1 = x_2 > k-x_2 = k-x_1\)，同样枚举 \(k\)，方案数为 \(C_{cnt_{x_1}}^2\times C_{cnt_{k-x_1}}^2\times C_{cnt_k}^2\)；
- \(x_1 = x_2 = k-x_2 = k-x_1\)，此时 \(k=2x_1\)，方案数为 \(C_{cnt_{x_1}}^4\times C_{cnt_{2x_1}}^2\)。
对于第二种情况，假设棒子长度为 \(k,k,k,x_1,x_2,k-x_1-x_2\)，强制 \(x_1\ge x_2\ge k-x_1-x_2\)。
同样记录 \(cnt_i\)，然后从小到大枚举 \(x_1\)，同时记录 \(cntt_i\)。
也分为三种情况：
- \(x_1 > x_2 > k-x_1-x_2\)，枚举 \(k\)，方案数为 \(cnt_{x_1}\times cntt_{k-x_1}\times C_{cnt_k}^3\)；
- \(x_1 = x_2 > k-x_1-x_2\)，枚举 \(k\)，方案数为 \(C_{cnt_{x_1}}^2\times cnt_{k-2x_1}\times C_{cnt_k}^3\)；
- \(x_1 = x_2 = k-x_1-x_2\)，此时 \(k=3x_1\)，方案数为 \(C_{cnt_{x_1}}^3\times C_{cnt_{3x_1}}^3\)。
时间复杂度 \(O(n^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
| #include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
int read(){
register int x = 0;
register char ch = getchar(), f = 1;
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = !f;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return f ? x : -x;
}
#define N 5005
#define M 10000005
int n, m, a[N], cnt[M], cntt[M];
long long ans;
long long C2(long long x){ return x < 2 ? 0 : x * (x - 1) / 2; }
long long C3(long long x){ return x < 3 ? 0 : x * (x - 1) * (x - 2) / 6; }
long long C4(long long x){ return x < 4 ? 0 : x * (x - 1) * (x - 2) * (x - 3) / 24; }
int main(){
n = read();
for (register int i = 1; i <= n; ++i) a[i] = read(), ++cnt[a[i]];
std :: sort(a + 1, a + 1 + n);
m = a[n];
n = std :: unique(a + 1, a + 1 + n) - a - 1;
for (register int i = 1; i <= n; ++i){
for (register int j = i + 1; j <= n && a[j] - a[i] < a[i]; ++j)
ans += 1ll * cntt[a[j]] * cnt[a[i]] * cnt[a[j] - a[i]] * C2(cnt[a[j]]),
ans += 1ll * C2(cnt[a[i]]) * C2(cnt[a[j] - a[i]]) * C2(cnt[a[j]]);
if (a[i] * 2 <= m) ans += 1ll * C4(cnt[a[i]]) * C2(cnt[a[i] * 2]);
for (register int j = i + 1; j <= n; ++j){
ans += 1ll * C3(cnt[a[j]]) * cnt[a[i]] * cntt[a[j] - a[i]];
if ((a[i] << 1) < a[j] && a[j] < a[i] * 3)
ans += 1ll * C3(cnt[a[j]]) * C2(cnt[a[i]]) * cnt[a[j] - (a[i] << 1)];
if (a[j] == a[i] * 3) ans += 1ll * C3(cnt[a[j]]) * C3(cnt[a[i]]);
}
for (register int j = 1; j < i; ++j)
if (a[i] + a[j] <= m) cntt[a[i] + a[j]] += cnt[a[i]] * cnt[a[j]];
if ((a[i] << 1) <= m) cntt[a[i] << 1] += C2(cnt[a[i]]);
}
printf("%lld\n", ans);
}
|
