数字对
【题目描述】
小H是个善于思考的学生，现在她又在思考一个有关序列的问题。
她的面前浮现出一个长度为n的序列{ai}，她想找出一段区间[L, R](1 <= L <= R <= n)。
这个特殊区间满足，存在一个k(L <= k <= R)，并且对于任意的i(L <= i <= R)，ai都能被ak整除。这样的一个特殊区间 [L, R]价值为R - L。
小H想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些区间又分别是哪些呢？你能帮助她吧。
【输入格式】
第一行，一个整数n.
第二行，n个整数，代表ai.
【输出格式】
第一行两个整数，num和val,表示价值最大的特殊区间的个数以及最大价值。
第二行num个整数，按升序输出每个价值最大的特殊区间的L.
【样例输入1】
5
4 6 9 3 6
【样例输出1】
1 3
2
【样例输入2】
5
2 3 5 7 11
【样例输出2】
5 0
1 2 3 4 5
【数据范围】
30%: 1 <= n <= 30 , 1 <= ai <= 32.
60%: 1 <= n <= 3000 , 1 <= ai <= 1024.
80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.
100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.
【思路】
题不是很难，就是可能一些细节注意不到或者优化想不到
我拿到题后的第一反应是一个数组f[i][j][k]表示从i开始的j位来记录这个区间的最小值和最大公约数
随便举一些例子就不难发现，其实要满足条件的区间，整除的那个数是这个区间最小而且是最大公约数
那么题就简单了，就是求最小值和最大公约数相同的区间，然后找到区间最大的并输出左端点
我们之前定义了一个f[i][j][k]，然后结合一起的知识，我们不难有一个大胆的想法
就是用RMQ来处理这个小小细节，表示为gcdn[i][j]是从i位开始的2^j位这个区间的最大公约数
minn[i][j]是从i为开始的2^j位这个区间的最小值
这里一想出来，接下来就是区间的最大长度了。。。这个简单，枚举一下这个长度然后找gcd和min相同的区间
当然，枚举，不存在的，直接二分就行了。。。。另外一提，这题非常容易超时
所以我来提几个细节
1.在RMQ时的外循环，不能循环到int类型的边界，而是要根据n来定义，循环到log₂n次（注意不要搞成根号n了），j是代表2^j次方
2.在表示2^j次方不要直接用函数pow，要用位运算，位运算的时间消耗更小。。。
只有这样才不会超时
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #include<cstdlib> 5 #include<cmath> 6 #include<cstring> 7 #include<queue> 8 #define maxn 500005 9 using namespace std; 10 int gcdn[maxn][32],minn[maxn][32],n,m,a[maxn]; 11 int gcd(int a,int b){ 12 if(b==0)return a; 13 else return gcd(b,a%b); 14 } 15 void rmq(){ 16 for(int j=1;j<=(int)log2(n);j++){ 17 for(int i=1;i<=n;i++){ 18 int new_=pow(2.0,j)+i-1; 19 if(new_>n)continue; 20 minn[i][j]=min(minn[i][j-1],minn[i+ (1<<(j-1))][j-1]); 21 gcdn[i][j]=gcd(gcdn[i][j-1],gcdn[i+ (1<<(j-1))][j-1]); 22 } 23 } 24 } 25 int ans[maxn],num,val,len; 26 void change(int l,int r,int n){ 27 if(l==r)return; 28 int mid=(l+r)>>1; 29 int j=log2(mid+1); 30 for(int i=1;i<=n-mid;i++){ 31 int a1,a2; 32 a1=min(minn[i][j],minn[i+mid- (1<<j) + 1][j]); 33 a2=gcd(gcdn[i][j],gcdn[i+mid- (1<<j) + 1][j]); 34 if(a1==a2){ 35 num++;ans[num]=i; 36 } 37 } 38 if(num==0)change(l,mid,n); 39 else{ 40 val=mid;len=num; 41 num=0;change(mid+1,r,n); 42 } 43 } 44 int main(){ 45 scanf("%d",&n); 46 for(int i=1;i<=n;i++){ 47 scanf("%d",&a[i]); 48 gcdn[i][0]=minn[i][0]=a[i]; 49 } 50 rmq(); 51 change(0,n-1,n); 52 printf("%d %d ",len,val); 53 for(int i=1;i<=len;i++){ 54 printf("%d ",ans[i]); 55 } 56 }
总结：
1.对于区间的最值一类问题，可以用RMQ解决
2.pow函数的使用要注意pow出来的值是浮点数，而且pow函数里的第一个数必须是浮点数，比如要求2^j，就是pow( 2.0, j )，当然这个细节是因为cena里会编译错误，自己是不会报错的
3.能用位运算就尽量用位运算，特别是循环中会多次执行一个语句，换成位运算后可以大大省下时间
4.注意区分一下log2和sqrt，两个出来的值不同，比如log2(64)=6,sqrt(64)=8，初中数学，相信就不用解释了