NOIP2011普及组复赛试题+源程序.docx

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,000 & N< 1,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 s[1]='-' thenbeginwrite('-');k:=2;end;p:=true;;for i:=l downto k dobeginif(p)and((s[i]='0')) then continue elsebeginwrite(s[i]);p:=false;;end;end;close(input); close(output);end.【法二】数字处理Var f:integer;n,ans:longint;beginassign(input, 'reverse.in'); reset(input);rewrite(output);assign(output, 'reverse.out');readln(n);if n<0 thenbeginf:=-1;n:=-n;endelsef:=1;ans:=0;while n<>0 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）【问题描述】一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统 计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置 注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例 1）,如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例 2）【输入】输入文件名为 stat.in, 2行第1行为一个字符串，其中只含字母，表示给定单词；第2行为一个字符串，其中只可能包含字母和空格，表示给定的文章输出】 输出文件名为 stat.outo只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从 0开始）；如果单词在文章中没有出现，则直接输出一个整数 -1输入输出样例1】stat.instat.outToto be or not to be is a question2 0【输入输出样例1解释】输出结果表示给定的单词 To在文章中出现两次，第一次出现的位置为 0输入输出样例2】stat.instat.outtoDid the Ottoman Empire lose its power at that time-1【输入输出样例2解释】表示给定白^单词 to在文章中没有出现，输出整数 -1。

数据范围】1W单词长度w 101W 文章长度 W 1,000,000解题】这道题也不是很难，program stat;var I,n,p:longint;s,s1:string;c:char;beginassign(input,'stat.in'); reset(input);assign(output,'stat.out'); rewrite(output);readln(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=' ' then 〃遇到空格，匹配是否相同beginif s=s1 then begin n:=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 then p:=i-length(s) +1; 〃最后没有空格end;if n=0 then writeln(-1) else writeln(n,' ',p);close(input);close(output);end.3 . 瑞士轮(swiss.cpp/c/pas)【背景】在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。

前 者的特点是比赛场数少，每场都紧张刺激，但偶然性较高后者的特点是较为公平，偶然性较低，但比赛 过程往往十分冗长本题中介绍的瑞士轮赛制，因最早使用于 1895年在瑞士举办的国际象棋比赛而得名它可以看作 是淘汰赛与循环赛的折衷，既保证了比赛的稳定性，又能使赛程不至于过长问题描述】2*N名编号为1~2N的选手共进行 R轮比赛每轮比赛开始前，以及所有比赛结束后，都会按照总 分从高到低对选手进行一次排名选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分 和总分相同的，约定编号较小的选手排名靠前每轮比赛的对阵安排与该轮比赛开始前的排名有关：第 1名和第2名、第3名和第4名、，，、第2K - 1名和第2K名、“ 、第2N - 1名和第2N名，各进行一场比赛每场比赛胜者得 1分，负者彳# 0分也就是说除了首轮以外，其它轮比赛的安排均不能事先确定， 而是要取决于选手在之前比赛中的表现现给定每个选手的初始分数及其实力值，试计算在 R轮比赛过后，排名第 Q的选手编号是多少我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜输入】输入文件名为 swiss.in 输入的第一行是三个正整数 N、R、Q,每两个数之间用一个空格隔开，表示有 2*N名选手、R轮比赛，以及我们关心的名次 Q。

第二行是2*N个非负整数si,第…，Sn,每两个数之间用一个空格隔开，其中 si表示编号为i的选手NOIP2011 普及组 复赛 的初始分数第三行是2*N个正整数W1, W2,…，WN,每两个数之间用一个空格隔开， 其中wi表示编号为i的选手的实力值输出】输出文件名为 swiss.out 输出只有一行，包含一个整数，即 R轮比赛结束后，排名第 Q的选手的编号输入输出样例】swiss.inswiss.out2 4 217 6 6 710520 15【输入输出样例说明】本轮对阵本轮结束后的得分选手编号/①②③④初始/7667第1轮①一④②一③7678第2轮④一①③一②7689第3轮④一③①一②8699第4轮③一④①一②96109【数据范围】对于30%的数据，1WNW100；对于50%的数据，1WNW 10,000；对于 100% 的数据，1WNW100Q00, 1WRW50, 1WQW2N, 0W s1, S2,…，SN < 108 , K w1,w2,…，w8工 10解题】 题目虽然长，但理解题意后就发现解题的瓶颈在于排序如果每一轮比赛的结果都进行快速排序，时间复杂度为 O (Rlongn )，但事实证明这样只能拿 60分。

如彳si AC,这需要一个巧算法：分析得知，快速排序实际上进行了许多无用的工作：如果两个人在第i轮都赢了，那么第i轮后的先后关系与第i-1轮是一样的；反之，如果两人都输了， 他们的先后关系也不会变所以，我们有一个新算法：一开始做一趟快速排序，然后对于每一轮，将此轮的 n个赢者(他们的先后关系和上一轮不变)和 n个输者(他们的先后关系和上一轮也不变分开，然后就是归并，于是时间复杂 度Rn)(实践证明，如果单纯的排序 r次，必然结果是超时事实上只需一次真正意义上的排序以后，在以 后的比赛中，按原顺序分成两组，获胜组和失败组，这两组依然是有序的，再把这两组归并成一组，就可 以了总时间复杂度 O(N*R))program swiss;var a,b,v:array[1..200000]of longint;c,d:array[1..100000,1..2]of 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 (a[i]>mid1) or (a[i]=mid1) and (v[i]mid2) do dec(j); if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t;t:=v[i]; v[i]:=v[j]; v[j]:=t;inc(i); dec(j);end;until i>j;if i