NOIP复习资料终极版.docx
- 文档编号:18503661
- 上传时间:2023-08-18
- 格式:DOCX
- 页数:45
- 大小:27.77KB
NOIP复习资料终极版.docx
《NOIP复习资料终极版.docx》由会员分享,可在线阅读,更多相关《NOIP复习资料终极版.docx(45页珍藏版)》请在冰点文库上搜索。
NOIP复习资料终极版
1.高精度
读入与输出
用字符串读入数据,用数组存储数据.
为了便于计算,可以用数组下标为0的元素记录该高精度数的长度.
const
maxn=250;
type
arr=array[0..maxn]ofinteger;
var
a,b:
arr;
procedureinit(vara:
arr);{读入部分}
var
str:
string;
i,j,l:
integer;
begin
readln(str);
fillchar(a,sizeof(a),0);
a[0]:
=length(str);
fori:
=1toa[0]do
a[i]:
=ord(str[a[0]-i+1])-ord('0');
end;
procedureprint(a:
arr);{输出部分}
vari:
integer;
begin
fori:
=a[0]downto1do
write(a[i]);
writeln;
end;
begin
init(a);
init(b);
print(a);
print(b);
end.
高精度加法
(1)A[i]+B[i]+进位得到和M;
(2)Mmod10是结果的第i位数字;
(3)Mdiv10是该位向下一位的进位.
procedureadd(vara:
arr;b:
arr);
var
m,i,j:
integer;
begin
ifa[0]
a[0]:
=b[0];
m:
=0;
fori:
=1toa[0]do
begin
m:
=m+a[i]+b[i];
a[i]:
=mmod10;
m:
=mdiv10;
end;
ifm>0then
begin
inc(a[0]);
a[a[0]]:
=m;
end;
end;
高精度减法
procedureminus(vara:
arr;b:
arr;varp:
integer);{a-b}
var
i,j,k,m:
integer;
temp:
arr;
begin
ifa[0]>b[0]then
p:
=1
elseifa[0]
p:
=-1
else
begin
k:
=a[0];
while(a[k]=b[k])and(k>0)do
dec(k);
ifa[k]
p:
=-1;
end;
ifp<0then
begin
temp:
=a;
a:
=b;
b:
=temp;
end;
fori:
=1toa[0]do
begin
a[i]:
=a[i]-b[i];
ifa[i]<0then
begin
dec(a[i+1]);
inc(a[i],10);
end;
end;
k:
=a[0];
while(a[k]=0)and(k>1)do
dec(k);
a[0]:
=k;
end;
高精度乘法
(1)高精度乘以单精度
proceduremulti1(vara:
arr;x:
integer);
var
i,m:
integer;
begin
m:
=0;
fori:
=1toa[0]do
begin
inc(m,a[i]*x);
a[i]:
=mmod10;
m:
=mdiv10;
end;
whilem<>0do
begin
inc(a[0]);
a[a[0]]:
=mmod10;
m:
=mdiv10;
end;
end;
(2)高精度乘以高精度
proceduremulti2(vara:
arr;b:
arr);
varc:
arr;
i,j,k,l:
integer;
begin
fillchar(c,sizeof(c),0);
fori:
=1toa[0]do
forj:
=1tob[0]do
inc(c[i+j-1],a[i]*b[j]);
fori:
=1tomaxn-1do
begin
inc(c[i+1],c[i]div10);
c[i]:
=c[i]mod10;
end;
k:
=maxn;
while(c[k]=0)and(k>1)do
dec(k);
c[0]:
=k;
a:
=c;
end;
2.位运算
not:
取反not
(1)=0;not(0)=1;
and:
同真则真1and1=1;0and1=0;0and0=0;
or:
有真则真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+j)shr1]以此替代mid:
=a[(I+j)div2]
常见应用:
去掉x(二进制)最后一位
如:
10011>1001
xshr1
在x最后加一个0
如:
11101>111010
xshl1
在x最后加一个1
如:
110>1101
(xshl1)+1
把x最后一位变成1
如:
1110>1111;111>111
xor1
把最后一位变成0
如:
1111>1110;100>100
xor1-1
最后一位取反
如:
111>110;100>101
xxor1
把右数第k位变成1
如:
1011>1111;11>11
xor(1shl(k-1))
把右数第k位变成0
如:
1110>1100;100>100
xxor(1shl(k-1))
右数第k位取反
如:
111>101;11001>11101;
xxor(1shl(k-1))
取x末k位
如:
11101>101(k=3)
xand((1shlk)-1)
取右数第k位
如:
11101>1(k=3)
xshr(k-1)and1
把末k位变成1
如:
110000>111111(k=4)
xor((1shlk)-1)
末k位取反
如:
110111>110000(k=3)
xxor((1shlk)-1)
把右边连续的1变成0
如:
1010111>1010000
xand(x+1)
把右起第一个0变成1
如:
1010111>1011111
xor(x+1)
把右边连续的0变成1
如:
1010000>1011111
xor(x-1)
取右边连续的1
如:
10111>111
(xxor(x+1))shr1
去掉右起第一个1的左边
如:
110>11
xand(xxor(x-1))
3.常见排序
快速排序(从小到大,下同)
procedureqsort(vardata:
arr;t,w:
longint);
var
i,j,mid,a,b:
longint;
begin
ifw>=tthen
exit;
i:
=t;
j:
=w;
mid:
=data[(w+t)shr1];
repeat
whiledata[i] inc(i); whiledata[j]>middo dec(j); ifi<=jthen begin a: =data[i]; data[i]: =data[j]; data[j]: =a; inc(i); dec(j); end; untili>j; ifi qsort(data,i,w); ift qsort(data,t,j); end; 冒泡排序 procedurebsort(vardata: arr); var i,j: integer; begin fori: =1ton-1do forj: =ndowntoi+1do ifa[j-1]>a[j]then begin a[0]: =a[j]; a[j]: =a[j-1]; a[j-1]: =a[0]; end; end; 堆排序1 procedureswap(i,j: longint);//交换 var t: longint; begin t: =a[i]; a[i]: =a[j]; a[j]: =t; end; procedureheapdown(i: longint); var l,r.m: longint; begin l: =ishl1;{l: =i*2;l是i的左儿子} r: =ishl1+1;{r: =(i*2)+1;r是i的右儿子} if(l<=n)and(a[l]>a[i])then m: =l else m: =i; if(r<=n)and(a[r]>a[m])then m: =r; ifi<>mthen begin swap(i,m); heapdown(m); end; end; procedureheapup(i: longint); var f: longint; begin f: =ishr1;{f: =idiv2;f是i的父亲}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP 复习资料 终极
![提示](https://static.bingdoc.com/images/bang_tan.gif)