首页 > ACM题库 > HDU-杭电 > HDU 3461-Code Lock-并查集-[解题报告]HOJ
2014
03-30

HDU 3461-Code Lock-并查集-[解题报告]HOJ

Code Lock

问题描述 :

A lock you use has a code system to be opened instead of a key. The lock contains a sequence of wheels. Each wheel has the 26 letters of the English alphabet ‘a’ through ‘z’, in order. If you move a wheel up, the letter it shows changes to the next letter in the English alphabet (if it was showing the last letter ‘z’, then it changes to ‘a’).
At each operation, you are only allowed to move some specific subsequence of contiguous wheels up. This has the same effect of moving each of the wheels up within the subsequence.
If a lock can change to another after a sequence of operations, we regard them as same lock. Find out how many different locks exist?

输入:

There are several test cases in the input.

Each test case begin with two integers N (1<=N<=10000000) and M (0<=M<=1000) indicating the length of the code system and the number of legal operations.
Then M lines follows. Each line contains two integer L and R (1<=L<=R<=N), means an interval [L, R], each time you can choose one interval, move all of the wheels in this interval up.

The input terminates by end of file marker.

输出:

There are several test cases in the input.

Each test case begin with two integers N (1<=N<=10000000) and M (0<=M<=1000) indicating the length of the code system and the number of legal operations.
Then M lines follows. Each line contains two integer L and R (1<=L<=R<=N), means an interval [L, R], each time you can choose one interval, move all of the wheels in this interval up.

The input terminates by end of file marker.

样例输入:

1 1
1 1
2 1
1 2

样例输出:

1
26

并查集题目,表示被题意折磨的好惨,百度了好几篇文章才看懂题目。

区间合并问题,初始化每个节点为一个区间,这样得到的所有解为26^n,之后每输入一个区间,如果该区间没出现过且没被之前的区间等效过,则可操作区间数目-1,具体原因可以自己推理下,原文中说的每一次动区间所有字母一起动,相当于该区间的组合数减少了26种,所以只要统计出这种区间出现了多少即可用二分快速幂求出结果。

区间合并的动机有点难想,不太明显,对于两段相邻但是不交叉的区间,可以将两个区间的并给等效掉,即出现了第三个区间是两个区间的并时,不予计数,因为之前的两个区间的操作可以达到相同的效果,对于有交叉或者不相邻的区间则没有这种属性,所以这时候区间的合并就有意义了,可以计算出总的区间的个数。

然后二分快速幂即可。

#include <iostream>
#include <cstring> 

using namespace std;

int father[10000001];
long long int ans;
int n,m;
const int mod=1000000007;
long long s;

int find(int x)
{
    while (x!=father[x])
        x=father[x];
    return x;
}

void Union(int a,int b)
{
    a=find(a);
    b=find(b);
    if (a==b)
        return ;
    father[a]=b;
    ans--;
}

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

void fast_power()
{
    s=1;
    long long int t=26;
    while (ans>0)
    {
        if (ans%2==1)
            s=(s*t)%mod;
        t=(t*t)%mod;
        ans=ans/2;
    }
}

int main()
{
    while (cin>>n>>m)
    {
        int a,b;
        init();
        ans=n;
        for (int i=1;i<=m;i++)
        {
            cin>>a>>b;
            Union(a-1,b);
        }
        fast_power();
        cout<<s<<endl;
    }
}

参考:http://blog.csdn.net/u011663071/article/details/20231615


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。