codeforces # 440 div2 E. Points, Lines and Ready-made Titles (和图有关的计数，思维题)

2017-10-24 · 2 min read · 思维题 计数问题

题目链接

题意：有n个整点，每个点处可以什么都不画，或者画一条垂直方向的直线，或者画一条水平方向的直线。

现在给出n个点的坐标，问最多右多少种不同的图案。(只要有一处不同，就认为两个不同）

思路：

参考题解

好菜啊不会做，转载一段题解。

和[bzoj 1854](http://www.cnblogs.com/kkkkahlua/p/7666811.html)的并查集思路蜜汁契合 // 看完了题解的我这样想道

首先显然可以将图分为若干个联通块。

且慢，哪里来的图？ 那就先考虑建图？ 不急不急，先来想想看每一个联通块的性质。

如果该联通块中有环的话，肯定每条边都能取到；如果联通块是一棵树，那么必有一条边取不到（具体阐述见上bzoj 1854），所以只需要知道

  1. 这个联通块中有多少条边
  2. 这个联通块是不是环

这两个信息就可以了

那么可以直接上并查集。

什么样的点可以并到一起呢？横坐标相同的或者纵坐标相同的。

有没有环怎么维护呢？看有没有加进去的边的端点本身就在一个集合里。

联通块中边的数目又怎么知道呢？这倒还挺有意思的，其实只要直接看出现过多少个横坐标或者纵坐标就可以了，因为一个横坐标或者一个纵坐标就代表一条可以选的直线，所以这块联通块的贡献就是2^(x+y)或者2^(x+y)-1

然后呢？就做完了。

然而呢？比赛结束。一天了。

/* ***********************************************
Author :111qqz
Created Time :2017年10月23日 星期一 15时51分51秒
File Name :E.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E5+7;
 7const LL mod = 1E9+7;
 8struct point 
 9{
10    int x,y;
11    int id;
12    bool operator < ( point b)
13    {
14    return  id < b.id;
15    }
16}p[N];

1vector < int>edge[N];
2bool cmpx ( point a,point b) { return a.x < b.x;}
3bool cmpy( point a,point b){ return a.y<b.y;}

 1int n;
 2int cnt;
 3set<int>X,Y;
 4bool vis[N];
 5LL ksm ( LL a,LL b)
 6{
 7    LL res = 1;
 8    while (b)
 9    {
10    if (b&1) res = res * a % mod;
11    b = b >> 1LL;
12    a = a * a % mod;
13    }
14    return res;
15}
16void dfs  ( int u)
17{
18    X.insert(p[u].x);
19    Y.insert(p[u].y);
20    vis[u] = true;
21    cnt++;
22    for ( auto v : edge[u])
23    if (!vis[v]) dfs(v);
24}
25int main()
26{
27    #ifndef  ONLINE_JUDGE 
28    freopen("./in.txt","r",stdin);
29  #endif

1    cin>>n;
2    for ( int i = 1 ; i <= n ; i++) cin>>p[i].x >> p[i].y,p[i].id = i;
3    sort(p+1,p+n+1,cmpx);
4    for ( int i = 2 ; i <= n  ; i++) 
5        if (p[i].x==p[i-1].x)
6        {
7        edge[p[i].id].push_back(p[i-1].id);
8        edge[p[i-1].id].push_back(p[i].id);
9        }

1    sort(p+1,p+n+1,cmpy);
2    for ( int i = 2 ; i <= n ; i++)
3        if (p[i].y==p[i-1].y)
4        {
5        edge[p[i].id].PB(p[i-1].id);
6        edge[p[i-1].id].PB(p[i].id);
7        }

 1    ms(vis,false);
 2    sort(p+1,p+n+1);
 3    LL ans = 1LL;
 4    for ( int i = 1 ; i <= n ; i++)if (!vis[i])
 5    {
 6        X.clear();
 7        Y.clear();
 8        cnt = 0;
 9        dfs(i);
10        int sum = X.size() + Y.size();
11        //cout<<"sum:"<<sum<<endl;
12        if (sum<=cnt) ans = ans * ksm(2,sum) % mod;
13        else ans = ans * (ksm(2,sum)-1 + mod) % mod;
14    }
15    cout<<ans<<endl;

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}

相关并且有趣的题目:bzoj1854 codeforces #346 div2