《noip复习资料终极版》由会员分享，可在线阅读，更多相关《noip复习资料终极版（30页珍藏版）》请在金锄头文库上搜索。
1、1.1.高精度高精度 读入与输出 用字符串读入数据,用数组存储数据. 为了便于计算,可以用数组下标为0的元素记录该高精度数的长度. constconst maxn=250; typetype arr=arrayarray0.maxn ofof integer; varvar a,b:arr;procedureprocedure init(varvar a:arr);读入部分 varvar str:stringstring;i,j,l:integer; beginbeginreadln(str);fillchar(a,sizeof(a),0);a0:=length(str);forfor i:=
2、1 toto a0 dodoai:=ord(stra0-i+1)-ord(0); endend;procedureprocedure print(a:arr);输出部分 varvar i:integer; beginbeginforfor i:=a0 downtodownto 1 dodowrite(ai);writeln; endend;beginbegininit(a);init(b);print(a);print(b); endend.高精度加法 (1)Ai+Bi+进位得到和M； (2)M modmod 10是结果的第i位数字；(3)M divdiv 10 是该位向下一位的进位. pro
3、cedureprocedure add(varvar a:arr;b:arr); varvar m,i,j:integer; beginbeginifif a00 thenthen beginbegininc(a0);aa0:=m;endend; endend;高精度减法 procedureprocedure minus(varvar a:arr;b:arr;varvar p:integer);a-b varvar i,j,k,m:integer;temp:arr; beginbeginifif a0b0 thenthen p:=1elseelse ifif a00) dododec(k);i
4、fif ak1) dodo dec(k);a0:=k; endend;高精度乘法 (1)高精度乘以单精度 procedureprocedure multi1( varvar a:arr;x:integer); varvar i,m:integer; beginbeginm:=0;forfor i:=1 toto a0 dodobeginbegininc(m,ai*x);ai:=m modmod 10;m:=m divdiv 10;endend;whilewhile m1) dododec(k);c0:=k;a:=c; endend;2.2.位运算位运算 notnot:取反 notnot(1)=
5、0; notnot(0)=1; andand:同真则真 1 andand 1=1; 0 andand 1=0; 0 andand 0=0; oror :有真则真 1 andand 1=1; 0 andand 1=1; 0 andand 0=0; xorxor:异真同假 1 andand 1=0; 0 andand 1=1; 0 andand 0=0; shlshl:a shlshl b就表示把a转为二进制后左移b位(在后面添b个0).a shlshl b的值实际上就是a乘以2的b次方,因为在二进制数后添一个0就相当于该 数乘以2. shrshr:a shrshr b表示二进制右移b位(去掉末b
6、位),相当于a除以2的b次方(取整).我们也经常用shrshr 1来代替divdiv 2,比如二分查找.堆的插入操作等等.想办法用shr代替除法运算可以使程序效率大大提高.例如快排中mid选取可以定为 mid:=a(I+j)shrshr 1 以此替代 mid:=a(I+j) divdiv 2常见应用: 去掉x(二进制)最后一位 如:100111001 x shrshr 1在x最后加一个0 如:11101111010x shlshl 1在x最后加一个1 如:1101101 (x shlshl 1)+1把x最后一位变成1 如:11101111;111111 x oror 1把最后一位变成0 如:1
7、1111110;100100 x oror 1-1最后一位取反 如:111110;100101 x xorxor 1把右数第k位变成1 如:10111111;1111 x oror (1 shlshl (k-1)把右数第k位变成0 如:11101100;100100 x xorxor (1 shlshl (k-1)右数第k位取反 如:111101;1100111101; x xorxor (1 shlshl (k-1)取x末k位 如:11101101 (k=3) x andand (1 shlshl k)-1)取右数第k位 如:111011(k=3)x shrshr (k-1) andand
8、1把末k位变成1 如:110000 111111(k=4) x oror (1 shlshl k)-1)末k位取反 如:110111110000(k=3) x xorxor (1 shlshl k)-1)把右边连续的1变成0 如:10101111010000 x andand (x+1)把右起第一个0变成1 如:10101111011111 x oror (x+1)把右边连续的0变成1 如:10100001011111 x oror (x-1)取右边连续的1 如:10111111 (x xorxor (x+1) shrshr 1去掉右起第一个1的左边 如:11011 x andand (x x
9、orxor (x-1)3.3.常见排序常见排序 快速排序(从小到大,下同) procedureprocedure qsort(varvar data:arr;t,w:longint); varvar i,j,mid,a,b:longint; beginbeginifif w=t thenthen exit;i:=t;j:=w;mid:=data(w+t) shr 1;repeatrepeatwhilewhile dataimid dodo dec(j);ifif ij;ifif iaj thenthen beginbegina0:=aj;aj:=aj-1;aj-1:=a0;endend; en
10、dend;堆排序1 procedureprocedure swap(i,j:longint);/交换 varvar t:longint; beginbegint:=ai;ai:=aj;aj:=t; endend;procedureprocedure heapdown(i:longint);varvar l,r.m:longint;beginbeginl:=i shlshl 1;l:=i*2;l是i的左儿子r:=i shlshl 1+1;r:=(i*2)+1;r是i的右儿子ifif (lai) thenthen m:=lelseelse m:=i;ifif (ram) thenthen m:=r
11、;ifif iai divdiv 2) thenthen swap(i divdiv 2,i)elseelse break;endend; endend;procedureprocedure deal;/主程序 beginbeginforfor i:=n divdiv 2 downtodownto 1 dodobuild(i,n);forfor i:=n downtodownto 2 dodobeginbeginswap(1,i);build(1,i-1);endend; endend; 4.Pascal4.Pascal常见函数与过程常见函数与过程 函数 copy(s,i,l) 从字符串s中截
12、取第I个字符开始后的长度为L的子串 如:copy(abcdef,2,2)=bclength(s) 求字符串s的长度如:length(edwsa)=5pos(s1,s2) 如果s1是s2的子串 ,则返回s1的第一个字符在s2中的位置,若不是子串,则返回0 如:pos(a,bcabca)=3upcase(ch) 求字符ch的大写体 如:upcase(a)=Ainc(i) 使i:=i+1; inc(i,b)使i:=i+b; dec(i) 使i:=i-1; dec(i,b)使i:=i-b; abs(x) 求x的绝对值 chr(x) 求ACSII码x对应的字符 ord(ch) 求字符ch对应的编号(注:
13、ord(false)=0 ord(true)=1) sqr(x) 求x的平方 sqrt(x) 求x的正根 round(x)求x的四舍五入 trunc(x)求x的整数部分 结果是integer型 int(x) 求x的整数部分 结果是real型 frac (x)求x的小数部分 pred(x) 求x的前导(pred(true)=false) succ(x) 求x的后继(succ(false)=true) odd(x) 判断x是否为奇数.如果是值为true,反之值为false. 如:odd(2)=false odd(5)=true eof 布尔函数,用于判断文件结束否. Eoln 布尔函数,用于判断行
14、结束否.过程 detele(s,i,l) 从字符串s中删除第I个字符开始后的长度为l的子串 如:delete(abcdef,2,2)adefinsert(s1,s2,i) 把s1插入到s2的第i个位置 如:insert(12,abc,2)a12bcstr(x,s) 把数值x化为数串s如:str(123,s) s=123val(s,x,i) 把数串s转化为数值x,如果成功则i=0,不成功则i为无效字符的序数 如:val(123,x,i) x=123 i=0fillchar(a,sizeof(a),x): x=00 x=$7Fmaxlongint x=$F0-maxlongint5.5.经典动规方
15、程经典动规方程 0/1背包 一维动规版: forfor i:=1 toto n dodoforfor j:=vmax downtodownto vi dodofj:=max(fj,fj-vi+wi); 二维动规版: forfor i:=1 toto n dodoforfor j:=0 toto vmax dodobeginbeginfi,j:=fi-1,j;ifif j=vi thenthen fi,j:=max(fi,j,fi-1,j-vi+wi);endend;完全背包 一维动规版: forfor i:=1 toto n dodoforfor j:=0 toto vmax dodofj:=max(fj,fj-vi+wi); 二维动规版: forfor i:=1 toto n dodoforfor j:=0 toto vmax dodofi,j:=max(fi,j,fi-k,j-k*vi+k*wi);(01 bjj) andand (costi,j=0) thenthen costi,j:=maxint;endend;readln;endend;forfor i:=1 toto n dodobeginbeginclosedi:=1;mincosti:=cost1,i;enden
