给平面上n个点，在每个点可以，画一条竖直线，画一条横直线，什么都不画，也就是不能画十字
这样n个点一共能画出多少种图形
数据范围
n<=100 000,点的坐标范围-1 000 000 000<=x,y<=1 000 000 000，
时间空间(2s/256MB)
输出答案MOD 1 000 000 007
题解
想了半天还想了递推，但是到横竖交叉我的递推就变得格外的复杂以至不可用。
我已经想到 如果有一群点可以通过横线和竖线连在一起，那么，我们只用考虑画出来的横线竖线的可能性
题解的意思是需要发现两个事实：
如果 这一群点能够成环，那么方案数=2^(横线数+竖线数)
如果 这一群点不能够成环，那么方案数=2^(横线数+竖线数) - 1
过程就是并查集之类的+找环就好了
所以我菜 就菜在 根本没有发现这两个 事实
代码/280ms/14368KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| typedef long long ll;
#define shi5 100000+10
#define MOD 1000000007
#include <bits/stdc++.h>
using namespace std;
struct poi{
ll x;
ll y;
int color;
};
int intcmp(const void *v1,const void *v2){return *(int *)v1-*(int *)v2;}
long long minn(long long v1,long long v2){return v1<v2?v1:v2;}
long long maxx(long long v1,long long v2){return v1>v2?v1:v2;}
poi p[100010]={0};
map<ll,vector<int> > x2index;
map<ll,vector<int> > y2index;
ll twopow(ll val){
if(val == 1)
return 2;
ll ret = twopow(val/2);
ret *= ret;
ret %= MOD;
if(val%2)
ret *= 2;
ret %= MOD;
return ret;
}
ll getnocircle(int v){
ll ret = twopow(v);
if(ret == 0)
return MOD-1;
else
return ret-1;
}
ll getcircle(int v){
return twopow(v);
}
ll dolink(int index,int c){
map<ll,ll> xlstartindex;
map<ll,ll> ylstartindex;
vector<ll> xlist;
vector<ll> ylist;
int xitr=0,yitr=0;
bool iscircle=false;
p[index].color=c;
xlist.push_back(p[index].x);
ylist.push_back(p[index].y);
xlstartindex[p[index].x] = index;
ylstartindex[p[index].y] = index;
while(xitr != xlist.size() or yitr != ylist.size()){
if(xitr != xlist.size()){
for(auto indexeach:x2index[xlist[xitr]]){
if(indexeach == xlstartindex[xlist[xitr]])
continue;
if(p[indexeach].color != 0)
iscircle = true;
else if(ylstartindex.count(p[indexeach].y)){
p[indexeach].color = c;
iscircle = true;
}else{
p[indexeach].color = c;
ylist.push_back(p[indexeach].y);
ylstartindex[p[indexeach].y] = indexeach;
}
}
xitr++;
}
if(yitr != ylist.size()){
for(auto indexeach:y2index[ylist[yitr]]){
if(indexeach == ylstartindex[ylist[yitr]])
continue;
if(p[indexeach].color != 0)
iscircle = true;
else if(xlstartindex.count(p[indexeach].x)){
p[indexeach].color = c;
iscircle = true;
}else{
p[indexeach].color = c;
xlist.push_back(p[indexeach].x);
xlstartindex[p[indexeach].x] = indexeach;
}
}
yitr++;
}
}
if(iscircle)
return getcircle(xlist.size()+ylist.size());
else
return getnocircle(xlist.size()+ylist.size());
}
int main(){
int n;
cin>>n;
int i;
for(i=0;i<n;i++){
scanf("%lld %lld",&p[i].x,&p[i].y);
x2index[p[i].x].push_back(i);
y2index[p[i].y].push_back(i);
}
int nowcolor=1;
ll ans = 1;
for(i=0;i<n;i++){
if(p[i].color == 0){
ans *= dolink(i,nowcolor);
ans %= MOD;
}
nowcolor++;
}
cout<<ans<<endl;
return 0;
}
|
依旧代码丑陋126行
大佬们都写得十分精简 低头
oscillation
wdmmsyf
参考
题目
官方题解