RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。你当然可以写个O(n)的(怎么写都可以吧=_=),但是万一要询问最值1000000遍,估计你就要挂了。这时候你可以放心地写一个线段树(前提是不写错)应该不会挂。但是,这里有更简单的算法,就是ST算法,它可以做到O(nlogn)的预处理,O(1)地回答每个询问。 来看一下ST算法是怎么实现的(以最大值为例): 首先是预处理,用一个DP解决。设a[i]是要求区间最值的数列,f[i,j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。f[1,2]=5,f[1,3]=8,f[2,0]=2,f[2,1]=4……从这里可以看出f[i,0]其实就等于a[i]。这样,Dp的状态、初值都已经有了,剩下的就是状态转移方程。我们把f[i,j]平均分成两段(因为f[i,j]一定是偶数个数字),从i到i+2^(j-1)-1为一段,i+2^(j-1)到i+2^j-1为一段(长度都为2^(j-1))。用上例说明,当i=1,j=3时就是3,2,4,5 和 6,8,1,2这两段。f[i,j]就是这两段的最大值中的最大值。于是我们得到了动规方程F[i,j]=max(F[i,j-1],F[i+2^(j-i),j-1]).接下来是得出最值,一个很好的办法,做到了O(1)。还是分开来。如在上例中我们要求区间[2,8]的最大值,就要把它分成[2,5]和[5,8]两个区间,因为这两个区间的最大值我们可以直接由f[2,2]和f[5,2]得到。扩展到一般情况,就是把区间[l,r]分成两个长度为2^k的区间(保证有f[i,j]对应)。直接给出表达式:k:=trunc(ln(r-l+1)/ln(2));ans:=max(F[l,k],F[r-2^k+1,k]);(稍微解释一下:我们求得一个k,使2^k与[x,y]内的数的个数最接近,以保证二分的两个区间包含所有区间内所有数1 2 3 4 5 6 7 8———————— ———————— 5 6 7 8 9101112比如上图,有12个数(一条短线代表一个数),k最大为3,我们得到两个区间[1,8]和[5,12],这两个区间虽然有重复,但并不影响我们计算最大值。最大值可由f[1,3]和f[12-2^3+1,3]得到)这样就计算了从i开始,长度为2^t次的区间和从r-2^i+1开始长度为2^t的区间的最大值(表达式比较烦琐,细节问题如加1减1需要仔细考虑)代码:program RMQ;vara:array[1..200000] of longint;f:array[1..200000,0..19] of longint;d:array[0..19] of longint;n,i,m,k,x,y:longint;function max(x,y:longint):longint;beginif y>xthen max:=yelse max:=x;end;procedure ready;vari,j,t:integer;beginfor i:=1 to n dof[i,0]:=a[i];t:=trunc(ln(n)/ln(2));for j:=1 to t dofor i:=1 to n doif i+d[j]-1<=nthen f[i,j]:=max(f[i,j-1],f[i+d[j-1],j-1])else break;end;beginreadln(n);for i:=1 to n do//读入n个数据read(a[i]);readln(m);d[0]:=1;for i:=1 to 19 do//计算2^nd[i]:=d[i-1]*2;ready;//预处理for i:=1 to m dobeginreadln(x,y);if x<>ythen begin k:=trunc(ln(y-x+1)/ln(2)); writeln(max(f[x,k],f[y-d[k]+1,k]));//回答每个提问 endelse writeln(a[x]);end;end.
5,c语言中函数A调用函数BB又可以调用A
可以,刚刚你问了递归,a调用b,b用调用a也是递归,这种叫间接递归哈可以当然可以, 一直下去就溢出了。。 程序挂掉。可以的,不仅这样可以,直接A调用A也可以,而且这种用法还是挺多的,典型的例子是阶乘运算unsigned long factorial(unsigned long x) if (x > 1) return x * factorial(x-1); else return 1;}函数的调用8.4.1 函数调用的一般形式前面已经说过,在程序中是通过对函数的调用来执行函数体的,其过程与其它语言的子程序调用相似。C语言中,函数调用的一般形式为: 函数名(实际参数表)对无参函数调用时则无实际参数表。实际参数表中的参数可以是常数,变量或其它构造类型数据及表达式。各实参之间用逗号分隔。8.4.2 函数调用的方式在C语言中,可以用以下几种方式调用函数:1. 函数表达式:函数作为表达式中的一项出现在表达式中,以函数返回值参与表达式的运算。这种方式要求函数是有返回值的。例如:z=max(x,y)是一个赋值表达式,把max的返回值赋予变量z。2. 函数语句:函数调用的一般形式加上分号即构成函数语句。例如: printf ("%d",a);scanf ("%d",&b);都是以函数语句的方式调用函数。3. 函数实参:函数作为另一个函数调用的实际参数出现。这种情况是把该函数的返回值作为实参进行传送,因此要求该函数必须是有返回值的。例如: printf("%d",max(x,y)); 即是把max调用的返回值又作为printf函数的实参来使用的。在函数调用中还应该注意的一个问题是求值顺序的问题。所谓求值顺序是指对实参表中各量是自左至右使用呢,还是自右至左使用。对此,各系统的规定不一定相同。介绍printf 函数时已提到过,这里从函数调用的角度再强调一下。main() int i=8; printf("%d\n%d\n%d\n%d\n",++i,--i,i++,i--);}如按照从右至左的顺序求值。运行结果应为: 8 7 7 8如对printf语句中的++i,--i,i++,i--从左至右求值,结果应为: 9 8 8 9应特别注意的是,无论是从左至右求值, 还是自右至左求值,其输出顺序都是不变的, 即输出顺序总是和实参表中实参的顺序相同。由于Turbo C现定是自右至左求值,所以结果为8,7,7,8。上述问题如还不理解,上机一试就明白了。8.4.3 被调用函数的声明和函数原型在主调函数中调用某函数之前应对该被调函数进行说明(声明),这与使用变量之前要先进行变量说明是一样的。在主调函数中对被调函数作说明的目的是使编译系统知道被调函数返回值的类型,以便在主调函数中按此种类型对返回值作相应的处理。其一般形式为: 类型说明符 被调函数名(类型 形参,类型 形参…); 或为: 类型说明符 被调函数名(类型,类型…); 括号内给出了形参的类型和形参名,或只给出形参类型。这便于编译系统进行检错,以防止可能出现的错误。例8.1 main函数中对max函数的说明为:int max(int a,int b);或写为: int max(int,int);C语言中又规定在以下几种情况时可以省去主调函数中对被调函数的函数说明。1) 如果被调函数的返回值是整型或字符型时,可以不对被调函数作说明,而直接调用。这时系统将自动对被调函数返回值按整型处理。例8.2的主函数中未对函数s作说明而直接调用即属此种情形。2) 当被调函数的函数定义出现在主调函数之前时,在主调函数中也可以不对被调函数再作说明而直接调用。例如例8.1中,函数max的定义放在main 函数之前,因此可在main函数中省去对max函数的函数说明int max(int a,int b)。3) 如在所有函数定义之前,在函数外预先说明了各个函数的类型,则在以后的各主调函数中,可不再对被调函数作说明。例如: char str(int a); float f(float b); main() …… } char str(int a) …… } float f(float b) …… }其中第一,二行对str函数和f函数预先作了说明。因此在以后各函数中无须对str和f函数再作说明就可直接调用。4) 对库函数的调用不需要再作说明,但必须把该函数的头文件用include命令包含在源文件前部。8.5 函数的嵌套调用C语言中不允许作嵌套的函数定义。因此各函数之间是平行的,不存在上一级函数和下一级函数的问题。但是C语言允许在一个函数的定义中出现对另一个函数的调用。这样就出现了函数的嵌套调用。即在被调函数中又调用其它函数。这与其它语言的子程序嵌套的情形是类似的。其关系可表示如图。图表示了两层嵌套的情形。其执行过程是:执行main函数中调用a函数的语句时,即转去执行a函数,在a函数中调用b 函数时,又转去执行b函数,b函数执行完毕返回a函数的断点继续执行,a函数执行完毕返回main函数的断点继续执行。计算s=22!+32!本题可编写两个函数,一个是用来计算平方值的函数f1,另一个是用来计算阶乘值的函数f2。主函数先调f1计算出平方值,再在f1中以平方值为实参,调用 f2计算其阶乘值,然后返回f1,再返回主函数,在循环程序中计算累加和。long f1(int p) int k; long r; long f2(int); k=p*p; r=f2(k); return r;}long f2(int q) long c=1; int i; for(i=1;i<=q;i++) c=c*i; return c;}main() int i; long s=0; for (i=2;i<=3;i++) s=s+f1(i); printf("\ns=%ld\n",s);}在程序中,函数f1和f2均为长整型,都在主函数之前定义,故不必再在主函数中对f1和f2加以说明。在主程序中,执行循环程序依次把i值作为实参调用函数f1求i2值。在f1中又发生对函数f2的调用,这时是把i2的值作为实参去调f2,在f2 中完成求i2!的计算。f2执行完毕把C值(即i2!)返回给f1,再由f1返回主函数实现累加。至此,由函数的嵌套调用实现了题目的要求。由于数值很大,所以函数和一些变量的类型都说明为长整型,否则会造成计算错误。