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

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

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

思路：

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

和bzoj 1854的并查集思路蜜汁契合 // 看完了题解的我这样想道
首先显然可以将图分为若干个联通块。
且慢，哪里来的图？那就先考虑建图？不急不急，先来想想看每一个联通块的性质。
如果该联通块中有环的话，肯定每条边都能取到；如果联通块是一棵树，那么必有一条边取不到（具体阐述见上bzoj 1854），所以只需要知道
这个联通块中有多少条边
这个联通块是不是环
这两个信息就可以了
那么可以直接上并查集。
什么样的点可以并到一起呢？横坐标相同的或者纵坐标相同的。
有没有环怎么维护呢？看有没有加进去的边的端点本身就在一个集合里。
联通块中边的数目又怎么知道呢？这倒还挺有意思的，其实只要直接看出现过多少个横坐标或者纵坐标就可以了，因为一个横坐标或者一个纵坐标就代表一条可以选的直线，所以这块联通块的贡献就是2^(x+y)或者2^(x+y)-1
然后呢？就做完了。
然而呢？比赛结束。一天了。

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2017年10月23日 星期一 15时51分51秒
  4File Name :E.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define PB push_back
 20#define fst first
 21#define sec second
 22#define lson l,m,rt<<1
 23#define rson m+1,r,rt<<1|1
 24#define ms(a,x) memset(a,x,sizeof(a))
 25typedef long long LL;
 26#define pi pair < int ,int >
 27#define MP make_pair
 28
 29using namespace std;
 30const double eps = 1E-8;
 31const int dx4[4]={1,0,0,-1};
 32const int dy4[4]={0,-1,1,0};
 33const int inf = 0x3f3f3f3f;
 34const int N=1E5+7;
 35const LL mod = 1E9+7;
 36struct point
 37{
 38    int x,y;
 39    int id;
 40    bool operator < ( point b)
 41    {
 42    return  id < b.id;
 43    }
 44}p[N];
 45
 46
 47vector < int>edge[N];
 48bool cmpx ( point a,point b) { return a.x < b.x;}
 49bool cmpy( point a,point b){ return a.y<b.y;}
 50
 51int n;
 52int cnt;
 53set<int>X,Y;
 54bool vis[N];
 55LL ksm ( LL a,LL b)
 56{
 57    LL res = 1;
 58    while (b)
 59    {
 60    if (b&1) res = res * a % mod;
 61    b = b >> 1LL;
 62    a = a * a % mod;
 63    }
 64    return res;
 65}
 66void dfs  ( int u)
 67{
 68    X.insert(p[u].x);
 69    Y.insert(p[u].y);
 70    vis[u] = true;
 71    cnt++;
 72    for ( auto v : edge[u])
 73    if (!vis[v]) dfs(v);
 74}
 75int main()
 76{
 77    #ifndef  ONLINE_JUDGE
 78    freopen("./in.txt","r",stdin);
 79  #endif
 80
 81    cin>>n;
 82    for ( int i = 1 ; i <= n ; i++) cin>>p[i].x >> p[i].y,p[i].id = i;
 83    sort(p+1,p+n+1,cmpx);
 84    for ( int i = 2 ; i <= n  ; i++)
 85        if (p[i].x==p[i-1].x)
 86        {
 87        edge[p[i].id].push_back(p[i-1].id);
 88        edge[p[i-1].id].push_back(p[i].id);
 89        }
 90
 91    sort(p+1,p+n+1,cmpy);
 92    for ( int i = 2 ; i <= n ; i++)
 93        if (p[i].y==p[i-1].y)
 94        {
 95        edge[p[i].id].PB(p[i-1].id);
 96        edge[p[i-1].id].PB(p[i].id);
 97        }
 98
 99    ms(vis,false);
100    sort(p+1,p+n+1);
101    LL ans = 1LL;
102    for ( int i = 1 ; i <= n ; i++)if (!vis[i])
103    {
104        X.clear();
105        Y.clear();
106        cnt = 0;
107        dfs(i);
108        int sum = X.size() + Y.size();
109        //cout<<"sum:"<<sum<<endl;
110        if (sum<=cnt) ans = ans * ksm(2,sum) % mod;
111        else ans = ans * (ksm(2,sum)-1 + mod) % mod;
112    }
113    cout<<ans<<endl;
114
115
116  #ifndef ONLINE_JUDGE
117  fclose(stdin);
118  #endif
119    return 0;
120}

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

相关文章