hdu Code Lock

题意是说有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.

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

这题其实就是并查集+二分求幂。首先要求出可以活动的区间数x，一个区间等价于某一位的密码种类为1，那么得到的密码锁的种类为26^(n-x)，因为n的数据较大，所以要用到二分求幂的方法。

先来分析一下二分求幂：

递归算法：

double powerWithUnsignedExponent(double base,unsigned int exponent)  
{  
    if(exponent==0)  
        return 1;  
    if(exponent==1)  
        return base;  
    double result=powerWithUnsignedExponent(base,exponent>>1);//exponent>>1即exponent/2   
    result*=result;  
    if(exponent & 0x1==1)//a & 0x1相当于a%2   
        result*=base;  
    return result;  
}

View Code

非递归算法：

int power(int a,int b)  
{  
    int ans=1;  
    while(b!=0)  
    {  
        if(b%2==1)  
            ans*=a;  
        b/=2;  
        a*=a;  
    }  
    return ans;  
}

View Code

再来分析一下这道题的区间判定问题，这题给出的区间可能会存在重叠的情况。例如[1,4]、[4,6]和[1,6],这个应该算3个区间，因为第三个区间不能由前两个区间组合得到。二

[1,4]、[5,6]和[1,6]却只能算两个区间，因为最后一个区间的所有情况可以由前两个区间得到。

所以这题的思路就是：

1、求出所有的区间个数，注意区间重复和重叠的情况，这里用了一个很巧妙的方法，可以把原来的区间左边界减一，这样就可以很简单的避免上面的问题了。

2、用二分幂的方法求出最终的结果。

这里注意int还是不够用的，要用64位整型：

#include"iostream"
#include"stdio.h"
#include"algorithm"
#include"string"
#include"string.h"
#include"cmath"
#include"queue"
#include"stack"
#include"vector"
using namespace std;
const int mx=10000001;
const int inf=1000000007;
int fa[mx];
int cnt;
int n,m;

void Set()
{
   int i;
   for(i=0;i<=n;++i)
        fa[i]=i;
}

int Find(int x)
{
    int t1,t2=x;
    while(t2!=fa[t2]) t2=fa[t2];
    while(x!=t2)
    {
        t1=fa[x];
        fa[x]=t2;
        x=t1;
    }
    return t2;
}

bool Union(int x,int y)
{
    int fx=Find(x);
    int fy=Find(y);
    if(fx==fy)
        return false;
    else
    {
        fa[fx]=fy;
        return true;
    }
}
long long binary_power(int N)
{
    long long base=26,res=1;
    while(N)
    {
        if(N&1)
        {
            res=(res*base)%inf;
        }
        N/=2;
        base=(base*base)%inf;
    }
    return res;
}
void IO()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        int i,l,r;
        cnt=0;
        Set();
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&l,&r);
            l--;
            if(Union(l,r)) cnt++;
        }
        printf("%lld
",binary_power(n-cnt)%inf);
    }
}
int main()
{
//    freopen("E:\in.txt","r",stdin);
    IO();
    return 0;
}

View Code