当前位置:首页 >> 学科竞赛 >>

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

NOIP2011 普及组 复赛

NOIP2011

普及组

复赛

1.数字反转(reverse.cpp/c/pas)
【问题描述】 给定一个整数,请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式,即除非给 定的原数为零,否则反转后得到的新数的最高位数字不应为零。 (参见样例 2) 【输入】 输入文件名为 reverse.in。 输入共一行,一个整数 N。 【输出】 输出文件名为 reverse.out。 输出共 1 行,一个整数,表示反转后的新数。 【输入输出样例 1】 reverse.in reverse.out 123 321 【输入输出样例 2】 reverse.in reverse.out -380 -83 【数据范围】 -1,000,000,000≤N≤1,000,000,000。 【解题】这道题非常简单,可以读字符串处理,也可以读数字来处理,只不过要注意符号问题(以及-0, 但测试数据没出) 。 【法一】字符串处理 Var i,l,k:integer; s:string; p:boolean; begin assign(input, 'reverse.in'); reset(input); assign(output, 'reverse.out'); rewrite(output); readln(s); l:=length(s); k:=1; if s[1]='-' then begin write('-'); k:=2; end; p:=true;; for i:=l downto k do begin if(p)and((s[i]='0')) then continue else begin write(s[i]); p:=false;; end; end; close(input); close(output); end. 【法二】数字处理 Var f:integer; n,ans:longint; begin assign(input, 'reverse.in');

reset(input);
NOIP2011 普 复赛—8-1

NOIP2011 普及组 复赛 assign(output, 'reverse.out'); rewrite(output); readln(n); if n<0 then begin f:=-1; n:=-n; end else f:=1; ans:=0; while n<>0 do begin ans:=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.out。 只有一行,如果在文章中找到给定单词则输出两个整数,两个整数之间用一个空格隔开, 分别是单词在文章中出现的次数和第一次出现的位置(即在文章中第一次出现时,单词首字 母在文章中的位置,位置从 0 开始) ;如果单词在文章中没有出现,则直接输出一个整数-1。 【输入输出样例 1】 stat.in stat.out To 2 0 to be or not to be is a question 【输入输出样例 1 解释】 输出结果表示给定的单词 To 在文章中出现两次,第一次出现的位置为 0。 【输入输出样例 2】 stat.in stat.out to -1 Did the Ottoman Empire lose its power at that time 【输入输出样例 2 解释】 表示给定的单词 to 在文章中没有出现,输出整数-1。 【数据范围】1≤单词长度≤10。 1≤文章长度≤1,000,000。 【解题】这道题也不是很难, program stat; var I,n,p:longint; s,s1:string; c:char; begin assign(input,'stat.in'); reset(input); assign(output,'stat.out'); rewrite(output);
NOIP2011 普 复赛—8-2

NOIP2011 普及组 复赛 readln(s); s:=upcase(s); // 函数 upcase()参数可为 char,也可为 string i:=-1; //i 统计读入的字符位置,首个字符出现的位置是 0 s1:=''; //s1 累加读入的字符 n:=0; //n 统计出现次数 p:=-1; //p 标记第一次出现的位置 repeat read(c); c:=upcase(c); //统一大小写 i:=i+1; if c=' ' then //遇到空格,匹配是否相同 begin if s=s1 then begin n:=n+1; if p=-1 then //p 标记第一次出现的位置,如果 p 是第一次更改,记录位置 p:=i-length(s); end; s1:=''; end else s1:=s1+c; //不是空格,继续叠加 until eoln(input); if s1=s then //处理最后一个单词是否相同的情况 begin n:=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 个非负整数s1, s2, …, s2N,每两个数之间用一个空格隔开,其中si 表示编号为i 的选手
NOIP2011 普 复赛—8-3

NOIP2011 普及组 复赛 的初始分数。 第三行是 2*N 个正整数w1, w2, …, w2N, 每两个数之间用一个空格隔开, 其中wi 表示编号为i 的选手 的实力值。 【输出】 输出文件名为 swiss.out。 输出只有一行,包含一个整数,即 R 轮比赛结束后,排名第 Q 的选手的编号。 【输入输出样例】 swiss.in swiss.out 2 4 2 1 7 6 6 7 10 5 20 15 【输入输出样例说明】 本轮对阵 本轮结束后的得分 / 选手编号 ① ② ③ ④ / 7 6 6 7 初始 7 6 7 8 第1轮 ①—④ ②—③ 7 6 8 9 第2轮 ④—① ③—② 8 6 9 9 第3 轮 ④—③ ①—② 9 6 10 9 第4 轮 ③—④ ①—② 【数据范围】 对于 30%的数据,1≤N≤100; 对于 50%的数据,1≤N≤10,000; 对于 100%的数据, 1≤N≤100,000, 1≤R≤50, 1≤Q≤2N, 0≤s1, s2, …, s2N ≤ 10 , 1≤w1,w2, …, w2N ≤ 10 。 【解题】题目虽然长,但理解题意后就发现解题的瓶颈在于排序。 如果每一轮比赛的结果都进行快速排序,时间复杂度为 O(Rlongn) ,但事实证明这样只能拿 60 分。 如何 AC,这需要一个巧算法:分析得知,快速排序实际上进行了许多无用的工作: 如果两个人在第 i 轮都赢了,那么第 i 轮后的先后关系与第 i-1 轮是一样的;反之,如果两人都输了, 他们的先后关系也不会变。 所以,我们有一个新算法:一开始做一趟快速排序,然后对于每一轮,将此轮的 n 个赢者(他们的先 后关系和上一轮不变)和 n 个输者(他们的先后关系和上一轮也不变分开,然后就是归并,于是时间复杂 度 O(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; begin i:=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 inc(i); while (a[j]<mid1) or (a[j]=mid1) and (v[j]>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<r then qsort(i,r);
NOIP2011 普 复赛—8-4
8

8

NOIP2011 普及组 复赛 if l<j then qsort(l,j); end; procedure mergesort; //归并排序 var i,l1,l2:longint; begin i:=0; l1:=1; l2:=1; repeat if (c[l1,1]>d[l2,1])or (c[l1,1]=d[l2,1])and(c[l1,2]<d[l2,2]) then begin i:=i+1; a[i]:=c[l1,1]; v[i]:=c[l1,2]; l1:=l1+1; end else begin i:=i+1; a[i]:=d[l2,1]; v[i]:=d[l2,2]; l2:=l2+1; end; until (l1>n)or(l2>n); while l1<=n do begin i:=i+1; a[i]:=c[l1,1]; v[i]:=c[l1,2]; l1:=l1+1; end; while l2<=n do begin i:=i+1; a[i]:=d[l2,1]; v[i]:=d[l2,2]; l2:=l2+1; end; end; begin //主程序 assign(input,'swiss.in');reset(input); assign(output,'swiss.out');rewrite(output); readln(n,r,q); for i:= 1 to n*2 do read(a[i]); //数组 a 保存初始分数 for i:= 1 to n*2 do read(b[i]); //数组 b 保存实力值 for i:=1 to n*2 do v[i]:=i; //数组 v[i]保存排名第 i 的选手编号 qsort(1,2*n); for i:= 1 to r do begin for j:= 1 to n do if b[v[2*j-1]]>b[v[2*j]] then begin inc(a[2*j-1]); c[j,1]:=a[2*j-1]; //数组 c[j,1]保存嬴方的总分;数组 c[j,2]保存嬴方的号码; c[j,2]:=v[2*j-1]; d[j,1]:=a[2*j]; //数组 d[j,1]保存输方的总分;数组 d[j,2]保存输方的号码; d[j,2]:=v[2*j]; end
NOIP2011 普 复赛—8-5

NOIP2011 普及组 复赛 else begin inc(a[2*j]); c[j,1]:=a[2*j]; c[j,2]:=v[2*j]; d[j,1]:=a[2*j-1]; d[j,2]:=v[2*j-1]; end; mergesort; end; writeln(v[q]); close(input);close(output); end.

4. 表达式的值(exp.cpp/c/pas)
【问题描述】 对于 1 位二进制变量定义两种运算: 运算符



×

运算规则 0⊕0=0 0⊕1=1 1⊕0=1 1⊕1=1 0 × 0=0 0 × 1=0 1 × 0=0 1 × 1=1

运算的优先级是: 1. 先计算括号内的,再计算括号外的。 2. “×”运算优先于“⊕”运算,即计算表达式时,先计算×运算,再计算⊕运算。 例如:计算表达式A⊕B × C 时,先计算B × C,其结果再与A 做⊕运算。 现给定一个未完成的表达式,例如_+(_*_),请你在横线处填入数字0 或者1,请问有多少种填法可以 使得表达式的值为0。 【输入】 输入文件名为 exp.in,共2 行。 第 1 行为一个整数L,表示给定的表达式中除去横线外的运算符和括号的个数。 第 2 行为一个字符串包含L 个字符,其中只包含’(’、’)’、’+’、’*’这4 种字符,其中’ (’、’)’是左右括号,’+’、’*’分别表示前面定义的运算符“⊕”和“×”。这行字符按顺序 给出了给定表达式中除去变量外的运算符和括号。 【输出】 输出文件 exp.out 共1 行。包含一个整数,即所有的方案数。注意:这个数可能会很大, 请输出方案数对 10007 取模后的结果。 【输入输出样例 1】 exp.in exp.out 4 3 +(*) 【输入输出样例说明】 给定的表达式包括横线字符之后为:_+(_*_) 在横线位置填入(0、0、0)、(0、1、0)、(0、0、1)时,表达式的值均为0,所以共有3种填法。 【数据范围】 对于 20%的数据有0≤L≤10。 对于 50%的数据有0≤L≤1,000。 对于 70%的数据有0≤L≤10,000。 对于 100%的数据有0≤L≤100,000。 对于 50%的数据输入表达式中不含括号。
NOIP2011 普 复赛—8-6

NOIP2011 普及组 复赛 【解题】 算法类似于表达式计算,一个符号栈,两个数据栈。记 f(s,0)表示表达式 s 为 0 的方案数,f(s,1)表示表 达式 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) program exp; const maxn= 100010; op:array[1..4] of char = ('(','+','*',')'); flag:array[1..4,1..4] of char = ( { ( } ('<','<','<','='), {+} ('<','>','<','>'), {*} ('<','>','>','>'), {)} ('>','>','>','>') var stack_op:array[1..maxn] of char; stack_data0, stack_data1:array[1..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); begin inc(top_op); stack_op[top_op]:=ch; end; function pop_op:char; begin pop_op:= stack_op[top_op]; dec(top_op); end; function gettop:char; begin gettop:=stack_op[top_op]; end; //运算符压栈

);

//符号优先级表

//运算符出栈

//取栈顶符号

procedure push_data(a0,a1:longint); begin inc(top_data); stack_data0[top_data]:=a0; stack_data1[top_data]:=a1; end; procedure pop_data(var a0,a1:longint); begin a0:=stack_data0[top_data]; a1:=stack_data1[top_data]; dec(top_data); end; function find(ch:char):integer; var i:longint; begin for i:= 1 to 4 do if op[i]=ch then exit(i); end;

//数据压栈

//数据出栈

//读入符号

NOIP2011 普 复赛—8-7

NOIP2011 普及组 复赛 begin assign(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+')'; len:=length(s); i:=1; while i<=len do begin if i=22 then readln; case flag[find(gettop),find(s[i])] of '<': begin push_op(s[i]); //运算符出栈 if (s[i]<>'(') then push_data(1,1); //数据出栈 inc(i); end; '=': begin now:=pop_op; inc(i); end; '>': begin pop_data(a0,a1); pop_data(b0,b1); now:=pop_op; if now='+' then begin t0:= (a0*b0) mod 10007; t1:= ((a0*b1) mod 10007+(a1*b1) mod 10007+ (a1*b0) mod 10007) mod 10007; push_data(t0,t1); end else begin t0:= ((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_data0[top_data]); close(input); close(output); end.

NOIP2011 普 复赛—8-8


相关文章:
NOIP2011普及组初赛试题答案C++
NOIP2011普及组初赛试题答案C++ - 第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组 ●● C++语言 二小时完成 )●● 全部试题答案均要求写在答卷纸上,写...
NOIP2011普及组初赛试题及答案C++版
NOIP2011普及组初赛试题及答案C++版_IT/计算机_专业资料。第十七届全国青少年信息...程序源文件理论上所占的硬盘空间 13.在含有 n 个元素的双向链表中查询是否存在...
NOIP2011普及组解题报告
NOIP2011 普及组解题报告一、数字反转 没得满分只能说明一个问题,你的程序写的...NOIP2016复赛普及组试题 13页 1下载券 NOIP2015普及组复赛试卷 7页 2下载券...
noip 2011 c++题解
noip 2011 c++题解_解决方案_计划/解决方案_应用文书。2011niopc++题解(NOIP2011)普及组复赛 1.数字反转 (reverse.cpp/c/pas) 【问题描述】 给定一个整数,请...
NOIP2011第十七届初赛Pascal普及组试题与答案(Wor...
NOIP2011第十七届初赛Pascal普及组试题与答案(Word)_学科竞赛_初中教育_教育专区...程序源文件理论上所占的硬盘空间 13、在含有 n 个元素的双向链表中查询是否...
Noip2011普及组Pascal初赛题及参考答案
Noip2011普及组Pascal初赛题及参考答案_其它课程_初中教育_教育专区。第十七届...程序运行时理论上所占的硬盘空间 D.程序源文件理论上所占的硬盘空间 13.在...
NOIP2011普及组初赛试题及答案C
NOIP2011普及组初赛试题及答案C_学科竞赛_初中教育_教育专区。NOIP2011 普及组...程序运行时理论上所占的硬盘空间 D.程序源文件理论上所占的硬盘空间 13.在...
NOIP2011初赛普及组C++题目及答案
程序源文件理论上所占的硬盘空间 13.在含有 n 个元素的双向链表中查询是否存在...NOIP2011普及组复赛试题 5页 5下载券 NOIP2011-C普及组试题 13页 5下载券 ...
NOIP2011普及组思维训练题实例
源程序: var i,j,k,t,n,m,c,s:longint; f:array[1..30,1..30]of...noip2011普及组复赛 5页 1下载券 NOIP2011普及组试题 5页 5下载券 NOIP2011...
NOIP2011-C普及组试题
程序源文件理论上所占的硬盘空间 13.在含有 n 个元素的双向链表中查询是否存在...NOIP2011普及组复赛试题 5页 5下载券 NOIP2011普及组初赛试题... 13页 1下载...
更多相关标签: