HDU 3461 Code Lock(并查集+二分求幂)

本文主要是介绍HDU 3461 Code Lock(并查集+二分求幂)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3461

原题：

  
1 1
1 1
2 1
1 2

  
1
26

分析与总结：

伤不起啊， 理解这题的题意废了我N多脑细胞 。。。

题意是说有N个字母组成的密码锁， 如【wersdfj】,   每一位上的字母可以转动， w可转动变成x， z变成a。但是题目规定， 只能同时转动某个区间上的所有字母， 如【1，3】， 那么第1到第3个的所有字母要同时转动，那么【 wersdfj 】经过一次操作就变成 【 xfssdfj 】.    一共有M 个区间是可以操作的。  

题目还规定：If a lock can change to another after a sequence of operations, we regard them as same lock. 

就是说， 经过可操作区间进行的操作得到的所有锁情况，都是同一个的。 也就是说，所有不同的锁就是“不可操作区间”的所有组合情况。

在最初时，每个字母看作是一个独立的区间， 那么就有N个区间， 可以很容易地用初始化的并查集来表示。然后一个区间可以看作是一个“元素”，  我们只需要求出共有多少个可操作区间x， 然后就可以计算得到N-x个不可操作的区间。 不可操作区间的所有组合，就是能组成的所有不同的锁。

每个区间可以有26种情况， 那么就共有26^(N-x)种情况。由于N可能会很大，所以直接计算浪费时间了，用二分求幂法来计算出结果。

这题最关键的一步是求出有多少个可操作区间。 用并查集来做时要注意，不能直接合并Union(L, R),   

假设有区间【1，3】， 【3，5】，【1，5】，  如果按照Union(L, R)来算， 那么得到两种可操作区间。但实际上是有3中可操作区间的，因为1～3， 3～5是有重叠了3的两个区间，所以1～5区间的情况不包括在前两个区间的情况内（可自己在纸上画画）。

如果是【1，3】， 【4，5】，【1，5】,  那么就是只有两种情况，因为最后一种的转动情况包含在了前两种转动的情况之内了。

只需稍微处理下，Union(L-1, R)或者Union(L, R+1)都可以。

代码：

#include<cstdio>
#define N 10000005
#define MOD 1000000007
int f[N],n,m;
void init(){for(int i=0; i<=n; ++i)f[i]=i;
}
int find(int x){int i, j=x;while(j!=f[j])j=f[j];while(x!=j){i=f[x]; f[x]=j; x=i;}return j;
}
bool Union(int x,int y){int a=find(x),b=find(y);if(a==b)return false;f[a] = b;return true;
}
long long myPower(int n){long long sum=1, tmp=26;while(n){if(n&1){sum = sum*tmp;sum %= MOD;}tmp = (tmp*tmp)%MOD;n>>=1;}return sum;
}
int main(){int l,r;while(~scanf("%d%d",&n,&m)){int cnt=0;init();for(int i=0; i<m; ++i){scanf("%d%d",&l,&r);--l;if(Union(l,r)) ++cnt;}printf("%lld\n", myPower(n-cnt)%MOD);}return 0;
}

——  生命的意义，在于赋予它意义。
          
     原创 http://blog.csdn.net/shuangde800 ， By   D_Double  (转载请标明)

这篇关于HDU 3461 Code Lock(并查集+二分求幂)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！