2 条题解

  • 0
    @ 2026-10-12 16:09:02

    比较牛的题

    我们观察到,题目相当于给定一些边,求连通块的个数。

    记连通块的个数为 cntcnt ,则答案为 9×10cnt−19\times10^{cnt-1} 。

    遍历一遍整个图的复杂度一定是 O(nm)O(nm) ,所以直接做肯定不行。

    这个题的建边方式也不适合用线段树优化。

    我们发现,题目给出的限制,是区间之间的连边。于是我们把限制划分成若干个区间,将这些区间相连,并用并查集维护连通块。

    fai,kfa_{i,k} 表示区间 [i,i+2k−1][i,i+2^{k}-1] 在并查集上的父亲是 [fai,k,fai,k+2k−1][fa_{i,k},fa_{i,k}+2^{k}-1]。

    然后把区间分成 O(logn)O(logn) 段后合并。

    其实这里也可以用st表的方法,分成 O(1)O(1) 个区间,因为这个限制可以合并。

    最后我们把大区间的限制转移到小区间,具体地,记 x=find(i,k)x=find(i,k):

    • 合并 [i,i+2k−1−1][i,i+2^{k-1}-1] 与 [x,x+2k−1−1][x,x+2^{k-1}-1]。
    • 合并 [i+2k−1,i+2k−1][i+2^{k-1},i+2^{k}-1] 与 [x+2k−1,x+2k−1][x+2^{k-1},x+2^{k}-1]。
    #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
    上传者