NOIP 2011 提高组day1 题解
美少女战士原创
1．铺地毯
(carpet.cpp/c/pas)
【问题描述】
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标
系的第一象限）铺上一些矩形地毯。一共有n 张地毯，编号从1 到n。现在将这些地毯按照
编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形
地毯边界和四个顶点上的点也算被地毯覆盖。
【输入】
输入文件名为 carpet.in。
输入共 n+2 行。
第一行，一个整数 n，表示总共有n 张地毯。
接下来的 n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每
两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x
轴和y 轴方向的长度。
第 n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。
【输出】
输出文件名为 carpet.out。
输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
【输入输出样例 1】
carpet.in carpet.out
3 3
1 0
2 3
0 2 3 3
2 1
3 3
2 2
【输入输出样例说明】
如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2，
2）的最上面一张地毯是3 号地毯。
【输入输出样例 2】
carpet.in carpet.out
3 -1
1 0
2 3
0 2 3 3
2 1
3 3
4 5
【输入输出样例说明】
如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5）
没有被地毯覆盖，所以输出-1。
（不好意思，因为是从PDF中复制过来的，所以没有图，不过挺简单的，大家可以自己做一下）
（嘿嘿，还是我的朋友智慧，我怎么就没想到用ＱＱ截图）
【数据范围】
对于 30%的数据，有n≤2；
对于 50%的数据，0≤a, b, g, k≤100；
对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。
//其实吧，感觉这道题就是送分得(大牛们不要鄙视我）//
刚看到这道题时，会以为是图论，建一个图，然后每输入一次就更改一下图，最后访问图中的一个点
仔细想想，其实完全没有必要嘛，干嘛要改整个图呢，可以把这些都记住，然后只改要求的那一个点，毕竟它只要一个点，然后就有了比较简单的AC方法了
//^^^思想已经在上面了，下面就给出标程吧//
var
ans,i,j,k,n:longint;
x,y,l,r:array[1..10000]of longint;
begin
assign(input,'carpet.in');assign(output,'carpet.out');
reset(input);rewrite(output);
readln(n);
for i:=1 to n do readln(x[i],y[i],l[i],r[i]);
readln(i,j);
ans:=-1;
for k:=1 to n do if
(x[k]<=i)and(x[k]+l[k]>=i)and(y[k]<=j)and(y[k]+r[k]>=j)
then ans:=k;
writeln(ans);
close(input);close(output);
end.
2．选择客栈
(hotel.cpp/c/pas)
【问题描述】
丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从1 到n 编号。每家客栈都按照
某一种色调进行装饰（总共k 种，用整数0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每
家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定
分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于
两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p。他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p
元的咖啡店小聚。
【输入】
输入文件 hotel.in，共n+1 行。
第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色
调的数目和能接受的最低消费的最高值；
接下来的 n 行，第i+1 行两个整数，之间用一个空格隔开，分别表示i 号客栈的装饰色
调和i 号客栈的咖啡店的最低消费。
【输出】
输出文件名为 hotel.out。
输出只有一行，一个整数，表示可选的住宿方案的总数。
【输入输出样例 1】
hotel.in hotel.out
5 2 3 3
0 5
1 3
0 2
1 4
1 5
样例说明
客栈编号① ② ③ ④ ⑤
色调 0 1 0 1 1
最低消费 5 3 2 4 5
2 人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，
④⑤，
但是若选择住4、5 号客栈的话，4、5 号客栈之间的咖啡店的最低消费是4，而两人能承受
的最低消费是3 元，所以不满足要求。因此只有前3 种方案可选。
【数据范围】
对于 30%的数据，有n≤100；
对于 50%的数据，有n≤1,000；
对于 100%的数据，有2≤n≤200,000，0 这道题吧，很容易就能想到一种暴搜方案，二重循环，任意两个旅馆组合，再加一重循环找最小值，判断是否可行，可以想象，N^3的复杂度，最多能过三组，除非实在没办法，才能用这种方法； 那么如何优化呢？显然，在枚举两个旅馆的时候，把这两个旅馆间的都访问过了，所以，我们就可以减一重循环在访问时，顺便记录最小值 //for j:=i+1 to n do if b[j] 这样之后，时间复杂度就降到N^2了（嘿嘿，有点成就感），可是，对于数据来说，我们仍然只能过5组…… 怎么办呢？继续优化吧 注意到最多只有50种颜色，那么我们可以记录每种颜色的旅馆的数量，从前往后一旦搜到有一个同种颜色，那么，之后的同种颜色的旅馆都可行（正确性就不证明了吧），然而，这里又有一个问题，如何知道一个旅馆后有多少个同种颜色的旅馆呢（显然不能搜了，否则就白优化了），所以可以建立一个200000*50 的数组，初始化一下就行，num【i，j】：=num【i+1，j】（color[i]<>j);/num[i+1,j]+1（color[i]=j); //虽然我考试时不是这样做的，用得是一维数组加记录（这里是为了便于大家理解） 这样，平均时间复杂度不到（n*K）这道题就AC了 //下面给出我考试时的AC代码// var n,k,p,i,j,min,ans,l:longint; a,b:array[1..200000]of longint;c:array[0..50]of longint; begin assign(input,'hotel.in');assign(output,'hotel.out'); reset(input);rewrite(output); readln(n,k,p); for i:=1 to n do begin readln(a[i],b[i]);inc(c[a[i]]);end; ／／标注一下，这里记录了同种颜色的旅馆个数／／ for i:=1 to n-1 do begin min:=b[i];dec(c[a[i]]);／／如果搜过，那就减去吧／／l:=c[a[i]]; ／／为了记录剩余的个数，引入的变量／／ for j:=i+1 to n do begin if b[j] if (a[i]=a[j])and(min<=p) then begin inc(ans,l);break;end; if a[i]=a[j] then dec(l); end; end; writeln(ans); close(input);close(output); end. 3．Mayan 游戏 (mayan.cpp/c/pas) 【问题描述】 Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个7 行5 列的棋盘，上面堆放 着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游 戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下： 1、每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方 块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参 见输入输出样例说明中的图6 到图7）；如果目标位置上没有方块，那么被拖动的方块将从 原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图1 和图2）；//呀，不好意思，PDF的图片我复制不出来，还望见谅，用字母写出来，还望见谅// 3 0 4 3 <—3 0 4 0 0 0 4 2 ==》 3 4 2 ==> 3 0 2 0 3 4 2 0 3 4 2 0 3 3 2 0 1 1 2 1 0 1 1 2 1 0 1 1 2 1 2、任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则 它们将立即被消除（参见图1 到图3）。 注意： a) 如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图4，三个颜 色为1 的方块和三个颜色为2 的方块会同时被消除，最后剩下一个颜色为2 的方块）。 b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所 有方块会被同时消除（例如下面图5 所示的情形，5 个方块会同时被消除）。 3、方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注 意：掉落的过程中将不会有方块的消除。 上面图 1 到图3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐 标为（0, 0），将位于（3, 3）的方块向左移动之后，游戏界面从图1 变成图2 所示的状态， 此时在一竖列上有连续三块颜色为4 的方块，满足消除条件，消除连续3 块颜色为4 的方块 后，上方的颜色为3 的方块掉落，形成图3 所示的局面。 【输入】 输入文件 mayan.in，共6 行。 第一行为一个正整数 n，表示要求游戏通关的步数。 接下来的 5 行，描述7*5 的游戏界面。每行若干个整数，每两个整数之间用一个空格隔 开，每行以一个0 结束，自下向上表示每竖列方块的颜色编号（颜色不多于10 种，从1 开 始顺序编号，相同数字表示相同颜色）。 输入数据保证初始棋盘中没有可以消除的方块。 【输出】 输出文件名为 mayan.out。 如果有解决方案，输出n 行，每行包含3 个整数x，y，g，表示一次移动，每两个整数 之间用一个空格隔开，其中（x，y）表示要移动的方块的坐标，g 表示移动的方向，1 表示 向右移动，-1 表示向左移动。注意：多组解时，按照x 为第一关健字，y 为第二关健字，1 优先于-1，给出一组字典序最小的解。游戏界面左下角的坐标为（0，0）。 如果没有解决方案，输出一行，包含一个整数-1。 【输入输出样例 1】 mayan.in 3 1 0 2 1 0 2 3 4 0 3 1 0 2 4 3 4 0 mayan.out 2 1 1 3 1 1 3 0 1 样例输入的游戏局面如上面第一个图片所示，依次移动的三步是：（2，1）处的方格向 右移动，（3，1）处的方格向右移动，（3，0）处的方格向右移动，最后可以将棋盘上所有方 块消除。 【数据范围】 对于 30%的数据，初始棋盘上的方块都在棋盘的最下面一行； 对于 100%的数据，0 < n≤5。 (太不容易了，这道题我抄了20多分钟，样例的图没有画，大家自己下载PDF 的题吧） 下面给出我的做法， 事实上，这道题给了3s，完全可以用暴搜，从行开始，再从列开始，找到一个不为0的点，就先往右，后往左，移动后，再能落下去的落，然后消，如果有被消得，就在落，一直重复，直至不能再消或落为止，然后再一次从行开始，再从列开始，找到一个不为0的点，直到超过步数或者找见就退出，粗略计算了一下复杂度最坏情况下应该在10^8左右，完全能够AC了，如果非要加优化，那么，就这样，若这一个点左边有点，那就说明之前已经试过了，所以就不用搜了，这样能节省1/4的时间，我试了一下，未加优化时，最常用时0.63s，优化后，最常用时0.32s（虽然都是一些废话） 下面给出标程//后续：大家还是直接看下面的吧，这里的在tyvj上会tle var ss:array[0..5,1..5,1..7]of integer; a,b,c:array[1..5]of integer; i,j,k,n:integer; function xiao(k:integer):boolean; var i,j:integer; v:array[1..5,1..7]of boolean;pp:boolean; begin fillchar(v,sizeof(v),false);pp:=false; for i:=1 to 5 do for j:=1 to 7 do begin if (i>1)and(i<5)and(ss[k,i,j]<>0)and(ss[k,i,j]=ss[k,i-1,j])and(ss[k,i,j] =ss[k,i+1,j]) then begin v[i,j]:=true;v[i-1,j]:=true;v[i+1,j]:=true;end; if (j>1)and(j<7)and(ss[k,i,j]<>0)and(ss[k,i,j-1]=ss[k,i,j])and(ss[k,i,j] =ss[k,i,j+1]) then begin v[i,j]:=true;v[i,j-1]:=true;v[i,j+1]:=true;end; end; for i:=1 to 5 do for j:=1 to 7 do if v[i,j] then begin pp:=true;ss[k,i,j]:=0;end; exit(pp); end; procedure luo(k:integer);var i,j,l:integer; begin for j:=2 to 7 do for i:=1 to 5 do if (ss[k,i,j]<>0)and(ss[k,i,j-1]=0) then begin l:=j;while (l>1)and(ss[k,i,l-1]=0) do dec(l);{这里注意一下，要一直往下落，知道不能再落，之所以强调，是因为我在考试时是从上往下找，若能落，就下落一下，结果才发现，可能又连续的两个需要落）} ss[k,i,l]:=ss[k,i,j];ss[k,i,j]:=0;end; end; procedure shuchu; var i:integer; begin for i:=1 to n do writeln(a[i]-1,' ',b[i]-1,' ',c[i]);close(input);close(output);halt; end; function pan:boolean; var i,j:integer; begin for i:=1 to 5 do for j:=1 to 7 do if ss[n,i,j]<>0 then exit(false); exit(true); end; procedure sosuo(x,y,p,k:integer);var t,i,j:integer; begin ss[k]:=ss[k-1]; t:=ss[k,x,y];ss[k,x,y]:=ss[k,x+p,y];ss[k,x+p,y]:=t; a[k]:=x;b[k]:=y;c[k]:=p; luo(k); while xiao(k) do luo(k); if (k=n)and(pan) then shuchu; if k for i:=1 to 5 do for j:=1 to 7 do if ss[k,i,j]<>0 then begin if i<5 then sosuo(i,j,1,k+1);if (i>1)and(ss[k,i-1,j]=0) then sosuo(i,j,-1,k+1); end; end; begin assign(input,'mayan.in');assign(output,'mayan.out'); reset(input);rewrite(output); readln(n); for i:=1 to 5 do begin j:=0;read(k);while k<>0 do begin inc(j);ss[0,i,j]:=k;read(k);end;end; for i:=1 to 5 do for j:=1 to 7 do if ss[0,i,j]<>0 then begin if i<5 then sosuo(i,j,1,1);if (i>1)and(ss[0,i-1,j]=0) then sosuo(i,j,-1,1); end; writeln('-1'); close(input);close(output); end. 后续：不好意思，今天，突然发现TYVJ上有这六道题了，测了一下，除了本题以外，其余都是0ms闪过，这道题我在cena上过的，可是交到tyvj上最后一组就TLE了，所以，又稍加修改了一下，下面的程序，在tyvj上最长耗时是两秒，但是，肯定过了，这里就贴出来与大家分享吧 var ss:array[0..5,1..5,1..7]of integer; a,b,c:array[1..5]of integer; i,j,k,n:integer; function xiao(k:integer):boolean; var i,j:integer; v:array[1..5,1..7]of boolean;pp:boolean; begin fillchar(v,sizeof(v),false);pp:=false; for i:=1 to 5 do for j:=1 to 7 do begin if (i>1)and(i<5)and(ss[k,i,j]<>0)and(ss[k,i,j]=ss[k,i-1,j])and(ss[k,i,j] =ss[k,i+1,j]) then begin v[i,j]:=true;v[i-1,j]:=true;v[i+1,j]:=true;end; if (j>1)and(j<7)and(ss[k,i,j]<>0)and(ss[k,i,j-1]=ss[k,i,j])and(ss[k,i,j] =ss[k,i,j+1]) then begin v[i,j]:=true;v[i,j-1]:=true;v[i,j+1]:=true;end; end; for i:=1 to 5 do for j:=1 to 7 do if v[i,j] then begin pp:=true;ss[k,i,j]:=0;end; exit(pp); end; procedure luo(k:integer);var i,j,l:integer; begin for j:=2 to 7 do for i:=1 to 5 do if (ss[k,i,j]<>0)and(ss[k,i,j-1]=0) then begin l:=j;while (l>1)and(ss[k,i,l-1]=0) do dec(l); ss[k,i,l]:=ss[k,i,j];ss[k,i,j]:=0;end; end; procedure shuchu; var i:integer; begin for i:=1 to n do writeln(a[i]-1,' ',b[i]-1,' ',c[i]);halt; end; function pan:boolean; var i:integer; begin for i:=1 to 5 do if ss[n,i,1]<>0 then exit(false); exit(true); end; procedure sosuo(x,y,p,k:integer);var t,i,j:integer; begin ss[k]:=ss[k-1]; t:=ss[k,x,y];ss[k,x,y]:=ss[k,x+p,y];ss[k,x+p,y]:=t; a[k]:=x;b[k]:=y;c[k]:=p; luo(k); while xiao(k) do luo(k); if (k=n)and(pan) then shuchu; if k for i:=1 to 5 do for j:=1 to 7 do if ss[k,i,j]<>0 then begin if (i<5)and(ss[k,i,j]<>ss[k,i+1,j])//其实就只有优化了一下这里// then sosuo(i,j,1,k+1);if (i>1)and(ss[k,i-1,j]=0) then sosuo(i,j,-1,k+1); end; end; begin readln(n); for i:=1 to 5 do begin j:=0;read(k);while k<>0 do begin inc(j);ss[0,i,j]:=k;read(k);end;end; for i:=1 to 5 do for j:=1 to 7 do if ss[0,i,j]<>0 then begin if (i<5)and(ss[0,i+1,j]<>ss[0,i,j]) then sosuo(i,j,1,1);if (i>1)and(ss[0,i-1,j]=0) then sosuo(i,j,-1,1); end; writeln('-1'); end. 程序不是很难懂，大家自己理解吧，这里就不标注了 这是我第一次参加NOIP，第一天的三道题，我前两道AC了，最后一道因为在过程里面开了数组，就ＷＡ了，全是２０１错误，共得了２１０分，这才感觉到细心也是蛮重要的／／其实，对比第二天的题，第一天的题，还是蛮简单的，／／怎么说呢，这里我想告诉大家，在真正考试时能拿多少分就拿多少分，如果有一道题在４５分钟之内不能ＡＣ，那就想办法过部分数据，如果压根没有思路，那就骗分，总之，这已经不是平常的练兵了，也不是在ｔｙｖｊ上刷提，必须ＡＣ才行，你的任务就是发挥到最好……还有…………不要粗心 NOIP2011 普及组复赛 1 .数字反转(reverse.cpp/c/pas ) 【问题描述】 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为 零，否则反转后得到的新数的最高位数字不应为零。(参见样例2) 【输入】 输入文件名为reverse. in 。 输入共一行，一个整数No 【输出】 输出文件名为reverse.out 。 输出共1行，一个整数，表示反转后的新数。 【输入输出样例1】 -1,000,000,000 < N< 1,000,000,000 。 【解题】这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题(以及但测试数据没出)。 -0 , 【法一】字符串处理 Var i,l,k:i nteger; s:stri ng; p:boolea n; begin assig 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 s[1]=' -' the n begin write('-'); k:=2; en d; p:=true;; for i:=l dow nto k do begin if(p)a nd((s[i]='0')) the n continue else begin write(s[i]); p:=false;; en d; en d; close(i nput); close(output); en d. 【法二】数字处理 Var f:i nteger; n,an s:lo ngint; begin assig n(i nput, 'reverse.i n'); reset(i nput); assig n(o utput, 'reverse.out'); rewrite(output); readl n(n); if n<0 the n begin f:=-1; n :=-n; 第十七届全国青少年信息学奥林匹克联赛初赛试题 （提高组 Pascal语言两小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共20题，每题1.5分。共计30分。每题有且仅有一个正确选项。） B 1．在二进制下，1100011 +（）= 1110000。 A．1011 B．1101 C．1010 D．1111 B 2．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。A．66 B．5A C．50 D．视具体的计算机而定 A 3．右图是一棵二叉树，它的先序遍历是（）。 A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF D 4．寄存器是（）的重要组成部分。 A．硬盘B．高速缓存C．内存D．中央处理器（CPU） B 5．广度优先搜索时，需要用到的数据结构是（）。 A．链表B．队列C．栈D．散列表 A 6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。 A．程序运行时理论上所占的内存空间 B．程序运行时理论上所占的数组空间 C．程序运行时理论上所占的硬盘空间 D．程序源文件理论上所占的硬盘空间 C 7．应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。 A．O(n2)B．O(n log n)C．O(n) D．O(1) D 8．为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。 A．微软 B．美国计算机协会（ACM） C．联台国教科文组织D．万维网联盟（W3C） NOIP2011 （普及组 C++语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。） 1．在二进制下，1011001 + （）= 1100110。 A．1011 B．1101 C．1010 D．1111 2．字符“0”的ASCII码为48，则字符“9”的ASCII码为（）。 A．39 B．57 C．120 D．视具体的计算机而定 3．一片容量为8G的SD卡能储存大约（）张大小为2MB的数码照片。 A．1600 B．2000 C．4000 D．16000 4．摩尔定律（Moore's law)是由英特尔创始人之一戈登·摩尔(Gordon Moor)提出来的。根据摩尔定律，在过去几十年一级在可预测的未来纪念，单块集成电驴的集成度大约每（）个月翻一番。A．1 B．6C．18 D．36 5．无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（）条边。 A．7 B．21 C．42 D．49 6．寄存器是（）的重要组成部分。 A．硬盘B．高速缓存C．内存D．中央处理器（CPU） 7．如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（）。 A．10 B．11 C．12 D．13 8．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 A．快速排序B．插入排序C．冒泡排序D．归并排序 9．一个正整数在二进制下有100位，则它在十六进制下有（）位。 A．7 B．13 C．25 D．不能确定 10．有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（）。 A．正确的，将文件放入回收站以为着彻底删除、无法恢复 B．不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复 C．不正确的，即使回收站清空，文件只是被标记为删除，仍可能通过回复软件找回 D．不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除 数字反转题目描述 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形 式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。【数据范围】 -1,000,000,000 ≤ N≤ 1,000,000,000。 输入格式 输入共 1 行，一个整数N。 输出格式 输出共 1 行，一个整数，表示反转后的新数。 样例输入： 123 －380 样例输出： 321 －83 统计单词数题目描述 一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位 置，有的还能统计出特定单词在文章中出现的次数。 现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章 中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。 【数据范围】 1 ≤ 单词长度≤ 10。 1 ≤ 文章长度≤ 1,000,000。 【输入输出样例 1 说明】 输出结果表示给定的单词To 在文章中出现两次，第一次出现的位置为0。 【输入输出样例 2 说明】 表示给定的单词to 在文章中没有出现，输出整数-1。 输入格式 第 1 行为一个字符串，其中只含字母，表示给定单词； 第 2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。 输出格式 只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开， 分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字 母在文章中的位置，位置从0 开始）；如果单词在文章中没有出现，则直接输出一个整数-1。 样例输入： [sample 1] To to be or not to be is a question [sample 2] to Did the Ottoman Empire lose its power at that time 样例输出： [sample 1] 2 0 [sample 2] -1 瑞士轮题目描述 2*N名编号为1~2N的选手共进行R轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。 每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1名和第2名、第3名和第4名、……、第2K-1名和第2K名、……、第2N-1名和第2N名，各进行一场比赛。每场比赛胜者得1分，负者得0分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。 现给定每个选手的初始分数及其实力值，试计算在R轮比赛过后，排名第Q的选手编号是多少。我 们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。 输入格式 输入的第一行是三个正整数N、R、Q，每两个数之间用一个空格隔开，表示有2*N名选手、R轮比赛，以及我们关心的名次Q。 第二行是2*N个非负整数s1，s2，…，s2N，每两个数之间用一个空格隔开，其中si表示编号为i 的选手的初始分数。 第三行是2*N个正整数w1，w2，…，w2N，每两个数之间用一个空格隔开，其中wi表示编号为i 的选手的实力值。 输出格式 NOIP普及组初赛历年试题及答案选择题篇 单项选择题：每次共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。注：答案在文末 一、计算机基础（每年8-10题，占选择题的一半，找份材料翻几遍就可拿分了） NOIP2011-3. 一片容量为8G的SD卡能储存大约( )张大小为2MB的数码照片。 A.1600 B.2000 C.4000 D.16000 NOIP2011-4. 摩尔定律(Moore'slaw)是由英特尔创始人之一戈登·摩尔(GordonMoor)提出来的。根据摩尔定律，在过去几十年一级在可预测的未来纪念，单块集成电路的集成度大约每( )个月翻一番。 A.1 B.6 C.18 D.36 NOIP2011-6.寄存器是( )的重要组成部分。 A.硬盘 B.高速缓存 C.内存 D.中央处理器(CPU) NOIP2011-10. 有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是( )。 A .正确的，将文件放入回收站以为着彻底删除、无法恢复 B.不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复 C.不正确的，即使回收站清空，文件只是被标记为删除，仍可能通过回复软件找回 D.不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除 NOIP2011-14. 生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下不属于生物特征识别技术及其应用的是( )。 NOIP2011-16. 关于汇编语言，下列说法错误的是( )。 A.是一种与具体硬件相关的程序设计语言 B.在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试 C.可以直接访问寄存器、内存单元、以及I/O端口 D.随着高级语言的诞生，如今已完全被淘汰，不再使用 NOIP2011-18. 1956年( )授予肖克利、巴丁和布拉顿，以表彰他们对半导体的研究和晶体管效应的发现。 A.诺贝尔物理学奖 B.约翰·冯·诺依曼奖 C.图灵奖 D.高德纳奖 NOIP2011-20. 从ENIAC到当前最先进的计算机，冯·诺依曼体系结构始终占有重要地位。冯诺依曼体系结构的核心内容是( )。 A.采用开关电路 B.采用半导体器件 C.采用存储程序和程序控制原理 D.采用键盘输入 NOIP2012-1. 计算机如果缺少( )，将无法正常启动。 A.内存 B.鼠标 C.U盘 D.摄像头 NOIP普及组初赛历年试题及答案选择题篇 ————————————————————————————————作者：————————————————————————————————日期： NOIP普及组初赛历年试题及答案选择题篇 单项选择题：每次共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。注：答案在文末 一、计算机基础（每年8-10题，占选择题的一半，找份材料翻几遍就可拿分了） NOIP2011-3. 一片容量为8G的SD卡能储存大约( )张大小为2MB的数码照片。 A.1600 B.2000 C.4000 D.16000 NOIP2011-4. 摩尔定律(Moore'slaw)是由英特尔创始人之一戈登·摩尔(GordonMoor)提出来的。根据摩尔定律，在过去几十年一级在可预测的未来纪念，单块集成电路的集成度大约每( )个月翻一番。 A.1 B.6 C.18 D.36 NOIP2011-6.寄存器是( )的重要组成部分。 A.硬盘 B.高速缓存 C.内存 D.中央处理器(CPU) NOIP2011-10. 有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是( )。 A .正确的，将文件放入回收站以为着彻底删除、无法恢复 B.不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复 C.不正确的，即使回收站清空，文件只是被标记为删除，仍可能通过回复软件找回 D.不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除 NOIP2011-14. 生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下不属于生物特征识别技术及其应用的是( )。 NOIP2011-16. 关于汇编语言，下列说法错误的是( )。 A.是一种与具体硬件相关的程序设计语言 B.在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试 C.可以直接访问寄存器、内存单元、以及I/O端口 D.随着高级语言的诞生，如今已完全被淘汰，不再使用 NOIP2011-18. 1956年( )授予肖克利、巴丁和布拉顿，以表彰他们对半导体的研究和晶体管效应的发现。 A.诺贝尔物理学奖 B.约翰·冯·诺依曼奖 C.图灵奖 D.高德纳奖 NOIP2011-20. 从ENIAC到当前最先进的计算机，冯·诺依曼体系结构始终占有重要地位。冯诺依曼体系结构的核心内容是( )。 A.采用开关电路 B.采用半导体器件 C.采用存储程序和程序控制原理 D.采用键盘输入 全国信息学奥林匹克联赛（NOIP2011）复赛普及组 全国信息学奥林匹克联赛（NOIP2011）复赛 普及组 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称数字反转统计单词数瑞士轮表达式的值英文题目与子目录名reverse stat swiss exp 可执行文件名reverse stat swiss exp 输入文件名reverse.in stat.in swiss.in exp.in 输出文件名 reverse.out stat.out swiss.out exp.out 每个测试点时限1秒1秒1秒1秒 测试点数目10 10 10 10 每个测试点分值10 10 10 10 附加样例文件有有有有 结果比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统传统 二．提交源程序文件名 对于 C++语言reverse.cpp stat.cpp swiss.cpp exp.cpp 对于 C语言reverse.c stat.c swiss.c exp.c 对于 pascal语言reverse.pas stat. pas swiss. pas exp.pas 三．编译命令（不包含任何优化开关） 对于 C++语言 g++ -o reverse reverse.cpp -lm g++ -o stat stat.cpp -lm g++ -o swiss swiss.cpp -lm g++ -o exp exp.cpp -lm 对于 C语言 gcc -o reverse reverse.c -lm gcc -o stat stat.c -lm gcc -o swiss swiss.c -lm gcc -o exp exp.c -lm 对于 pascal语言 fpc reverse.pas fpc stat.pas fpc swiss.pas fpc exp.pas 四．运行内存限制 内存上限 128M 128M 128M 128M 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为： CPU P4 3.0GHz，内存 1G，上述时限以此配置为准。 4、特别提醒：评测在 NOI Linux下进行。 第1 页共5 页 全国信息学奥林匹克联赛（NOIP2011）复赛普及组 1．数字反转 (reverse.cpp/c/pas) 【问题描述】 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。 【输入】输入文件名为reverse.in。输入共1行，一个整数N。 第十八届全国青少年信息学奥林匹克联赛初赛 （普及组Pascal语言试题） 竞赛时间：2012年10月13日14:30~16:30 选手注意： ●试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上一律无效。 ●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料 一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项） 1．计算机如果缺少（），将无法正常启动。 A．内存B．鼠标C．U盘D．摄像头 2．（）是一种先进先出的线性表。 A．栈B．队列C．哈希表（散列表）D．二叉树 3．目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。 A．硅B．铜C．锗D．铝 4．十六进制数9A在（）进制下是232。 A．四B．八C．十D．十二 5．（）不属于操作系统。 A．Windows B．DOS C．Photoshop D．NOI Linux 6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。 A．ABC B．CBA C．ACB D．BAC 7．目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。 A．显示器B．CPU C．内存D．鼠标 8．使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列5，4，3，2，1需要执行（）次操作，才能完成冒泡排序。 A．0 B．5 C．10 D．15 9．1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。 A．电子管B．晶体管C．集成电路D．超大规模集成电路 10．无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。 A．中国公司的经理与波兰公司的经理交互商业文件 2011年第十七届全国青少年信息学奥林匹克联赛初赛试题 （普及组 Pascal 语言两小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共 20 题，每题 1.5 分，共计 30 分。每题有且仅有一个正确选项。） 1、在二进制下，1101001 + （） = 1110110。 A、1011 2、字符“0”的 ASCII 码为 48，则字符“9”的 ASCII 码为（）。 A、39 3、一片容量为 8GB 的 SD 卡能存储大约（）张大小为 2MB 的数码照片。 A、1600 4、摩尔定律（Moore's law）是由英特尔创始人之一戈登·摩尔（Gordon Moore）提出来的。根据摩尔定律，在过去几十年以及在可预测的未来几年，单块集成电路的集成度大约每（）个月翻一番。 A、1 5、无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它共有（）条边。 A、7 6、寄存器是（）的重要组成部分。 A、硬盘 7、如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（）。 A、10 8、体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 A、快速排序 B、插入排序 C、冒泡排序 D、归并排序 B、11 C、12 D、13 B、高速缓存 C、内存 D、中央处理器（CPU） B、21 C、42 D、49 B、6 C、18 D、36 B、2000 C、4000 D、16000 B、57 C、120 D、视具体的计算机而定 B、1101 C、1010 D、1111 1 四．运行内存限制 内存上限 128M 128M 128M 128M 全国信息学奥林匹克联赛（NOIP2011）复赛普及组 1．数字反转 (reverse.cpp/c/pas) 【问题描述】 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。 【输入】输入文件名为reverse.in。输入共1行，一个整数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。 2．统计单词数 (stat.cpp/c/pas) 【问题描述】 一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和 第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。 【输入】 输入文件名为stat.in，2行。第1行为一个字符串，其中只含字母，表示给定单词；第2行为一个字符串，其中只可能包含字母和空格，表示给定的文章。 【输出】 输出文件名为stat.out。只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0开始）；如果单词在文章中没有出现，则直接输出一个整数-1。 【输入输出样例1】 stat.in stat.out To to be or not to be is a question 2 0 【输入输出样例1说明】 输出结果表示给定的单词To在文章中出现两次，第一次出现的位置为0。 【输入输出样例2】 stat.in stat.out to Did the Ottoman Empire lose its power at that time -1 【输入输出样例2说明】 表示给定的单词to在文章中没有出现，输出整数-1。 【数据范围】 1 ≤单词长度≤ 10。 1 ≤文章长度≤ 1,000,000。 NOIP2011第十七届全国青少年信息学奥林匹克联赛初赛试题 （提高组 C++语言两小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确选项。） 1．在二进制下，1011001 + （）= 1100110。 A．1011 B ．1101 C．1010 D．1111 2．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。 A．66 B．5A C．50 D．视具体的计算机而定 3．右图是一棵二叉树，它的先序遍历是（）。 A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF 4．寄存器是（）的重要组成部分。 A．硬盘B．高速缓存C．内存D．中央处理器（CPU） 5．广度优先搜索时，需要用到的数据结构是（）。 A．链表B．队列C．栈D．散列表 6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（）。 A．程序运行时理论上所占的内存空间 B．程序运行时理论上所占的数组空间 C．程序运行时理论上所占的硬盘空间 D．程序源文件理论上所占的硬盘空间 7．应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。 A．O (n2) B．O (n log n ) C．O (n) D．O (1) 8．为解决web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。 A．微软B．美国计算机协会（ACM）C．联合国教科文组织D．万维网联盟（W3C） 9．体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到低站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 A．快速排序B．插入排序C．冒泡排序D．归并排序10．1956年（）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain）A．诺贝尔物理学奖B．约翰·冯·诺依曼奖 C．图灵奖D．高德纳奖（Donald E. Knuth Prize） 第十七届全国青少年信息学奥林匹克联赛试题 （普及组 Pascal 语言） ●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共 20 题，每题 1.5 分，共计 30 分。每题有且仅有一个正确选项。） 1、在二进制下，1101001 + （） = 1110110。 A、1011 B、1101 C、1010 D、1111 2、字符“0”的 ASCII 码为 48，则字符“9”的 ASCII 码为（）。 A、39 B、57 C、120 D、视具体的计算机而定 3、一片容量为 8GB 的 SD 卡能存储大约（）张大小为 2MB 的数码照片。 A、1600 B、2000 C、4000 D、16000 4、摩尔定律（Moore's law）是由英特尔创始人之一戈登·摩尔（Gordon Moore）提出来的。根据摩尔定律，在过去几十年以及在可预测的未来几年，单块集成电路的集成度大约每（）个月翻一番。 A、1 B、6 C、18 D、36 5、无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它共有（）条边。 A、7 B、21 C、42 D、49 6、寄存器是（）的重要组成部分。 A、硬盘 B、高速缓存 C、内存 D、中央处理器（CPU） 7、如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（）。 A、10 B、11 C、12 D、13 8、体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 A、快速排序 B、插入排序 C、冒泡排序 D、归并排序 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); 第十七届全国青少年信息学奥林匹克联赛初赛试题（提组 Pascal 语言两小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共10题，每题1.5分，共15分，每题有且仅有一个正确选项。） 1. 在二进制下，1011010+（）=1100111。 A.1011 B.1101 C.1010 D.1111 解析：简单的二进制运算，炮灰都会。直接用减法：1100111-1011010=00001101；也可用补码计算： 1100111-1011010=（1100111）补+（-1011010）补=（01100111）+（11011010）补=（01100111）+（10100101+00000001）=（01100111）+10100110）=100001101=1101（超过8位者溢出）。答案：B 2. 字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。A．66 B.5A C.50 D.视具体的计算机而定 解析：每年必考进制转换题。若记得ASCII码的可以直接算出Z的码然后转回16进制，A的ASCII码是65，则Z的ASCII码为65+25=90，（90）10=（5A）16。若不记得的就把十六进制的41转回十进制，4*16+1=65，然后+25得90，再转成16进制得5A。 答案：B A．ABDEFC B.DBEFAC C.DFEBCA D.ABCDEF 解析：每年必考树的遍历题。先序遍历就是先根遍历，就是先根，再左右子树的遍历。然后就ABDEFC出来了。 答案：A 4. 寄存器是（）的重要组成部分。 A. 硬盘 B. 高速缓存 C. 内存 D. 中央处理器（CPU） 解析：每年必考硬件知识题。计算机中能存储数据的部件有：寄存器，一级缓存，二级缓存，只读存储器ROM，随机存储器RAM和外存。其中寄存器和一级缓存在CPU内，一级缓存又名片上的缓存。二级缓存，只读存储器ROM和随机存储器RAM都在主板上，二级缓存又名板上的缓存，只读存储器ROM和随机存储器RAM共同构成内存。外存指硬盘、光盘和可移动磁盘等。CPU包括运算逻辑部件ALU、寄存器部件和控制部件等。 答案：D 全国信息学奥林匹克联赛（2011）复赛 普及组 （请选手务必仔细阅读本页内容）一．题目概况 二．提交源程序文件名 三．编译命令（不包含任何优化开关） 四．运行内存限制 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、中函数 ()的返回值类型必须是，程序正常结束时的返回值必 须是 0。 3、全国统一评测时采用的机器配置为： P4 3.0，内存 1G，上述 时限以此配置为准。 4、特别提醒：评测在下进行。 1．数字反转 () 【问题描述】 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例 2）。 【输入】 输入文件名为。输入 共 1 行，一个整数 N。 【输出】 输出文件名为。 输出共 1 行，一个整数，表示反转后的新数。 【输入输出样例 1】 【输入输出样例2】 【数据范围】 -1,000,000,000 ≤ N ≤ 1,000,000,000。 2．统计单词数 () 【问题描述】 一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。 现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1）， 如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。 【输入】 输入文件名为，2 行。 第 1 行为一个字符串，其中只含字母，表示给定 单词；第 2 行为一个字符串，其中只可能包含字 母和空格，表示给定的文章。【输出】输出文件 名为。只有一行，如果在文章中找到给定单词 则输出两个整数，两个整数之间用一个空格隔 开，分别是单词在文章中出现的次数和第一次出 现的位置（即在文章中第一次出现时，单词首字 母在文章中的位置，位置从 0 开始）；如果单词 在文章中没有出现，则直接输出一个整数-1。 【输入输出样例 1】 17届NOIP（C语言）普及组初赛试题 一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。） 1．在二进制下，1101001 + （）= 1110110。 A. 1011 B. 1101 C. 1010 D. 1111 2．字符“0”的ASCII码为48，则字符“9”的ASCII码为（）。 A. 39 B. 57 C. 120 D. 视具体的计算机而定3．一片容量为8GB的SD卡能存储大约（）张大小为2MB的数码照片。A. 1600 B. 2000 C. 4000 D. 16000 4．摩尔定律（Moore's law）是由英特尔创始人之一戈登?摩尔（Gordon Moore）提出来的。根据摩尔定律，在过去几十年以及在可预测的未来几年，单块集成电路的集成度大约每（）个月翻一番。 A. 1 B. 6 C. 18 D. 36 5．无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图G 有7个顶点，则它共有（）条边。 A. 7 B. 21 C. 42 D. 49 6．寄存器是（）的重要组成部分。 A. 硬盘 B. 高速缓存 C. 内存 D. 中央处理器（CPU） 7．如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（）。 A. 10 B. 11 C. 12 D. 13 8. 体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 A. 快速排序 B. 插入排序 C. 冒泡排序 D. 归并排序 9．一个正整数在二进制下有100位，则它在十六进制下有（）位。 A. 7 B. 13 C. 25 D. 不能确定 10．有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。 NOIP2011提高组解题报告day1 (2011-12-13 09:29:54) 标签： 杂谈 铺地毯 【问题描述】 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标 系的第一象限）铺上一些矩形地毯。一共有n 张地毯，编号从1 到n。现在将这些地毯按照 编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。 【输入】 输入文件名为carpet.in。 输入共n+2 行。 第一行，一个整数n，表示总共有n 张地毯。 接下来的n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每 两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x 轴和y 轴方向的长度。 第n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。 【输出】 输出文件名为carpet.out。 输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。 【输入输出样例】 carpet.in 3 1 0 2 3 0 2 3 3 2 1 3 3 2 2 3 carpet.out 3 【解题报告】 从后往前扫，找到第一个覆盖这个点的就输出，否则无解。 program carpet; //uses sysutils; var n,i,a,b:longint; x2,x1,y1,y2:array[0..100001]of longint; //time:extended; procedure main; begin readln(n); 全国信息学奥林匹克联赛（NOIP2011）复赛 提高组day1 （请选手务必仔细阅读本页内容） 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU P4 3.0GHz，内存1G，上述时限以此配置为准。 4、特别提醒：评测在NOI Linux下进行。 1．铺地毯 (carpet.cpp/c/pas) 【问题描述】 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标 系的第一象限）铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到 n 。现在将这些地毯按照 编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。 地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形 地毯边界和四个顶点上的点也算被地毯覆盖。 【输入】 输入文件名为 carpet.in 。 输入共 n+2 行。 第一行，一个整数 n ，表示总共有 n 张地毯。 接下来的 n 行中，第 i+1 行表示编号 i 的地毯的信息，包含四个正整数 a ，b ，g ，k ，每 两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a ，b ）以及地毯在 x 轴和 y 轴方向的长度。 第 n+2 行包含两个正整数 x 和 y ，表示所求的地面的点的坐标（x ，y ）。 【输出】 输出文件名为 carpet.out 。 输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。 如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2， 2）的最上面一张地毯是 y x NOIP2011普及组初赛试题C++版 第十七届全国青少年信息学奥林匹克联赛初赛试题 一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。） 1．在二进制下，1011001 + （） = 1100110。 A．1011 B．1101 C．1010 D．1111 2．字符“0”的ASCII码为48，则字符“9”的ASCII码为（）。 A．39 B．57 C．120 D．视具体的计算机而定 3．一片容量为8G的SD卡能储存大约（）张大小为2MB的数码照片。 A．1600 B．2000 C．4000 D． 16000 4．摩尔定律（Moore's law)是由英特尔创始人之一戈登·摩尔(Gordon Moor)提出来的。根据摩尔定律，在过去几十年一级在可预测的未来纪念，单块集成电驴的集成度大约每（）个月翻一番。 A．1 B． 6 C． 18 D． 36 5．无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（）条边。 A．7 B．21 C．42 D．49 6．寄存器是（）的重要组成部分。 A．硬盘 B．高速缓存 C．内存 D．中央处理器（CPU） 7．如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（）。 A．10 B．11 C．12 D．13 8．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 A．快速排序 B．插入排序 C．冒泡排序 D．归并排序 9．一个正整数在二进制下有100位，则它在十六进制下有（）位。 A．7 B．13 C．25 D．不能确定 10．有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（）。 A．正确的，将文件放入回收站以为着彻底删除、无法恢复 B．不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复C．不正确的，即使回收站清空，文件只是被标记为删除，仍可能通过回复软件找回 D．不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除11．广度优先搜索时，需要用到的数据结构是（）。 A．链表 B．队列 C．栈 D．散列表 12．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。 A．程序运行时理论上所占的内存空间B．程序运行时理论上所占的数组空间 C．程序运行时理论上所占的硬盘空间 D．程序源文件理论上所占的硬盘空间NOIP2011普及组复赛(试题+源程序)
noip2011初赛试题及答案(完美Word版)
noip2011 初赛普及组c++试题及答案
NOIP2011普及组
NOIP普及组初赛历年试题及答案选择题篇
NOIP普及组初赛历年试题及标准答案选择题篇
全国信息学奥林匹克联赛(NOIP2011)复赛普及组
NOIP2012普及组初赛及答案(Pascal)
NOIP2011普及组初赛试题与答案
(NOIP2011)复赛普及组试题
NOIP2011提高组初赛试题_C++含答案
noip2011普及组初赛试题与答案
NOIP 2011普及组复赛(试题+源程序)
第十七届NOIP2011 提高组初赛试题及答案解析
NOIP2011复赛普及组试题
NOIP2011-17届NOIP(C语言)普及组初赛试题
NOIP2011提高组解题报告day1
NOIP2011提高组复赛试题Day1
NOIP2011普及组初赛试题及答案C
相关主题
文本预览