设为首页 加入收藏

TOP

[SCOI2016] 萌萌哒
2019-06-10 14:08:50 】 浏览:8
Tags:SCOI2016

用并查集合并相同的点,答案为9*10^{并查集的块数-1}。

由“区间对区间的”可以联想到线段树优化之类的方法,换成倍增会更简单~

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

const int N=1e5+10;
const int mod=1e9+7;

int n,m,L[N],f[20][N];
int find(int i,int x) {return f[i][x]==x?x:f[i][x]=find(i,f[i][x]);}
void merge(int i,int x,int y) {f[i][find(i,x)]=find(i,y);}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=2; i<=n; ++i) L[i]=L[i>>1]+1;
    for(int i=0; i<=L[n]; ++i) for(int j=1; j<=n; ++j) f[i][j]=j;
    for(int l1,r1,l2,r2; m--; ) {
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        int d=L[r1-l1+1];
        merge(d,l1,l2);
        merge(d,r1-(1<<d)+1,r2-(1<<d)+1);
    }
    for(int i=L[n]; i; --i)
    for(int j=1; j+(1<<i)-1<=n; ++j) {
        int k=find(i,j);
        if(k==j) continue;
        merge(i-1,j,k);
        merge(i-1,j+(1<<(i-1)),k+(1<<(i-1)));
    }
    ll ans=9,tot=0;
    for(int i=1; i<=n; ++i) if(find(0,i)==i) tot++;
    for(int i=1; i<tot; ++i) ans=ans*10%mod;
    printf("%lld\n",ans);
    return 0;
}



编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇[CTSC2008] 网络管理 下一篇[ZJOI2015] 幻想乡战略游戏

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }