[SCOI2016]萌萌哒

C++(g++ 7.5.0) 解法, 执行用时: 196ms, 内存消耗: 10232K, 提交时间: 2023-02-21 21:01:04

#include <bits/stdc++.h>
using namespace std;

//st表的并查集
int n, m;
int fa[100010][25];//i的第j级父节点
//数字首位不能为0 9*10^(s-1)
const int MOD = 1e9+7;

inline void init(int n){
    for(int k = 0; k <= 20; k++){
        for(int i = 0; i <= n; i++){
            fa[i][k] = i;
        }
    }
}

inline int find(int x, int k){
    //找爹(k级)
    if(fa[x][k] == x){
        return x;
    }
    return fa[x][k] = find(fa[x][k], k);

}

inline void Union(int x, int y, int k){
    int fx = find(x, k);
    int fy = find(y, k);
    if(fx != fy){
        fa[fx][k] = fy;
    }
}

int main(){

    scanf("%d%d", &n, &m);
    init(n);

    while(m--){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1 , &r1, &l2, &r2);
        for(int k = 20; k >= 0; k--){
            if(l1 + (1 << k) - 1 <= r1){
                //合并
                Union(l1, l2, k);
                l1 += (1 << k);
                l2 += (1 << k);
            }
        }
    }
    //离线更新，合并子区间
    for(int k = 20; k > 0; k--){
        for(int i = 1; i + (1 << k) - 1 <= n; i++){
            int pos = find(i, k);
            if(pos != i){
            Union(i, pos, k-1);
            Union(i + (1 << k-1), pos + (1 << k-1), k-1);}
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(fa[i][0] == i){
            ans = !ans ? 9 : 1LL*ans*10 %MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 232ms, 内存消耗: 10672K, 提交时间: 2020-01-23 19:22:34

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int MX=1e5+9;
const int mod=1e9+7;
int n,m,l1,r1,l2,r2;
int fa[20][MX];

int fin(int k,int x){
    if( fa[k][x]==x )
        return x;
    else
        return fa[k][x]=fin(k,fa[k][x]);
}

void chuli(int k,int a,int b){
    int A=fin(k,a),B=fin(k,b);
    if( A==B )
        return ;
    fa[k][A]=B;
    if( !k )
        return ;
    chuli(k-1,a,b);
    chuli(k-1,a+(1<<(k-1)),b+(1<<(k-1)));
}

int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d %d",&n,&m);
    if( n==1 ){
        printf("10\n");
        return 0;
    }
    for( int i=0 ; i<=19 ; i++ )
        for( int j=1 ; j<=n ; j++ )
            fa[i][j]=j;
    while( m-- ){
        scanf("%d %d %d %d",&l1,&r1,&l2,&r2);
        if( l1>l2 ){
            swap(l1,l2);
            swap(r1,r2);
        }
        int len=r1-l1+1;
        int k=log2(len);
        chuli(k,l1,l2);
        chuli(k,r1-(1<<k)+1,r2-(1<<k)+1);
    }
    int sum=0;
    for( int i=1 ; i<=n ; i++ )
        if( fin(0,i)==i )
            sum++;
    ll ans=9;
    for( int i=1 ; i<=sum-1 ; i++ ){
        ans*=10;
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 162ms, 内存消耗: 8700K, 提交时间: 2020-06-20 15:45:01

#include<bits/stdc++.h>
#define RG register
#define il inline
#define N 100010
#define MOD 1000000007
#define LL long long
using namespace std;
int f[21][N],n,m,cnt;LL Ans=9;
int find(int x,int y){if(f[y][x]!=x)f[y][x]=find(f[y][x],y);return f[y][x];}
void merge(int x,int y,int len){
  if(find(x,len)!=find(y,len))
    f[len][f[len][x]]=f[len][y];
}
int main(){
  scanf("%d%d",&n,&m);for(int j=0;j<=20;++j)for(int i=1;i<=n;++i)f[j][i]=i;
  for(int i=1;i<=m;++i){
    int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
    for(int j=20;j!=-1;j--)
      if(a+(1<<j)-1<=b)merge(a,c,j),a+=1<<j,c+=1<<j;
  }
  for(int j=20;j;j--)
    for(int i=1;i+(1<<j)-1<=n;++i)
      merge(i,find(i,j),j-1),
    merge(i+(1<<(j-1)),f[j][i]+(1<<(j-1)),j-1);
  for(int i=1;i<=n;++i)if(find(i,0)==i)cnt++;
  for(int i=1;i<cnt;++i)Ans*=10,Ans%=MOD;cout<<Ans;
  return 0;
}

详情