首页 > 代码库 > HDU 2017 Code Lock (并查集的应用+快速幂)
HDU 2017 Code Lock (并查集的应用+快速幂)
链接:HDU 3461
题目大意:
题目的大意是一个密码锁上有编号为1到N的N个字母,每个字母可以取26个小写英文字母中的一个。再给你M个区间[L,M],表示该区间的字母可以一起同步“增加”(从‘a‘变为‘b‘为增1,‘z‘增1为‘a‘)。假如一组密码按照给定的区间进行有限次的“增加”操作后可以变成另一组密码,那么我们认为这两组密码是相同的。该题的目标就是在给定N、M和M个区间的前提下计算有多少种不同的密码。
根据题意,如果一个可调整的区间都没有的话,答案应该是26的N次方。每当加入一个区间的时候,答案就减少为之前的26分之1(因为该区间的加入使得原本不同的26种情况变得等价了)。因此当有x个“不同的”区间加入进来之后,答案应该为26^(N-x)。
思路:
所以题目就是求区间的个数了。但是注意的是 【1,3】【4,5】和【1,5】区间是等价的。【1,3】【3,5】和【1,5】又是不等价的的,因为3是重叠的。
如何解决区间个数,用并查集刚好,不过要变化的是merge_set(l-1,r)或者merge_set【l,r+1】这样可以解决,线段的拼接问题。这里要好好想一下。
代码:
#include<iostream> #include<cstdio> #include<cstring> #define mod 1000000007 #define N 10000000+10 using namespace std; typedef long long int64; int uset[N]; //int rank[N]; int cnt; void make_set(int n) { for(int i=0;i<=n;i++) { uset[i]=i; //rank[i]=1; } } int find_set(int x) { if(uset[x]!=x) uset[x]=find_set(uset[x]); return uset[x]; } void merge_set(int x,int y) { int fx=find_set(x); int fy=find_set(y); if(fx==fy) return; else { uset[fx]=fy; cnt++; } } int64 exp(int n) { int64 res=1; int64 tmp=26; while(n) { if(n&1) res=(res*tmp)%mod; tmp=tmp*tmp%mod; n>>=1; } return res; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { make_set(n); cnt=0; for(int i=0;i<m;i++) { int l,r; scanf("%d%d",&l,&r); merge_set(l-1,r); } //printf("-->%d\n",n-cnt); printf("%I64d\n",exp(n-cnt)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。