密码锁(并查集+快速幂C++)

xiaoxiao2021-03-01  42

密码锁 总时间限制: 5000ms 内存限制: 524288kB 描述 世界上有一种圆筒形密码锁,这种锁有n位,每一位是a-z中的任意一个字母,这种锁一共有m个可操作的区间,对于每个区间都可以整体向上转动(可以转动多次)。比如abc向上转一下就是bcd,zab向上转一下就是abc(z向上转就是a)。你可以同时转动每个区间内的密码锁,能够通过转动使之一样的密码锁为同一种密码,问你这个密码锁总共有多少种不同的密码。 (如可以操作2-4这个区间,那么ABBB和AAAA就是同一个密码。) 输入 输入有一系列测试样例,每个测试样例包含两个整数N(1<=N<=100000000)和M(0<=M<=1000000),分别代表圆筒形密码锁的长度和可操作的区间数量。 接下来M行。每行包含两个整数L和R(1<=L<=R<=N),表示一个可操作的区间。 输出 输出不同的密码数,答案对1000000007取模。 样例输入

1 1 1 1 2 1 1 2

样例输出

1 26

思路点拔:首先,我们走一走样例,第一个就不看了,那么第二个为什么是26种呢?我们可以这么想:首先确定一个区间,然后我们就去算另一个区间可取的情况有多少种,所以26就是这么来的,所以,本题就是用并查集去对输入的两个数作为等价类去进行合并,然后,答案就是26的(n-合并次数)次方,所以,代码应该很明确了,就是要注意:由于本题的数据非常大,所以我们需要进行读入优化,否则会超时,求26的幂就是需要用一个二分思想的快速幂来进行计算,否则也会超时,最后模一下就完事了~,上代码!!!

#include<cstdio> #include<iostream> using namespace std; int tot,n,m; int mo=1000000007; //模数 long long qkpow(int n) //快速幂 { long long i=1,ans=26; while(n>0) { if(n%2==1) //用二分的思想进行快速计算 { i*=ans; i%=mo; //每次算完就要取模 } ans*=ans; ans%=mo; n/=2; //二分 } return i; //返回结果 } int fa[200000005]; //定义fa数组存储每个节点的父亲节点 void makeSet(int n) //初始化 { for(int i=1;i<=n;i++) fa[i]=i; } int find(int n)//寻找根节点 { if(n!=fa[n]) //用递归思求根节点 fa[n]=find(fa[n]); return fa[n]; } void unionSet(int a,int b) //合并 { int x=find(a),y=find(b); //记录两个数的根节点 if(x!=y) //如果根节点不相等 { fa[x]=y; //合并 tot++; //统计合并次数 } } bool read(int &x) //读入优化(在本题,读入优化比scanf快200多毫秒) { int f=1; x=0; char s=getchar(); while(s<'0'||s>'9') //如果输入的东西不是数字 { if(s=='-') //如果是负的 f=-1; //f就等于-1 s=getchar(); //继续读入(getchar()比scanf快得多) } while(s>='0'&&s<='9') //如果是数字 { x=x*10+s-'0'; //继续读入 s=getchar(); } x*=f; } int main() { while(scanf("%d%d",&n,&m)!=EOF) //无限输入 { tot=0; //初始时合并次数为0 makeSet(n);//初始化 int a,b; for(int i=1;i<=m;i++) //输入 { read(a); read(b); unionSet(a-1,b); //合并 } printf("%lld\n",qkpow(n-tot)%mo); //输出结果 } return 0;//结束了 } //思路不难,但是极易超时(我错了45次 >_<),所以一定要注意,因为时间卡得很紧
转载请注明原文地址: https://www.6miu.com/read-4200121.html

最新回复(0)