noip复赛模拟练习答案.docx

《noip复赛模拟练习答案.docx》由会员分享，可在线阅读，更多相关《noip复赛模拟练习答案.docx（20页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1. TOM有一个无穷序列中如下：1100100000。 请你扶植TOM找出在这个无穷序列中指定位置上的数字 输入格式 Input Format 第一行一个正整数N，表示询问的次数； 接下来的N行一个正整数Ai,Ai表示在序列中的位置。 输出格式 Output Format N行，每一行为0或1，表示序列第Ai位上的数字。 对于100%的数据有N=1500000,Ai=109var n,i:longint; x,z,y:int64;begin readln(n); for i:=1 to n do begin readln(x); z:=(x-1)*2; y:=trunc(sqrt(z);if

2、 z=y*(y+1) then writeln(1) else writeln(0); end;readln;readln;end.输入 39910111输出0 0 1输入 5 7 1024 15 10000 4 输出 1 0 0 0 12. 输入一个正整数N1 = N =20后，可以得到一个N*N的数字螺旋方阵，分别求该方阵中的主对角线与副对角线上的数字之与S，P，输出S、P的差。 例如：N=5 得到的数字螺旋方阵如下： 1 2 3 4 5 其中：主对角线从左上角到右下角，得到 16 17 18 19 6 的数字之与为：S=1+17+25+21+9=73 15 24 25 20 7 副对角线

3、从右上角到左下角，得到 14 23 22 21 8 的数字之与：P=5+19+25+23+13=85 13 12 11 10 9 S-P= - 12Input 一个正整数NOutput主对角线与副对角线上的数字之与的差。Sample Input 5Sample Output -12var n,i,j,t,f,l,q,z:integer;s1,s2:longint; a:array1.20,1.20 of integer;begin readln(n); t:=1; f:=1; l:=n;i:=1;q:=1;z:=n; while t=n*n do begin case f of 1:begin

4、 for j:=q to z do begin ai,j:=t;inc(t);end; f:=2; q:=i+1;dec(l); z:=l+q-1; end; 2:begin for i:=q to z do begin ai,j:=t;inc(t);end; f:=3;q:=j-1; z:=q-l+1; end; 3:begin for j:=q downto z do begin ai,j:=t;inc(t); end; f:=4;q:=i-1;dec(l);z:=q-l+1; end; 4:begin for i:=q downto z do begin ai,j:=t;inc(t);

5、end; f:=1;q:=j+1;z:=q+l-1; end; end; end; s1:=0;s2:=0; for i:=1 to n do s1:=s1+ai,i; for i:=n downto 1 do s2:=s2+an-i+1,i; writeln(s1-s2);end. 输入 7 输出 -24输入 20 输出 -200 输入 12 输出-7215 输出 -1123.字母A，B，C的全部可能的组合按字典依次排序是： A， AB，ABC，AC，B，BC，C 每个组合都对应一个字典依次的序号，如下所示： 1A 2AB 3ABC 4AC 5B 6BC 7C 找出某个字母组合的字典序号。例

6、如，上例中AC的字典序号是4。 注:假设某个字母组合为X1X2X3XK,保证X1X2X3XK。 输入：输入包括2行： 第一行：N，表示字母组合由字母表中前NN=26个字母组成； 第二行：某一个字母组合,都是大写字母； 输出：该字母组合的序号； 输入样例： 3 AB 输出样例： 2 fi表示为i位的总方案数,每读一位就累加 var n,i,j,tot:longint; f:array0.27 of longint; a:array0.26 of char; c:char; begin fillchar(f,sizeof(f),0); readln(n); for i:=n downto 1 do

7、 begin for j:=i+1 to n do fi:=fi+fj; inc(fi); end; tot:=0; j:=0; a0:=; while not eoln do begin inc(j); read(aj); for i:=ord(aj-1)-64+1 to ord(aj)-64-1 do tot:=tot+fi; inc(tot); end; writeln(tot); end.二进制数n mod m的结果是多少？ 输入数据 第一行输入一个二进制数n。 第二行输入一个二进制数m。 输出数据 输出n mod m的结果。 输入样例 1010101010 111000 输出样例 1

8、010 数据规模 n的长度二进制数的位数=200 000； m的长度二进制数的位数=20。 与进制的高精同理，进制每次乘，进制每次乘 program fdfd; var a,ans:array0.200000 of longint; b,i,r:longint; c:char; begin a0:=0; while not eoln do begin read(c); inc(a0); aa0 :=ord(c)-48; end; readln; b:=0; while not eoln do begin read(c); b:=b*2+ord(c)-48; end; r:=0; for i:=

9、1 to a0 do r:=(r*2+ai)mod b ; ans0:=0; repeat inc(ans0); ansans0:=r mod 2; r:=r div 2; until r=0; for i:=ans0 downto 1 do write(ansi); writeln; end.输入 1110001111 1111100 输出 101011输入 11111114. 的奖金_如今，Sally要参与竞赛，她邀请参与OI的你一起扶植，成功后七三分成_输入格式第一行一个数N，表示吃的天数Naj) and (sj+1si) then si:=sj+1; if sim then m:=si

10、; end; writeln(m);end.输入 4100 500 400 3505. NSDFZ的同学们为了庆贺春节，打算排练一场舞会。 描绘 Description 明显交谊舞是2个人跳的，而且一男一女 -_-|。 由于交谊舞之前的节目支配，全部的表演者都站成了一排。这一排人的依次满意2点： 对于一对舞伴男生站在女生的左边。 任何一对舞伴之间,要么没有人，要么就有假设干对舞伴。 排得过于整齐导致那些要表演交谊舞的人都没方法看到自己的舞伴，怎么办类. 所幸的是，SDFZ的女生比男生聪慧得多。她们知道自己左边有几个男生。 如今就请你再告知这些女生，她们的舞伴间隔 她们多远即包括那个男生，一共有

11、多少男生夹在他们之间。 输入格式 Input Format 第一行为一个数n，表示参与跳交谊舞的女生个数。 第二行n个数，从左到右表示这n个女生左边分别有多少个男生。 输出格式 Output Format 一排n个数，行末无空格。表示n个女生与其舞伴的间隔 。样例输入64 5 6 6 6 6样例输出1 1 1 4 5 6假设相邻的两个女生以左的男生人数不一样，那么当前女生与其舞伴的间隔 确定为一，很好想。接着考虑一样的状况，往前找，找到第一个可用男生时，就可以求解了，详细操作见程序。program vijos1062;var head,tail,n,i,j,now,cal,k:longint;

12、 ans:array1.1500 of longint; data:array0.1500 of longint; flag:boolean;begin readln(N); now:=0; for i:=1 to n do begin read(datai); end; readln; now:=1; for i:=1 to n do begin cal:=datai; k:=i-1; if datai=datai-1 then begin flag:=false; while not(flag) do begin if datak=datai then begin dec(cal); de

13、c(k); end; if (dataidatak) and (datai-datakdatai-cal) then flag:=true; if (dataidatak) and (datai-datak=datai-cal) then begin dec(cal); dec(k); end; end; ansi:=datai-cal+1; end else begin ansi:=1; end; end; for i:=1 to n-1 do write(ansi, ); writeln(ansn);end.6. 键盘输入一个含有括号的四那么运算表达式，可能含有多余的括号，编程整理该表达式

14、，去掉全部多余的括号，原表达式中全部变量与运算符相对位置保持不变，并保持与原表达式等价。例：输入表达式应输出表达式a+(b+c) a+b+c (a*b)+c/d a*b+c/da+b/(c-d) a+b/(c-d)留意输入a+b时不能输出b+a。表达式以字符串输入，长度不超过。输入不要判错。全部变量为单个小写字母。只是要求去掉全部多余括号，不要求对表达式化简。二、算法分析四那么运算表达式含运算符+,-,*,/,(,)，其优先依次由低至高为+,- *,/ (,)一个括号是否作为多余的括号剔除，关键是分析该括号内优先级最低的运算符与左邻括号或右邻括号的运算符之间的运算优先关系：设待整理的表达式为(

15、s1 op s2)；op括号内优先级最低的运算符(+,-或*,/);、假设左邻括号的运算符为/，那么无论op为何运算符，括号必需保存，即 /( s1 op s2)。因为原式(s1 op s2)作为除数，一旦去除括号后，仅s1作为除数，不可能与原式等价；、假设左邻括号的运算符为*或-，而op为+或-，那么保存括号，即*-(s1+-s2)。不能去除括号的缘由是：假设左邻标符为*，优先级大于括号内运算符，因此必需用括号保证括号内的+或-优先进展;假设左邻算符为-，去除括号后，由于括号内的+、-要变号， 结果不与原式等价；、假设右邻括号的运算符为*或/，而op为+或-，原式中的op运算必需优先进展，因

16、此括号不能去除，即(s1+-s2)*/；、除上述状况外，括号去除，结果与原式等价，即s1 op s2。我们从最里层嵌套的括号开始，根据上述规律逐步向外层进展括号整理，直至最外层的括号保存或去除为止。这个整理过程可以用下述的一个递归过程reduce描绘：function reduce(表达式串s,var op):string; 整理表达式s,并返回s串中优先级最低的运算符op与整理结果 beginif s是变量 thenbeginop= ; reduce=变量s; exitend;if s是(s)形式 thenbeginreduce=reduce(s,op); exitend; s是s1 op

17、s2 形式 a=reduce(s1,c1);b=reduce(s2,c2);if (op in *,-) and (c2 in +,-) then s2=(s2);if (op in *,/) and (c1 in +,-) then s1=(s1);if (op in /) and (c2 ) then s2=(s2);reduce=s1 op s2end;例如，剔除表达式(a+b)*f)-(i/j)中多余的括号。根据上述算法进展整理的过程如下：(a+b)*f)-(i/j),-(a+b)*f),* (i/j),/ (a+b)*f,* i/j,/ (a+b),+ f, i, j, a+b,+a

18、, b, 图1.1-1最终，自底向上得整理结果：(a+b)*f-i/j。三、程序分析Program P11;varins : string; 算术表达式 p : char; 最低级运算符 function suitable(s:string;i:byte):byte; si为),函数suitable输出与之相对应的(在s中的位置 vart:byte;begint:=1;repeatdec(i);if si=)then inc(t)else if si=( then dec(t)until t=0;suitable:=iend; suitablefunction find(s:string):b

19、yte; 输出表达式s中最低级算符的位置 vari,k:byte;begini:=length(s);k:=0;while i0 dobeginif (si=+) or (si=-)then beginfind:=i;exitend; thenif (k=0) and (si=*) or (si=/) then k:=i;if si=) then i:=suitable(s,i);dec(i)end; whilefind:=kend; findfunction reduce(s:string;var p:char):string; 整理表达式s并返回优先级最低的运算符p vara,b:stri

20、ng; 表达式s的左项与右项整理的结果 c1,c2:char; 表达式s的左项与右项的最低级运算符 i:byte; 表达式s的最低级运算符的位置 beginif length(s)=1 假设表达式是变量那么返回变量 then beginreduce:=s;p:= ;exitend; thenif (slength(s)=) and (suitable(s,length(s)=1) 假设表达式被一对括号包住,那么返回括号内表达式的整理结果 then beginreduce:=reduce(copy(s,2,length(s)-2),p);exitend; theni:=find(s);p:=si

21、; 找出最低级运算符及其位置 a:=reduce(copy(s,1,i-1),c1); 分别整理左项与右项 b:=reduce(copy(s,i+1,length(s)-i),c2); 根据p与c1,c2,确定是否加括号 if (p in *,-) and (c2 in +,-) then b:=(+b+);if (p in *,-) and (c1 in +,-) then a:=(+a+);if (p=/) and (c2 ) then b:=(+b+);reduce:=a+p+b 返回整理结果 end; reducebeginwrite(Str = );readln(ins); 输入算术表达式 writeln(reduce(ins,p) 剔除多余括号并打印整理结果 end. main第 20 页