noip普及组复赛

1、NOIP2011普及组复赛1 .数字反转（c/pas ）【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给 定的原数为零，否则反转后得到的新数的最高位数字不应为零。（参见样例2）【输入】输入文件名为。输入共一行，一个整数No【输出】输出文件名为。-1,000,000,000 N 1,000,000,000 o-0 ,【解题】 这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题(以及 但测试数据没出)。【法一】字符串处理Var i,l,k:i nteger;s:stri ng;p:boolea n;beginassig n

2、(i nput, ”)；reset(i npu t);assig n(output, ); rewrite(out pu t);readl n(s);l:=le ngth(s);k:=1;if s1=- the nbeginwrite(-);k:=2;en d;p:=true;for i:=l dow nto k dobeginif(p)an d(si-0) the n contin ueelsebeginwrite(si);p :=false;en d;en d;close(i npu t); close(out pu t);en d.【法二】数字处理Var f:i nteger;n,an

3、s:lo ngint;beginassig n(i nput, );reset(i npu t);assig n(output, ); rewrite(out pu t);readl n(n);if n0 the nbegin f:=-1; n :=-n; end else f:=1; an s:=0; while n0 do begin an s:=a ns*10+n mod 10; n :=n div 10;en d;an s:=a ns*f;writel n(a ns);close(i npu t); close(out pu t); en d.2.统计单词数c/cpp）【问题描述】一般

4、的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统 计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数 和第一次出现的位置。 注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的 某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例 2）【输入】 输入文件名为，2行。第1行为一个字符串，其中只含字母，表示给定单词；第2行为一个字符串，其中只可能包含字母和空格，表示给定的文章。 【输出】输出文件名为。-1。只有

5、一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开， 分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字 母在文章中的位置，位置从 0开始）；如果单词在文章中没有出现，则直接输出一个整数【输入输出样例1】Toto be or not to be is a questi on2 0toDid the Ottoma n Empire lose its po wer at that time-10。【输入输出样例1解释】输出结果表示给定的单词 To在文章中出现两次，第一次出现的位置为 【输入输出样例2】【输入输出样例2解释】表示给定的单词to在文章

6、中没有出现，输出整数-1。【数据范围】1W单词长度W 10。1W文章长度W 1,000,000 。【解题】这道题也不是很难，P rogram stat;var l,n,p :1 ongint;s,s1:stri ng;c:char;beginassig n(i npu t,);reset(i npu t);assig n(outpu t,); rewrite(out pu t);readl n(s);s:=upcase(s); 3.壬瑞士轮 c/pas)【背景】在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前 者的特点是比赛场数少，每场都紧张刺激，但偶然性

7、较高。后者的特点是较为公平，偶然性较低，但比赛 过程往往十分冗长。本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折衷，既保证了比赛的稳定性，又能使赛程不至于过长。【问题描述】2*N名编号为12N的选手共进行 R轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分 从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分 和。总分相同的，约定编号较小的选手排名靠前。每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1名和第2名、第3名和第4名、第2K- 1名和第2K名、第2N - 1名和第2N名，各进

8、行一场比赛。每场比赛胜者得1分，负者得0分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表 现。现给定每个选手的初始分数及其实力值，试计算在R轮比赛过后，排名第 Q的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。【输入】输入文件名为。输入的第一行是三个正整数 赛，以及我们关心的名次 Q。第二行是2*N 选手的初始分数。第三行是2*N 手的实力值。【输出】输出文件名为 输出只有一行，【输入输出样例】个非负整数S1, s个正整数wi , w 2,。包含一个整数，即R Q,每两个数之间用一个空格隔开，表示有2,S 2N,每两个

9、数之间用一个空格隔开，其中,W 2N,每两个数之间用一个空格隔开，其中R轮比赛结束后，排名第 Q的选手的编号。2*N名选手、R轮比Si表示编号为i的w表示编号为i的选2 4 27 6 6 710520 151【输入输出样例说明】本轮对阵本轮结束后的得分选手编号/初始/7667第1轮一一7678第2轮一一7689第3轮一一8699第4轮一一96109K NW 100; K NW 10,000 ;【数据范围】对于30%的数据，对于50%的数据，对于 100% 的数据，1 W NW 100,000 , 1W RW 50, 1W QW 2N, 0 W si, S2,S2n w 108 , iw wi,

10、w2,8W2N W 10 。【解题】 题目虽然长，但理解题意后就发现解题的瓶颈在于排序。如果每一轮比赛的结果都进行快速排序，时间复杂度为0(Riongn )，但事实证明这样只能拿 60分。如何AC,这需要一个巧算法：分析得知，快速排序实际上进行了许多无用的工作：如果两个人在第i轮都赢了，那么第i轮后的先后关系与第i-1轮是一样的；反之，如果两人都输了， 他们的先后关系也不会变。所以，我们有一个新算法：一开始做一趟快速排序，然后对于每一轮，将此轮的n个赢者(他们的先后关系和上一轮不变)和n个输者(他们的先后关系和上一轮也不变分开，然后就是归并，于是时间复杂度 O (Rn)(实践证明，如果单纯的排

11、序r次，必然结果是超时。事实上只需一次真正意义上的排序以后，在以后的比赛中，按原顺序分成两组，获胜组和失败组，这两组依然是有序的，再把这两组归并成一组，就可 以了。总时间复杂度 O(N*R)p rogram swiss;var a,b,v:array1.200000of longint;c,d:array1.100000,1.2of longint;n ,r,q,i,j:lo ngi nt;p rocedure qsort(l,r:l ongin t);var i,j,mid1,mid2,t:l ongint;begini:=l;j:=r; mid1:=a(l+r)div 2; mid2:=v

12、(l+r)div 2;rep eat4.表达式的值c/pas）运算符运算规则00=001=110=111=1X0X0=00X1=01X0=01X1=1运算的优先级是：1.先计算括号内的，再计算括号外的。【问题描述】对于1位二进制变量定义两种运算:，即计算表达式时，先计算X运算，再计算运算。先计算B X C,其结果再与 A做运算。_+（_*_），请你在横线处填入数字 0或者1,请问有多少种填法可以2.“X”运算优先于“”运算例如：计算表达式 A B X C时， 现给定一个未完成的表达式，例如使得表达式的值为0。【输入】输入文件名为，共2行。第1行为一个整数L,表示给定的表达式中 除去横线外 的运

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

14、 10。50%的数据有 0 LW 1,000。70%的数据有 0 LW 10,000。100%的数据有 0W LW 100,000。50%的数据输入表达式中不含括号。算法类似于表达式计算，一个符号栈，两个数据栈。记 示表达式s为1的方案数。f(a+b,0) = f(a,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)f（s,O）表示表达式s为0的方案数，f（s,1）表program exp;const maxn= 100010;op:array1.4 of char = (,+,*,);flag:array1