问一下(玄关&为桂子山)
  • 板块学术版
  • 楼主xrh1145
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/27 14:17
  • 上次更新2024/8/27 14:39:45
查看原帖
问一下(玄关&为桂子山)
1353313
xrh1145楼主2024/8/27 14:17

题目大概是这个样子的:

给定 nn 和长度为 nn 的序列 xx 和 yy,需要求出满足条件的 i,j,k(1≤i,j,k≤n)(i≠j≠k)i,j,k(1\le i,j,k\le n)(i\not=j\not=k) 的个数满足 i,j,ki,j,k 的 xx 和 yy 至少有一个不同。

现在有了一个容斥思路,但是没有具体的容斥方案。求助。

为了更好的理解题意,放上暴力代码:

#include<bits/stdc++.h>
#define MAXN 200002
using namespace std;
int x[MAXN],y[MAXN];
inline bool unsame(int i,int j,int k){
	return x[i]!=x[j]&&x[j]!=x[k]&&x[k]!=x[i]||y[i]!=y[j]&&y[j]!=y[k]&&y[k]!=y[i];
}
int main(){
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		int n,ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d %d",&x[i],&y[i]);
		}
		for(int i=1;i<=n;++i){
			for(int j=i+1;j<=n;++j){
				for(int k=j+1;k<=n;++k){
					if(unsame(i,j,k)){
						++ans;
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
2024/8/27 14:17
加载中...