2 条题解

  • 0
    @ 2026-11-9 20:48:17

    暴力过不了是因为大量重复计算,连足够多边之后两个大区间相同的条件并不能给区间中间的元素带来新的限制,连接两个边缘即可

    #include<bits/stdc++.h>
    #define mod 1000000007
    using namespace std;
    int n,m,k,jc,l1,r1,l2,r2;
    long long ans=1;
    vector<int> to[100007];
    bitset<100032> vis;
    void dfs(int i){
        vis[i]=true;
        for(int j : to[i]){
            if(!vis[j]){
                dfs(j);
            }
        }
    }
    signed main(){
    	ios::sync_with_stdio(0);
        cin.tie(0);
        cin>>n>>k;
        for(int i=1;i<=k;++i){
            cin>>l1>>r1>>l2>>r2;
            if(l1==l2){
                continue;
            }
            if(l1==1||l2==1){
                jc=1;
            }
            if(m>7251031){
                for(int j=l1;j<=min(r1,l1+15);++j){
                    to[j].emplace_back(j+l2-l1);
                    to[j+l2-l1].emplace_back(j);
                    ++m;
                }
                for(int j=max(l1+16,r1-15);j<=r1;++j){
                    to[j].emplace_back(j+l2-l1);
                    to[j+l2-l1].emplace_back(j);
                    ++m;
                }
                continue;
            }
            for(int j=l1;j<=r1;++j){
                to[j].emplace_back(j+l2-l1);
                to[j+l2-l1].emplace_back(j);
                ++m;
            }
        }
        for(int i=1;i<=n;++i){
            if(!vis[i]){
                dfs(i);
                ans*=(i==1 ? 9 : 10);
                ans%=mod;
            }
        }
        cout<<ans;
        return 0;
    }
    
    • 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;
      } 
      
      • 1

      信息

      ID
      897
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      (无)
      递交数
      24
      已通过
      6
      上传者