hdu 3461 Code Lock（并查集）2010 ACM-ICPC Multi-University Training Contest（3）
想不到这还可以用并查集解，不过后来证明确实可以……
题意也有些难理解——
给你一个锁，这个所由n个字母组成，然后这个锁有m个区间，每次可以对一个区间进行操作，并且区间中的所有字母要同时操作。每次操作可以将区间中所有字母+1。即把a变成b，把z变成a。
举个例子，比如有一个锁，由abcdef组成，前三个字母abc是一个区间，第四五个字母de是一个区间，那么如果对abc操作一次，则获得新锁bcddef，再对de区间操作一次，得bcdeff。但是，最后一个字母f是不能操作的。
如果一把锁通过对可操作区间的有限次操作可以得到另一个锁，那么我们说这两个锁是相同的，请求出在已给的长度和区间的情况下一共有多少种不同的锁。
输入：
第一行包括两个整数n, m。n表示这个锁的字符长度，m表示可操作区间个数。
接下来m行，每行包括两个整数a, b，表示一个从a到b的区间。
输出：
输出不同的锁的数量，结果Mod100000007。
经过分析发现——
1. 如果没有区间，那么有26^n种锁。
2. 如果有一个长度为1的区间（例如abcdef中的(1, 1)，即字符'a'），那么因为这个区间中无论第一个字符为什么，经过有限次变换都可以成为a，那么只要后5个字符和"abcdef"相同，则是同一把锁，所以有26^(n-1)种不同的锁。
3. 如果有一个长度为k(k <= n)的区间（例如abcdef中的(1, 3)，即"abc"），那么，只要前三个字符ASSIC码依次增1的字符串（如abc, bcd, xyz），只要其余字符与"abcdef"相同，则都可以通过有限次的变换得到"abcdef"。因此，有26^(n-1)种不同的锁。
4. 如果在"abcdef"中，同时存在三个区间(1, 3), (4, 5), (1, 5)，因为变换(1, 5)等价于同程度变换(1, 3), (4, 5)，所以可以忽略三者中的一个，认为存在两个区间。因此，存在26^(n-2)种不同的锁。
5. 在"abcdef"中，区间(1, 3), (3, 5), (1, 5)是不同的。因为旋转(1, 3)t次后，再旋转(3, 5)t次，会将第3个字符旋转2*t次，而其他字符旋转t次，不等价于旋转(1, 5)t次。所以共计存在3个区间。因此，存在26^(n-3)种不同的锁。
综上，忽略重复的区间，剩下的区间数为tmp，则存在26^(n-tmp)种不同的锁。
此时，就是最神奇的转换——我们可以使用并查集来去掉那些重复的区间。合并的状态是区间的左右坐标，我们将每个区间的左右坐标分别用l, r表示。因为结论（4）（5），可以将每个区间的坐标看做(l-1, r)。
以上是我看题解+自己理解得到的一些结论，那个转换成并查集实在是太精彩了。许多题目不仅需要缜密的分析，许多时候还需要思维的转换。当然了，见多才能识广，为什么可以举一反三？不仅因为才思敏捷，更因为在这之前已经见了三十，三百，乃至三千了。当然，足够的独立思考是很重要的，虽然每个人对于学与思的要求不一样，但我们要把握好最适合自己的度，取得近似最优解。
废话说完，上代码——
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #define LL long long //坑爹的东西 6 using namespace std; 7 8 const int N = 10000010; 9 const int M = 1000000007; 10 11 int fm[N]; 12 LL ans, n, m, tmp; 13 14 int mfind(int x) 15 { 16 int fx = x; 17 while(fx != fm[fx]) fx = fm[fx]; //查询 18 while(x != fm[x]) //路径压缩 19 { 20 int mid = fm[x]; 21 fm[x] = fx; 22 x = mid; 23 } 24 return fx; 25 } 26 27 void mmerge(int x, int y) 28 { 29 int fx = mfind(x); 30 int fy = mfind(y); 31 if(fx != fy) //合并（如果父节点相同，则是存在一个可以忽略的区间） 32 { 33 fm[fx] = fy; 34 tmp++; //不可忽略的可操作区间 35 } 36 } 37 38 LL qpow(LL x, LL y) //快速幂 39 { 40 if(y == 0) return 1; 41 LL rt = 1; 42 while(y > 1) 43 { 44 if(y%2) 45 { 46 rt *= x; 47 rt %= M; 48 } 49 y /= 2; 50 x *= x; 51 x %= M; 52 } 53 return (rt*x)%M; 54 } 55 56 int main() 57 { 58 //freopen("test.txt", "r", stdin); 59 while(~scanf("%lld%lld", &n, &m)) 60 { 61 tmp = 0; 62 for(int i = 0; i <= n; i++) fm[i] = i; 63 for(int i = 0; i < m; i++) 64 { 65 int a, b; 66 scanf("%d%d", &a, &b); 67 mmerge(a-1, b); 68 } 69 //printf("%d ", tmp); 70 printf("%lld\n", qpow(26, n-tmp)); 71 } 72 }View Code 优质内容筛选与推荐>>
1、横扫PHP职场的找工作面试秘籍
2、Java中java.util.concurrent包下的4中线程池代码示例
3、【监控笔记】【2.3】扩展事件——慢查询SQL（执行超过3S的SQL）
4、javadoc注释规范
5、使用async 和 await方法来