2 条题解
-
0
比较牛的题
我们观察到,题目相当于给定一些边,求连通块的个数。
记连通块的个数为 ,则答案为 。
遍历一遍整个图的复杂度一定是 ,所以直接做肯定不行。
这个题的建边方式也不适合用线段树优化。
我们发现,题目给出的限制,是区间之间的连边。于是我们把限制划分成若干个区间,将这些区间相连,并用并查集维护连通块。
表示区间 在并查集上的父亲是 。
然后把区间分成 段后合并。
其实这里也可以用st表的方法,分成 个区间,因为这个限制可以合并。
最后我们把大区间的限制转移到小区间,具体地,记 :
- 合并 与 。
- 合并 与 。
#include<bits/stdc++.h> using namespace std; #define int long long #define lb(x) x&(-x) #define ls(p) (p<<1) #define rs(p) ((p<<1)|1) #define pii pair<int,int> #define F first #define S second #define mkp make_pair #define psb push_back #define vi vector<int> const int mod=1e9+7; const int N=1e5+1000,V=1e8,inf=1e15; int n,m; int fa[N][22]; int fnd(int x,int k){ if(fa[x][k]==x) return x; return fa[x][k]=fnd(fa[x][k],k); } void merge(int x,int y,int d){ fa[fnd(x,d)][d]=fnd(y,d); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=0;j<=20;j++) fa[i][j]=i; } while(m--){ int A,B,C,D; cin>>A>>B>>C>>D; int X=A,Y=C; for(int i=20;i>=0;i--){ if(X+(1<<i)-1<=B){ merge(X,Y,i); X=X+(1<<i);Y=Y+(1<<i); } } } for(int j=20;j>=1;j--){ for(int i=1;i+(1<<j)-1<=n;i++){ int L=i,R=i+(1<<j)-1,DT=(1<<(j-1)); merge(L,fnd(L,j),j-1); merge(L+DT,fnd(L,j)+DT,j-1); } } int cnt=0,ans=9; for(int i=1;i<=n;i++){ if(fnd(i,0)==i) cnt++; } for(int i=2;i<=cnt;i++) ans=ans*10%mod; cout<<ans; return 0; }
信息
- ID
- 897
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 24
- 已通过
- 6
- 上传者