NOIP2011普及组复赛(试题源程序)

1、NOIP2011 普及组 复赛1 .数字反转(reverse.cpp/c/pas )【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给 定的原数为零，否则反转后得到的新数的最高位数字不应为零。(参见样例2)【输入】输入文件名为 reverse. in 。输入共一行，一个整数 No【输出】输出文件名为 reverse.out 。输出共1行，一个整数，表示反转后的新数。【输入输出样例1】reverse.inreverse.out123321【输入输出样例2】reverse.inreverse.out-380-83【数据范围】-1,000,000,0

2、00 N 1,000,000,000 。-0 ,【解题】 这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题(以及 但测试数据没出)。【法一】字符串处理Var i,l,k:i nteger;s:stri ng;p:boolea n;beginassig n(i nput, reverse.i n);reset(i nput);assig n(o utput, reverse.out);rewrite(output);readl n( s);l:=le ngth(s);k:=1;if s1= - the nbeginwrite(-);k:=2;en d;p:=true;f

3、or i:=l dow nto k dobeginif(p)a nd(si=0) the n continueelsebeginwrite(si); p:=false;en d;en d;close(i nput);close(output);en d.【法二】数字处理Var f:i nteger;n,an s:lo ngint;beginassig n(i nput, reverse.i n);reset(i nput);rewrite(output);assig n(o utput, reverse.out); readl n(n);if n0 the nbegin f:=-1; n :=

4、-n;endelsef:=1;an s:=0;while n0 dobeginan s:=a ns*10+n mod 10; n:=n div 10;en d;an s:=a ns*f;writel n(a ns);close(i nput); close(output); en d.2. 统计单词数（stat.pas/c/cpp）【问题描述】一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统 计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数 和第一次出现的位置。注意：匹配单词时，不区

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

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

7、, p:l ongint;s,s1:stri ng; c:char;beginassig n(i nput,stat.i n);reset(i nput);assig n(o utput,stat.out);rewrite(output);readl n( 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;if c

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

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

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

11、两个数之间用一个空格隔开，表示有 2*N名选手、R轮比赛，以及我们关心的名次 Q。第二行是2*N个非负整数S1, S2,sn，每两个数之间用一个空格隔开，其中s表示编号为i的选手 的初始分数。第三行是2*N个正整数W1, W2，,WN ,每两个数之间用一个空格隔开，其中Wi表示编号为i的选手的实力值。【输出】输出文件名为 swiss.out 。输出只有一行，包含一个整数，即R轮比赛结束后，排名第 Q的选手的编号。【输入输出样例】swiss.i nswiss.out2 4 217 6 6 710520 15【输入输出样例说明】本轮对阵本轮结束后的得分选手编号/初始/7667第1轮一一7678第2

12、轮一一7689第3轮一一8699第4轮一一96109【数据范围】对于30%的数据，1 N 100;对于50%的数据，1 N 10,000;对于 100%的数据，1 N 100,000, K R 50, K Q 2N, 0 S1, S2,sn mid1) or (ai=mid1) and (vimid2) do in c(i);while (ajmid2) do dec(j);if ij;if ir the n qsort(i,r);if ldl2,1)or (cl1,1=dl2,1)a nd(cl1,2 n)or(l2 n);while l1=n dobegini:=i+1;ai：=cl1,1

13、;vi:=cl1,2;11:=11+1;en d;while l2bv2*j then beginin c(a2*j-1);cj,1:=a2*j-1;cj,2:=v2*j-1;dj,1:=a2*j;dj,2:=v2*j;end/数组a保存初始分数数组b保存实力值数组vi保存排名第i的选手编号数组cj,1保存嬴方的总分；数组数组dj,1保存输方的总分；数组cj,2保存嬴方的号码;dj,2保存输方的号码；elsebeginin c(a2*j); cj,1：=a2*j; cj,2:=v2*j; dj,1:=a2*j-1; dj,2:=v2*j-1; en d;mergesort;en d;write

14、l n(vq);close(i nput);close(output); en d.4. 表达式的值（exp.cpp/c/pas）【问题描述】对于1位二进制变量定义两种运算：运算符运算规则0 0=00 1=11 0=11 1=1X0 X 0=0 0 X 1=0 1 X 0=01 X 1=1运算的优先级是：1. 先计算括号内的，再计算括号外的。2. “X”运算优先于“”运算 ，即计算表达式时，先计算X运算，再计算运算。例如：计算表达式 A B X C时，先计算B X C,其结果再与 A做运算。现给定一个未完成的表达式，例如_+（_*_），请你在横线处填入数字 0或者1,请问有多少种填法可以使得表

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

16、（0、1、0）、（0、0、1）时，表达式的值均为 0,所以共有3种填法。 【数据范围】对于 20%的数据有0 L 10。对于 50%的数据有0 L 1,000。对于 70%的数据有0 L 10,000。对于100%的数据有0 LW 100,000。对于50%的数据输入表达式中不含括号。【解题】f(s,0)表示表达式s为0的方案数，f(s,1)表示表算法类似于表达式计算，一个符号栈，两个数据栈。记 达式s为1的方案数。f(a+b,O) = f(a,O)*f(b,O)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,

17、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; constmax n= 100010;op:array1.4 of char = (,+,*,);flag:array1.4,1.4 of char =( ( + (,), * (,), ) (,);/符号优先级表varstack_op:array1.max n of char;stack_data0, stack_data1:array1.max n of longint; n ,top_op, top_data, i, le n:

18、l ongint;a0, a1, b0, b1, t0, t1:lo ngint;s: ansistring ;ch,no w:char;procedure push_op(ch:char);运算符压栈beginin c(top_op); stack_optop_op:=ch;en d;function pop_op:char;/ 运算符出栈beginpop_op:= stack_optop_op;dec(top_op);en d;fun ctio n gettop:char;取栈顶符号begingettop:=stack_optop_op;en d;procedure push_data(a

19、0,a1:lo ngi nt);数据压栈beginin c(top_data);stack_data0top_data:=a0; stack_data1top_data:=a1;en d;procedure pop_data(vara0,a1:lo ngin t);数据出栈begina0:=stack_data0top_data;a1:=stack_data1top_data;dec(top_data);en d;function fin d(ch:char):i nteger;/ 读入符号vari:l ongint;beginfor i:= 1 to 4 doif opi=ch the n exit(i);end;beginassig n(i nput,exp.i n);reset(i nput);assig n(o utput,exp.out);rewrite(output);top_op:=0;top_data:=0;/ top_op运算符栈顶指针；top_data 数据栈顶指针push_op();