【题解】Points, Lines and Ready-made Titles Codeforces 871C 图论

Prelude

真是一道好题，然而比赛的时候花了太多时间在B题上，没时间想这个了QAQ。

题目链接：萌萌哒传送门（。＾▽＾）

Solution

观察样例和样例解释，我们发现，假如有四个点，恰好占据在某一个矩形的四个顶点上，那么这个矩形的四条边，都是可以自由选择画或者不画的。

这时候，我们称这四个点每个点“控制”了四条直线中的一条，可以自由选择这条直线画或者不画。这里可以配合样例解释理解一下。

考虑建立常用的图论模型——行列模型，把每一行抽象成一个点，每一列抽象成一个点，假如在\((x,y)\)处有一个点，那么用一条边连接第\(x\)行和第\(y\)列所代表的点。

在这个图上，每条边可以选择“控制”她所连接的两个点中的一个。

再次观察样例，发现如果四个点恰好占据在一个矩形的四个顶点上，那么这个连通块内会有一个环。

紧接着我们发现，如果在建出来的图上，某个连通块内有一个环的话，那么这个连通块内的每一个点，都可以被一条边“控制”，并且这些边不会重复。

也就是说，这个连通块内的每一个点所代表的直线，都是可以自由选择画或者不画的，因此，假设这个连通块内的点数为\(n\)，则这个连通块内的方案数为\(2^{n}\)。

假如某一个连通块内没有环，即形成了一棵树，那么容易发现，只有“所有直线都画”这一种情况没法办到，因此，方案数为\(2^{n}-1\)。

根据乘法原理，每个连通块之间互不干扰，所以把每个连通块的方案数乘起来就好了。

Code

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <map>

#include <cctype>

#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 200010;

const int MOD = 1e9+7;

int read() {

	int x = 0, ch;

	while( isspace(ch = getchar()) );

	do x = x * 10 + ch - '0';

	while( isdigit(ch = getchar()) );

	return x;

}

int n;

map<int,int> idx, idy;

int nid;

namespace G {

	int head[MAXN], nxt[MAXN], to[MAXN], m;

	void init() {

		memset(head, -1, sizeof head);

	}

	void adde( int u, int v ) {

		to[m] = v, nxt[m] = head[u], head[u] = m++;

		to[m] = u, nxt[m] = head[v], head[v] = m++;

	}

}

int fpow( int a, int b ) {

	int c = 1;

	while(b) {

		if( b & 1 ) c = int(1LL * c * a % MOD);

		a = int(1LL * a * a % MOD);

		b >>= 1;

	}

	return c;

}

int vis[MAXN];

queue<int> q;

int solve( int s ) {

	using namespace G;

	int e = 0, o = 0; // 边数和点数

	vis[s] = 1, q.push(s);

	while( !q.empty() ) {

		int u = q.front(); q.pop();

		++o;

		for( int i = head[u]; ~i; i = nxt[i], ++e )

			if( !vis[to[i]] )

				vis[to[i]] = 1, q.push(to[i]);

	}

	e >>= 1;

	return e == o-1 ? (fpow(2, o) - 1 + MOD) % MOD : fpow(2, o);

}

int main() {

	n = read();

	G::init();

	for( int i = 0; i < n; ++i ) {

		int x = read(), y = read();

		if( !idx[x] ) idx[x] = ++nid;

		if( !idy[y] ) idy[y] = ++nid;

		G::adde(idx[x], idy[y]);

	}

	int ans = 1;

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

		if( !vis[i] )

			ans = int(1LL * ans * solve(i) % MOD);

	printf( "%d\n", ans );

	return 0;

}

巴特西

【题解】Points, Lines and Ready-made Titles Codeforces 871C 图论

Prelude

Solution

Code

最新文章

热门文章