hdu 3461 Code Lock

点击打开hdu 3461

思路: 并查集+离散化+快速幂
分析:
1 题目给定长度为n的字符串，然后给定m个操作，询问最后的不同字符串的个数
2 考虑长度为n的时候，因为每个字符有26种情况('a'~'z')，所以有26^n。因为有m次的操作，题目中说了如果可以被变换那么认为是相同的字符串，那么不同的字符串就是所有不被操作区间的组合
3 那么我们利用并查集去求有操作的集合的个数，比如[1,3],[3,5]和[1,5]是三个集合，而[1,3],[4,5]和[1,5]则是2个集合
4 对于区间[l,r]，那么我们一般转化为处理(l-1,r],这样不用考虑端点的问题了，最后利用快速幂求出ans即可

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2001;

struct Node{
    int x;
    int y;
};
Node node[MAXN];

int n , m , pos;
int num[MAXN];
int father[MAXN];

void init(){
    sort(num , num+pos);
    pos = unique(num , num+pos)-num;
    for(int i = 0 ; i <= pos ; i++)
        father[i] = i;
}

int search(int x){
    int left = 0;
    int right = pos-1;
    while(left <= right){
         int mid = (left+right)>>1; 
         if(num[mid] == x)
             return mid+1;
         else if(num[mid] < x)
             left = mid+1;
         else
             right = mid-1;
    }
}

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

long long quickPow(long long m , long long n){
    long long sum = 1;
    while(n){
         if(n&1) 
            sum = (sum*m)%MOD; 
         n >>= 1;
         m = (m*m)%MOD;
    }
    return sum%MOD;
}

void solve(){
    int cnt = n;
    for(int i = 0 ; i < m ; i++){
        int x = search(node[i].x);    
        int y = search(node[i].y);    
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            father[fx] = fy; 
            cnt--;
        }
    }
    printf("%lld\n" , quickPow(26 , cnt));    
}

int main(){
    int x , y;
    while(scanf("%d%d" , &n , &m) != EOF){
        pos = 0;
        for(int i = 0 ; i < m ; i++){
             scanf("%d%d" , &node[i].x , &node[i].y); 
             node[i].x--;
             num[pos++] = node[i].x; 
             num[pos++] = node[i].y; 
        } 
        init();
        solve();
    }
    return 0;
}