NOIP-2011普及组复赛(试题+源程序).doc

1、NOIP2011 普及组 复赛NOIP2011 普 复赛8-1NOIP2011 普及组 复赛1数字反转（reverse.cpp/c/pas）【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零。 （参见样例 2）【输入】输入文件名为 reverse.in。输入共一行，一个整数 N。【输出】输出文件名为 reverse.out。输出共 1 行，一个整数，表示反转后的新数。【输入输出样例 1】reverse.in reverse.out123 321【输入输出样例 2】reverse.in rev

2、erse.out-380 -83【数据范围】-1,000,000,000N1,000,000,000。【解题】这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题（以及-0，但测试数据没出） 。【法一】字符串处理Var i,l,k:integer;s:string;p:boolean;beginassign(input, reverse.in); reset(input);assign(output, reverse.out); rewrite(output);readln(s);l:=length(s);k:=1;if s1=- then beginwrite(-);k

3、:=2;end;p:=true;for i:=l downto k do beginif(p)and(si=0) then continueelsebeginwrite(si);p:=false;end;end;close(input); close(output);end.【法二】数字处理Var f:integer;n,ans:longint;beginassign(input, reverse.in); reset(input);NOIP2011 普及组 复赛NOIP2011 普 复赛8-2assign(output, reverse.out); rewrite(output);readl

4、n(n);if n0 dobeginans:=ans*10+n mod 10;n:=n div 10;end;ans:=ans*f;writeln(ans);close(input); close(output);end.2.统计单词数(stat.pas/c/cpp)【问题描述】一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分

5、大小写的情况下完全相同（参见样例 1） ，如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例 2）【输入】输入文件名为 stat.in，2 行。第 1 行为一个字符串，其中只含字母，表示给定单词；第 2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。【输出】输出文件名为 stat.out。只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从 0 开始） ；如果单词在文章中没有出现，则直接输出一个整数-1。【输入输出样例 1】stat.in sta

6、t.outToto be or not to be is a question2 0【输入输出样例 1 解释】输出结果表示给定的单词 To 在文章中出现两次，第一次出现的位置为 0。【输入输出样例 2】stat.in stat.outtoDid the Ottoman Empire lose its power at that time-1【输入输出样例 2 解释】表示给定的单词 to 在文章中没有出现，输出整数 -1。【数据范围】1单词长度10。1文章长度1,000,000。【解题】这道题也不是很难，program stat;var I,n,p:longint;s,s1:string;c:c

7、har;beginassign(input,stat.in); reset(input);assign(output,stat.out); rewrite(output);NOIP2011 普及组 复赛NOIP2011 普 复赛8-3readln(s);s:=upcase(s); / 函数 upcase()参数可为 char，也可为 stringi:=-1; /i 统计读入的字符位置，首个字符出现的位置是 0s1:=; /s1 累加读入的字符n:=0; /n 统计出现次数p:=-1; /p 标记第一次出现的位置repeatread(c);c:=upcase(c); /统一大小写i:=i+1;

8、if c= then /遇到空格，匹配是否相同beginif s=s1 thenbeginn:=n+1;if p=-1 then /p 标记第一次出现的位置，如果 p 是第一次更改，记录位置p:=i-length(s);end;s1:=;endelses1:=s1+c; /不是空格，继续叠加until eoln(input);if s1=s then /处理最后一个单词是否相同的情况beginn:=n+1;if p=-1 thenp:=i-length(s)+1; /最后没有空格end;if n=0 then writeln(-1)else writeln(n, ,p);close(input

9、);close(output);end.3. 瑞士轮(swiss.cpp/c/pas)【背景】在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。本题中介绍的瑞士轮赛制，因最早使用于 1895 年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折衷，既保证了比赛的稳定性，又能使赛程不至于过长。【问题描述】2*N 名编号为 12N 的选手共进行 R 轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分

10、为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。每轮比赛的对阵安排与该轮比赛开始前的排名有关：第 1 名和第 2 名、第 3 名和第 4 名、第 2K1 名和第 2K 名、 、第 2N1 名和第 2N 名，各进行一场比赛。每场比赛胜者得 1 分，负者得 0 分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。现给定每个选手的初始分数及其实力值，试计算在 R 轮比赛过后，排名第 Q 的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。【输入】输入文件名为 swiss.in 。输

11、入的第一行是三个正整数 N 、R、Q，每两个数之间用一个空格隔开，表示有2*N 名选手、R 轮比赛，以及我们关心的名次Q 。第二行是 2*N 个非负整数s1, s2, , s2N，每两个数之间用一个空格隔开，其中si 表示编号为i 的选NOIP2011 普及组 复赛NOIP2011 普 复赛8-4手的初始分数。第三行是 2*N 个正整数w1, w2, , w2N，每两个数之间用一个空格隔开，其中wi 表示编号为i 的选手的实力值。【输出】输出文件名为 swiss.out。输出只有一行，包含一个整数，即 R 轮比赛结束后，排名第 Q 的选手的编号。【输入输出样例】swiss.in swiss.o

12、ut2 4 27 6 6 710 5 20 151【输入输出样例说明】本轮对阵 本轮结束后的得分选手编号 / 初始 / 7 6 6 7第 1 轮 7 6 7 8第 2 轮 7 6 8 9第 3 轮 8 6 9 9第 4 轮 9 6 10 9【数据范围】 对于 30%的数据，1N100；对于 50%的数据，1N10,000；对于 100%的数据，1N100,000，1R 50，1Q 2N，0s1, s2, , s2N ，1w 1,w2, , 80w2N 。80【解题】题目虽然长，但理解题意后就发现解题的瓶颈在于排序。如果每一轮比赛的结果都进行快速排序，时间复杂度为 O（Rlongn） ，但事实证

13、明这样只能拿 60 分。如何 AC，这需要一个巧算法：分析得知，快速排序实际上进行了许多无用的工作：如果两个人在第 i 轮都赢了，那么第 i 轮后的先后关系与第 i-1 轮是一样的；反之，如果两人都输了，他们的先后关系也不会变。所以，我们有一个新算法：一开始做一趟快速排序，然后对于每一轮，将此轮的 n 个赢者（他们的先后关系和上一轮不变）和 n 个输者（他们的先后关系和上一轮也不变分开，然后就是归并，于是时间复杂度 O（Rn） ）（实践证明，如果单纯的排序 r 次，必然结果是超时。事实上只需一次真正意义上的排序以后，在以后的比赛中，按原顺序分成两组，获胜组和失败组，这两组依然是有序的，再把这两

14、组归并成一组，就可以了。总时间复杂度 O(N*R) ）program swiss;var a,b,v:array1.200000of longint; c,d:array1.100000,1.2of longint;n,r,q,i,j:longint;procedure qsort(l,r:longint);var i,j,mid1,mid2,t:longint;begini:=l;j:=r; mid1:=a(l+r)div 2; mid2:=v(l+r)div 2;repeat /按分数从高到低排序，分数相同的，编号较小的选手排名靠前while (aimid1) or (ai=mid1) a

15、nd (vimid2) do dec(j);if ij;if idl2,1)or (cl1,1=dl2,1)and(cl1,2n)or(l2n);while l1bv2*j thenbegininc(a2*j-1);cj,1:=a2*j-1; /数组 cj,1保存嬴方的总分；数组 cj,2保存嬴方的号码；cj,2:=v2*j-1;dj,1:=a2*j; /数组 dj,1保存输方的总分；数组 dj,2保存输方的号码；dj,2:=v2*j;endNOIP2011 普及组 复赛NOIP2011 普 复赛8-6elsebegininc(a2*j);cj,1:=a2*j;cj,2:=v2*j;dj,1:

16、=a2*j-1;dj,2:=v2*j-1;end;mergesort;end;writeln(vq);close(input);close(output);end.4. 表达式的值(exp.cpp/c/pas)【问题描述】对于 1 位二进制变量定义两种运算：运算符 运算规则 00=001=110=111=1 0 0=00 1=01 0=01 1=1运算的优先级是：1. 先计算括号内的，再计算括号外的。2. “”运算优先于“”运算，即计算表达式时，先计算运算，再计算运算。例如：计算表达式AB C 时，先计算B C，其结果再与A 做运算。现给定一个未完成的表达式，例如_+(_*_)，请你在横线处填

17、入数字0 或者1，请问有多少种填法可以使得表达式的值为0。【输入】输入文件名为 exp.in，共2 行。第 1 行为一个整数L，表示给定的表达式中除去横线外的运算符和括号的个数。第 2 行为一个字符串包含L 个字符，其中只包含（ 、）、+、*这4 种字符，其中（、）是左右括号，+、*分别表示前面定义的运算符“”和“”。这行字符按顺序给出了给定表达式中除去变量外的运算符和括号。【输出】输出文件 exp.out 共1 行。包含一个整数，即所有的方案数。注意：这个数可能会很大，请输出方案数对 10007 取模后的结果。【输入输出样例 1】exp.in exp.out4+(*)3【输入输出样例说明】

18、给定的表达式包括横线字符之后为：_+(_*_)在横线位置填入(0、0 、0)、(0、1、0)、(0、0、1)时，表达式的值均为0，所以共有3种填法。【数据范围】 对于 20%的数据有0L10 。对于 50%的数据有0L1,000 。对于 70%的数据有0L10,000 。对于 100%的数据有0L100,000 。对于 50%的数据输入表达式中不含括号。NOIP2011 普及组 复赛NOIP2011 普 复赛8-7【解题】算法类似于表达式计算，一个符号栈，两个数据栈。记 f(s,0)表示表达式 s 为 0 的方案数，f(s,1) 表示表达式 s 为 1 的方案数。f(a+b,0) = f(a,

19、0)*f(b,0) f(a+b,1) = f(a,0)*f(b,0)+f(a,0)*f(b,1)+f(a,1)*f(b,0) f(a*b,0)=f(a,0)*f(b,0) + f(a,1)*f(b,0) + f(a,0)*f(b,1) f(a*b,1) = f(a,1) * f(b,1)program exp;const maxn= 100010;op:array1.4 of char = (,+,*,);flag:array1.4,1.4 of char = ( ( (,), * (,), ) (,) ); /符号优先级表var stack_op:array1.maxn of char;st

20、ack_data0, stack_data1:array1.maxn of longint;n,top_op, top_data, i, len:longint;a0, a1, b0, b1, t0, t1:longint;s:ansistring;ch,now:char;procedure push_op(ch:char); /运算符压栈begininc(top_op);stack_optop_op:=ch;end;function pop_op:char; /运算符出栈beginpop_op:= stack_optop_op;dec(top_op);end;function gettop:

21、char; /取栈顶符号begingettop:=stack_optop_op;end;procedure push_data(a0,a1:longint); /数据压栈begininc(top_data);stack_data0top_data:=a0;stack_data1top_data:=a1;end;procedure pop_data(var a0,a1:longint); /数据出栈begina0:=stack_data0top_data;a1:=stack_data1top_data;dec(top_data);end;function find(ch:char):intege

22、r; /读入符号var i:longint;beginfor i:= 1 to 4 doif opi=ch then exit(i);end;NOIP2011 普及组 复赛NOIP2011 普 复赛8-8beginassign(input,exp.in); reset(input);assign(output,exp.out); rewrite(output);top_op:=0; top_data:=0; / top_op 运算符栈顶指针； top_data 数据栈顶指针push_op(); push_data(1,1); / 压栈readln(n); readln(s); s:=s+);l

23、en:=length(s);i:=1;while i() then push_data(1,1); /数据出栈inc(i); end;=: begin now:=pop_op; inc(i); end;: beginpop_data(a0,a1); pop_data(b0,b1);now:=pop_op;if now=+ thenbegint0:= (a0*b0) mod 10007;t1:= (a0*b1) mod 10007+(a1*b1) mod 10007+ (a1*b0) mod 10007) mod 10007;push_data(t0,t1);endelsebegint0:= (a0*b1) mod 10007 + (a1*b0) mod 10007 + (a0*b0) mod 10007 ) mod 10007;t1:= (a1*b1) mod 10007;push_data(t0,t1);end;end;end;end;writeln(stack_data0top_data);close(input); close(output);end.