P8398 题解
船酱魔王
·
·
题解
P8398 [CCC2022 S4] Good Triplets 题解
题意回顾
在一个圆上，逆时针等距分布着 c 个点，我们放置一些关键点，当一个以关键点为三个顶点的非退化三角形且内部包含原点时称其为好三角形，统计所有好三角形的个数。
## 分析
正难则反。
我们尝试统计内部不包含原点的三角形，再用任选出三个点的总数减去。
我们发现当一个三角形在圆的半径的一边时，一定为不合法，否则为合法。
我们假设一条直线为圆的半径，每次统计出以 $ i $ 为顶点之一且剩下的顶点都在以直线为分割，与 $ i $ 同侧的半圆中的三角形个数，要维护当前半圆内的点数总和，再将直线旋转一格。
注意 $ c $ 奇偶的分类讨论，以及 ```long long``` 的使用。
## AC 代码
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
int n, c;
int a[N];
int cnt[N];
int sum[N];
long long c2(int x) {
if(x <= 1) {
return 0;
}
return (long long)x * (x - 1) / 2;
}
long long c3(int x) {
if(x <= 2) {
return 0;
}
return (long long)x * (x - 1) * (x - 2) / 6;
}
int main() {
scanf("%d%d", &n, &c);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++;
}
int li = c / 2;
long long ans = 0;
int now = 0;
for(int i = 1; i <= li; i++) {
now += cnt[i];
}
if(c % 2 == 0) {
for(int i = 0; i < c; i++) {
ans += (long long)cnt[i] * c2(now);
ans += (long long)c2(cnt[i]) * (now - cnt[(i + li) % c]);
now -= cnt[(i + 1) % c];
now += cnt[(i + li + 1) % c];
}
} else {
for(int i = 0 ; i < c; i++) {
ans += (long long)cnt[i] * c2(now);
ans += (long long)c2(cnt[i]) * now;
now -= cnt[(i + 1) % c];
now += cnt[(i + li + 1) % c];
}
}
for(int i = 0; i < c; i++) {
ans += c3(cnt[i]);
}
long long sum = c3(n);
printf("%lld\n", sum - ans);
return 0;
}
```