NOIP复习资料终极版

《NOIP复习资料终极版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.高精度读入与输出用字符串读入数据,用数组存储数据.为了便于计算,可以用数组下标为0的元素记录该高精度数的长度.constmaxn=250;typearr=array[0..maxn]ofinteger;vara,b:arr;procedureinit(vara:arr);{读入部分}varstr:string;i,j,l:integer;beginreadln(str);fillchar(a,sizeof(a),0);a[0]:=length(str);fori:=1toa[0]doa[i]:=ord(str[a[0

2、]-i+1])-ord('0');end;procedureprint(a:arr);{输出部分}vari:integer;beginfori:=a[0]downto1dowrite(a[i]);writeln;end;begininit(a);init(b);print(a);print(b);end.高精度加法(1)A[i]+B[i]+进位得到和M；(2)Mmod10是结果的第i位数字；(3)Mdiv10是该位向下一位的进位.procedureadd(vara:arr;b:arr);varm,i,j:integer;

3、beginifa[0]0thenbegininc(a[0]);a[a[0]]:=m;end;end;高精度减法procedureminus(vara:arr;b:arr;varp:integer);{a-b}vari,j,k,m:integer;temp:arr;beginifa[0]>b[0]thenp:=1elseifa[0]

4、henp:=-1elsebegink:=a[0];while(a[k]=b[k])and(k>0)dodec(k);ifa[k]1)dodec(k);a[0]:=k;end;高精度乘法

5、(1)高精度乘以单精度proceduremulti1(vara:arr;x:integer);vari,m:integer;beginm:=0;fori:=1toa[0]dobegininc(m,a[i]*x);a[i]:=mmod10;m:=mdiv10;end;whilem<>0dobegininc(a[0]);a[a[0]]:=mmod10;m:=mdiv10;end;end;(2)高精度乘以高精度proceduremulti2(vara:arr;b:arr);varc:arr;i,j,k,l:integer;be

6、ginfillchar(c,sizeof(c),0);fori:=1toa[0]doforj:=1tob[0]doinc(c[i+j-1],a[i]*b[j]);fori:=1tomaxn-1dobegininc(c[i+1],c[i]div10);c[i]:=c[i]mod10;end;k:=maxn;while(c[k]=0)and(k>1)dodec(k);c[0]:=k;a:=c;end;2.位运算not:取反not(1)=0;not(0)=1;and:同真则真1and1=1;0and1=0;0and0=0;or

7、:有真则真1and1=1;0and1=1;0and0=0;xor:异真同假1and1=0;0and1=1;0and0=0;shl:ashlb就表示把a转为二进制后左移b位(在后面添b个0).ashlb的值实际上就是a乘以2的b次方,因为在二进制数后添一个0就相当于该数乘以2.shr:ashrb表示二进制右移b位(去掉末b位),相当于a除以2的b次方(取整).我们也经常用shr1来代替div2,比如二分查找.堆的插入操作等等.想办法用shr代替除法运算可以使程序效率大大提高.例如快排中mid选取可以定为mid:=a[(I+

8、j)shr1]以此替代mid:=a[(I+j)div2]常见应用:去掉x(二进制)最后一位如:10011>1001xshr1在x最后加一个0如:11101>111010xshl1在x最后加一个1如:110>1101(xshl1)+1把x最后一位变成1如:1110>1111;111>111xor1把最后一位变成0如:1