题解 P6355 [COCI2007-2008#3] DEJAVU

kcm的原题。。

貌似是个组合数（？

\(\sf {Solution}\)

对于每一个点，我们需要统计与它同一行的点数\(a\) 和同一列的点数\(b\) ，则该点对结果\(ans\) 的贡献为\((a-1)\times (b-1)\) 。

当然如果统计两重循环的话，那肯定是会TLE的啦。那么就要加一个预处理了：

用两个map 数组分别统计\(a\) 和\(b\) 。
\(m1_i\) 就代表在第\(i\) 行的点数，\(m2_j\) 就代表在第\(j\) 列的点数。

（之所以考虑用map是因为开数组可能会炸，后来发现好像不会……）

\(\sf {P.S}\)

因为有乘运算，并且\(n\leq 10^5\) ，所以不开long long是要炸掉的哦。

\(\sf {Code}\)

#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

struct node

{

	int x,y;

}a[100004];

int n;

long long ans;

map<long long,long long>m1,m2;//long long!

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

		scanf("%d%d",&a[i].x,&a[i].y);//读入

	for(int i=1;i<=n;++i)

		++m1[a[i].x],++m2[a[i].y];//分别统计行和列

	for(int i=1;i<=n;++i)

		ans+=(m1[a[i].x]-1)*(m2[a[i].y]-1);//根据那啥算

	printf("%lld",ans);

	return 0;

}

巴特西

题解 P6355 [COCI2007-2008#3] DEJAVU

\(\sf {Solution}\)

\(\sf {P.S}\)

\(\sf {Code}\)

最新文章

热门文章