本人早期题解，题目不算太难。
题目链接
题意
现有 道题，每道题有一个主题
和一个难度 。现在要从其中选出三道题，使得他们满足以下条件的任意一条：
这三道题的主题互不相同；
这三道题的难度互不相同。
求出合法的方案数，题目保证不存在两道题，使得他们主题与难度都一样。
。
题解
由于上述两个条件之间是或的关系，也就是说一个合法的选择方案只需要满足任意一个条件就可以，这样很不好想，我们考虑算出不合法的方案总数，在用总方案数减去就可以了。
总数很好算：从
个数中选出三个数，共有
种方案，也就是
种。
根据题意，我们可以知道不满足的方案必然同时满足以下两个条件：
三道题中有至少两道题主体一致；
三道题中有至少两道题难度一致。
由于题目中已经告诉我们，不存在两道题主题与难度都相等，所以两个条件转化为：
三道题中有两道题主体一致；
三道题中有两道题难度一致。
虽然感觉没有什么变化，但是下面这两条显然更清晰。
现在，我们不妨将一道题看作二维平面上的一个点，其中第 道题的坐标为 。
再次转化不合法方案的条件：
三个点中有两个点横坐标一致；
三个点中有两个点纵坐标一致。
通俗一点说，这三个点在二维平面上组成了一个 L 形（当然，这个 L
形也有可能是旋转过的）。
那么，我们不妨枚举这个 L
形上拐弯处那个点，这样就可以求出不合法的方案数了。
最后减掉就可以了。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline int read()
{
int s=0,w=1;
char ch;
while((ch=getchar())>'9'||ch<'0')
if(ch=='-')
w=-1;
while(ch>='0'&&ch<='9')
{
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int numa[200001];
int numb[200001];
int a[200001];
int b[200001];
int n;
signed main()
{
int t=read();
while(t--)
{
long long ans=0;
n=read();
for(int i=1;i<=n;i++)
numa[i]=numb[i]=0;
ans=(long long)n*(n-1)*(n-2)/6;
for(int i=1;i<=n;i++)
{
a[i]=read(),numa[a[i]]++;
b[i]=read(),numb[b[i]]++;
}
for(int i=1;i<=n;i++)
ans-=(long long)(numa[a[i]]-1)*(numb[b[i]]-1);
printf("%lld\n",ans);
}
return 0;
}
|
早期题解，感谢观看！