当前位置：文档库 › NOIP2013冲刺训练(第十五组)

NOIP2013冲刺训练(第十五组)

[NOIP2013&NOI2014省选]冲刺训练

[第十五组]

测试时间：3.5小时

内存管理

【问题描述】

Windows的内存管理系统是十分复杂的，我们要求你编写一个程序，来模拟内存管理操作。

计算机的内存被分割成30000个相同大小的连续区域，每个区域被称作一个内存块（Block），这些内存块被依次编号为1，2，3，…，29998，29999，30000。内存管理的基本单位是块，即某个应用程序申请或访问的内存必须是块的整数倍。

当某应用程序申请或访问内存时，该应用程序会向Windows发送一条消息（Message）：

（1） +：表示应用程序在第Time秒向Windows发送一条申请内存的消息；

（2） . ：表示应用程序在第Time秒向Windows发送一条访问第Label块内存的消息。

其中：和会在真正的消息中被替换为相应数字。

程序开始时，所有内存块均处于空闲状态。

对于申请内存的消息，Windows系统会将当前空闲内存块中编号最小的那一块分配给相应的应用程序，并且相应内存块转变为被占用状态。对于访问内存的消息，若当前内存块处于被占用状态，则Windows系统会反馈一个“+”表示该内存块可以被访问，否则反馈一个“-”表示程序无法访问该内存块。对于任何被占用的内存块，若在600秒内无任何操作，则该内存块会被系统释放掉，重新变为空闲状态。

【输入格式】

输入文件包含若干行，每行描述一条消息，消息共有两种：

（1） +

（2） .

消息含义见问题描述。“+”前有一个空格，“.”的前后都有一个空格，其他地方无多于空格。

保证Time按照非递减顺序出现，对于在同一时刻发出的消息，按照输入顺序处理。

【输出格式】

对于每条申请内存的消息，输出Windows分配给该应用程序的内存块编号。

对于每条访问内存的消息，输出“+”或“-”表示该内存块是否可以被成功访问。

【输入输出样例】

输入：

1 +

2 . 2

2 . 3

3 . 30000

601 . 1

601 . 2

602 . 3

602 +

1202 . 2

输出：

【样例说明】

对于前3条申请内存的消息，Windows系统依次将1、2、3号内存块分配给应用程序，若在接下来600秒内没有对这些内存块进行任何操作，这些内存块将在第601秒时被系统释放掉；

对于接下来3条访问内存的消息，2号和3号内存块在占用，返回“+”，同时它们的释放时间被推迟到第602秒。30000号内存块未被占用，于是返回“-”；

再接下来3条访问内存的消息，由于在第601秒时1号内存块被释放，在第602秒时2号和3号内存块被释放，所以依次返回“-”、“+”和“-”，同时2号内存块的释放时间被推迟到第1201秒；

下面2条申请内存的消息，由于目前1号和3号是空闲内存块，2号在被占用，所以Windows分别将1号和3号内存块分配给应用程序，并且1号和3号内存块的释放时间为第1202秒。

最后一条访问内存的消息，由于2号内存块已在第1201秒时被释放掉，因此返回“-”。

【数据范围】

对于20%的数据，满足：消息数不大于500；

对于100%的数据，满足：消息数不大于100000，每次申请内存操作时，至少会有一个内存块处于空

闲状态，0<=Time<86400，保证数据合法。

买礼物

【问题描述】

圣诞节要到了，WZK想要为女朋友购买一些礼物。商店里总共有n个礼物，编号分别为1到n。假设P i、V i分别表示第i件物品的价格和WZK女朋友的喜爱程度。有一些礼品是有特殊含义的，WZK必须给他的女朋友买。

WZK现在手上有两张信用卡，而且这两张信用卡只能分开使用。即假设当第一张卡中有3元，第二张卡中有2元时，WZK不能用这两张卡购买5元的礼物。

因为WZK是神犇，又这么痴情，所以商店老板准备免费赠送WZK一个礼物。现在，WZK经过分析后想知道，如何购买礼物才能使他女朋友对礼物的喜爱值之和最大。

【输入格式】

输入文件中的第一行为三个整数V1，V2，n（1<=V1<=500，1<=V2<=50，1<=n<=300），分别表示两张信用卡的额度和礼物的个数。

接下来的n行，每行有三个整数P i，V i，S i（1<=P i，V i<=1000），分别表示礼物的价格、喜爱程度以及是否必须购买，S i=1表示该礼物必须购买，S i=0表示不一定要购买。

【输出格式】

输出文件中仅一行为一个整数，表示WZK女朋友对礼物的喜爱程度。

如果WZK不能将所有必须购买的礼物购买到，那么就输出-1。

【输入输出样例】

输入1：

3 2 4

3 10 1

2 10 0

5 100 0

5 80 0

输出1：

120

输入2：

3 2 4

3 10 1

2 10 0

5 100 0

5 80 1

输出2：

100

【数据范围】

对于20%的数据，满足：1<=n<=50；

对于100%的数据，满足：1<=V1<=500，1<=V2<=50，1<=n<=300。

防贼道路

【问题描述】

A国有N个城市，M条双向道路（所有城市都是连通的），每条道路都有相应的价值，由于A国盗贼出没比较频繁，所以国王决定只保留一些道路，使得任意两座城市只有一条简单路径连通。

假设T是其中一种合法的方案，那么P(T)代表的是合法方案中所有道路价值的最大公约数。国王想借此机会了解一下你的数学能力，所以你需要在一秒内回答他所有P(T)的最小公倍数的大小。

【输入格式】

输入文件中的第一行为两个整数N，M，表示城市数量，道路数量。

接下来的M行，每行有三个数s，t，d，分别表示城市s与城市t间存在一条价值为d的道路，保证s不等于t。

【输出格式】

输出文件中仅一行为一个整数，表示所求的最小公倍数ans。

【输入输出样例】

输入：

3 3

1 2 2

2 3 3

1 3 6

输出：

【样例说明】

有3个合法的方案，P(T)分别为1，2，3，它们的最小公倍数为6。

【数据范围】

对于20%的数据，满足：M=N-1；

对于另外20%的数据，满足：M=N；

对于另外30%的数据，满足：所有道路的价值都是2的整数次幂；

对于100%的数据，满足：N<=1000，M<=100000，D i<=2^15-1，ans<=2^64-1。

noip普及组复赛模拟试题26(答案)

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。 var s3,s1,s2:string; n,i:integer; begin assign(input,'reverse.in');reset(input); assign(output,'reverse.out');rewrite(output); read(s1); n:=length(s1); if s1[1]='-' then begin s2:='-'; for i:=1 to n-1 do s1[i]:=s1[i+1]; delete(s1,n,1); end; n:=length(s1); for i:=1 to n do s3:=s3+s1[n-i+1]; i:=1; while(s3[i]='0')and(length(s3)>1) do delete(s3,1,1); write(s2+s3); close(input);close(output); end. 2．统计单词数(stat.cpp/c/pas)【问题描述】一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。【输入】输入文件名为stat.in，2 行。第 1 行为一个字符串，其中只含字母，表示给定单词；第 2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

NOIP2015提高组复赛试题Day2

全国信息学奥林匹克联赛（2015）复赛提高组 2 （请选手务必仔细阅读本页内容）一．题目概况二．提交源程序文件名三．编译命令（不包含任何优化开关） 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、中函数 ()的返回值类型必须是，程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为： () x2 240 ，2.8，内存 4G，上述时限以此配置为准。 4、只提供格式附加样例文件。 5、特别提醒：评测在当前最新公布的下进行，各语言的编译

器版本以其为准。

1．跳石头 () 【问题描述】一年一度的“跳石头”比赛又要开始了！这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。【输入格式】输入文件名为。输入文件第一行包含三个整数 L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。接下来 N 行，每行一个整数，第 i 行的整数（0 < < L）表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。【输出格式】输出文件名为。输出文件只包含一个整数，即最短跳跃距离的最大值。【输入输出样例 1】【输入输出样例 1 说明】将与起点距离为 2 和 14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离 17 的岩石跳到距离 21 的岩石，或者

noip普及组复赛模拟试题18

1. 话说去年苹果们被陶陶摘下来后都很生气，于是就用最先进的克隆技术把陶陶克隆了好多份>.<然后把他们挂在树上，准备摘取。摘取的规则是，一个苹果只能摘一个陶陶，且只能在它所能摘到的高度以下（即是小于关系）的最高的陶陶，如果摘不到的话只能灰溜溜的走开了>.<给出苹果数目及每个苹果可以够到的高度和各个陶陶的高度，求苹果们都摘完后剩下多少个陶陶…… 【输入格式】第一行为两个数，分别为苹果的数量n和陶陶的数量m（n,m<=2000）以下的n行，分别为各个苹果能够到的最大高度。再接下来的m行，分别为各个陶陶的高度。高度均不高于300。当然了，摘取的顺序按照输入的“苹果够到的最大高度”的顺序来摘。【输出格式】输出仅有一个数，是剩下的陶陶的数量【样例输入】5 5↙9↙10↙2↙3↙1↙6↙7↙8↙9↙10 【样例输出】3 2. 某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：7 279 5 279 这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是：5 279 7 279则按输出错误处理，不能得分。【输入】输入文件scholar.in包含n+1行：第1行为一个正整数n，表示该校参加评选的学生人数。第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n（恰好是输入数据的行号减1）。所给的数据都是正确的，不必检验。【输出】输出文件scholar.out共有5行，每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。【输入输出样例1】 scholar.in scholar.out 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 【输入输出样例2】 scholar.in scholar.out 8 80 89 89 8 265 2 264

NOIP2013普及组初赛试题

2013年第十九届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题一、单项选择题（共 20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项） 1. 一个 32 位整型变量占用（ A ）个字节。 A. 4 B. 8 C. 32 D. 128 2. 二进制数 11.01 在十进制下是（A ）。 A. 3.25 B. 4.125 C. 6.25 D. 11.125 3. 下面的故事与（ B ）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事........................’” A. 枚举 B. 递归 C. 贪心 D. 分治 4. 逻辑表达式（）的值与变量 A 的真假无关。 A. (A ? B) ??A B. (A ? B) ??B C. (A ? B) ?(?A ? B) D. (A ? B) ??A ? 5. 将（2, 6, 10, 17）分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数h(x) =（ D ），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。 A. x mod 11 B. x2 mod 11 C. 2x mod 11 D. [X] mod 11，其中[X]表示X下取整 6. 在十六进制表示法中，字母 A 相当于十进制中的（ B ）。 A. 9 B. 10 C. 15 D. 16 7. 下图中所使用的数据结构是（ B ）。 8. 在 Windows 资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制”的操作选项，它的意思是（ C ）。 A. 用剪切板中的文件替换该文件 B. 在该文件所在文件夹中，将该文件克隆一份 C. 将该文件复制到剪切板，并保留原文件 D. 将该文件复制到剪切板，并删除原文件 9. 已知一棵二叉树有 10 个节点，则其中至多有（ A ）个节点有 2 个子节点。 A. 4 B. 5 C. 6 D. 7 10.在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4 个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的（c ）条边。 A. 1 B. 2 C. 3 D. 4 11. 二叉树的（A ）第一个访问的节点是根节点。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 以上都是 12. 以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ C ）。 A. A0, A1, A2, A3 B. A0, A1, A3, A2 C. A0, A2, A1, A3 D. A0, A3, A1, A2 13. IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（D ）位地址的 IPv6 协议所取代。 A. 40 B. 48 C. 64 D. 128 14. （A ）的平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。 A. 快速排序 B. 插入排序 C. 冒泡排序 D. 基数排序 15. 下面是根据欧几里得算法编写的函数，它所计算的是 a 和 b 的（ b ）。 function euclid(a, b : longint) : longint;

NOIP2015提高组

CCF全国信息学奥林匹克联赛（NOIP2015）复赛提高组 day1 （请选手务必仔细阅读本页内容）注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，内存4G，上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。

1．神奇的幻方 (magic.cpp/c/pas) 【问题描述】幻方是一种很神奇的 N?N 矩阵：它由数字 1,2,3,……,N?N 构成，且每行、每列及两条对角线上的数字之和都相同。当 N 为奇数时，我们可以通过以下方法构建一个幻方：首先将 1 写在第一行的中间。之后，按如下方式从小到大依次填写每个数 K(K=2,3,…,N?N) ： 1.若(K?1)在第一行但不在最后一列，则将 K 填在最后一行，(K?1)所在列的右一列； 2.若(K?1)在最后一列但不在第一行，则将 K 填在第一列，(K?1)所在行的上一行； 3.若(K?1)在第一行最后一列，则将 K 填在(K?1)的正下方； 4.若(K?1)既不在第一行，也不在最后一列，如果(K?1)的右上方还未填数，则将K填在(K?1)的右上方，否则将 K 填在(K?1)的正下方。现给定 N，请按上述方法构造 N?N 的幻方。【输入格式】输入文件名为magic.in。输入文件只有一行，包含一个整数 N，即幻方的大小。【输出格式】输出文件名为magic.out。输出文件包含 N行，每行 N个整数，即按上述方法构造出的 N?N 的幻方。相邻两个整数之间用单个空格隔开。 magic/magic1.in magic/magic1.ans 【输入输出样例2】见选手目录下的magic/magic2.in和magic/magic2.ans。【数据规模与约定】对于 100% 的数据，1≤N≤39 且 N 为奇数。

noip 普及组复赛

NOIP2011 普及组复赛 1．数字反转（c/pas）【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零。（参见样例2）【输入】输入文件名为。输入共一行，一个整数N。【输出】输出文件名为。输出共1行，一个整数，表示反转后的新数。 -1,000,000,000≤N≤1,000,000,000。【解题】这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题（以及-0，但测试数据没出）。【法一】字符串处理 Var i,l,k:integer; s:string; p:boolean; begin assign(input, ''); reset(input); assign(output, ''); 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, ''); reset(input); assign(output, ''); rewrite(output); readln(n);

NOIP普及组复赛解题报告

NOIP2015 普及组解题报告南京师范大学附属中学树人学校CT 1.金币（coin.cpp/c/pas）【问题描述】国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。请计算在前K 天里，骑士一共获得了多少金币。【输入格式】输入文件名为coin.in 。输入文件只有1行，包含一个正整数K，表示发放金币的天数。【输出格式】输出文件名为coin.out。输出文件只有1 行，包含一个正整数，即骑士收到的金币数。【数据说明】对于100%的数据，1 < K < 10,000 【思路】模拟【时空复杂度】 O(k) ，O(1) 2 、扫雷游戏（mine.cpp/c/pas ）【问题描述】

扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。【输入格式】输入文件名为mine.in 。输入文件第一行是用一个空格隔开的两个整数n和m分别表示雷区的行数和列数。接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符’* '表示相应格子是地雷格，字符' ?'表示相应格子是非地雷格。相邻字符之间无分隔符。【输出格式】输出文件名为mine.out 。输出文件包含n行，每行m个字符，描述整个雷区。用’* '表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。【数据说明】对于100% 的数据，1< n W 1Q01< me 100 【思路】模拟【技巧】可将数组多开一圈，省去边界条件的判断【时空复杂度】 O(mn)，O(mn)

NOIP2015普及组复赛解题报告

精心整理 NOIP2015普及组解题报告南京师范大学附属中学树人学校CT 1.金币(coin.cpp/c/pas) 【问题描述】国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天）放模式会一直这样延续下去：当连续N 续N+1天里，每天收到N+1枚金币。请计算在前K 【输入格式】输入文件名为coin.in。输入文件只有1 【数据说明】对于100%的数据，1≤K≤10,000。【思路】模拟【时空复杂度】 O(k)，O(1)

2、扫雷游戏（mine.cpp/c/pas）【问题描述】扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出n行m 向上与之直接相邻的格子。【输入格式】输入文件名为mine.in。接下来n行，每行m 雷个数表示非地雷格。相邻字符之间无分隔符。【数据说明】对于100%的数据，1≤n≤100，1≤m≤100。【思路】模拟【技巧】

可将数组多开一圈，省去边界条件的判断。【时空复杂度】 O(mn)，O(mn)

3.求和(sum.cpp/c/pas) 【问题描述】一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色color i（用[1，m]当中的一个整数表示），并且写了一个数字number i。定义一种特殊的三元组：(x,y,z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件： 1.x,y,z都是整数,x

NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组C试题

第十九届全国青少年信息学奥林匹克联赛初赛普及组C语言试题竞赛时间：2013年10月13日14:30~16:30 选手注意： ●试题纸共有9页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。 ●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项） 1.一个32位整型变量占用（）个字节。 A. 4 B. 8 C. 32 D. 128 2.二进制数11.01在十进制下是（）。 A. 3.25 B. 4.125 C. 6.25 D. 11.125 3.下面的故事与（）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：?从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’? A. 枚举 B. 递归 C. 贪心 D. 分治 4.逻辑表达式（）的值与变量A的真假无关。 A. (A ? B) ? ?A B. (A ? B) ? ?B C. (A ? B) ? (?A ? B) D. (A ? B) ? ?A ? B 5.将（2, 6, 10, 17）分别存储到某个地址区间为0~10的哈希表中，如果哈希函数h(x) = （），将不会产生冲突，其中a mod b表示a除以b的余数。 A. x mod 11 B. x2 mod 11 C. 2x mod 11 D. ?√ ?mod 11，其中?√ ?表示√下取整 6.在十六进制表示法中，字母A相当于十进制中的（）。 A. 9 B. 10 C. 15 D. 16

NOIP2013提高组复赛Day2

CCF全国信息学奥林匹克联赛（NOIP2013）复赛提高组 day2 （请选手务必仔细阅读本页内容）注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+， 2.71GHz，内存2G，上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒：评测在NOI Linux下进行。

1．积木大赛 (block.cpp/c/pas) 【题目描述】春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是?i。在搭建开始之前，没有任何积木（可以看成n块高度为0的积木）。接下来每次操作，小朋友们可以选择一段连续区间[L,R]，然后将第L块到第R块之间（含第L块和第R块）所有积木的高度分别增加1。小M是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。【输入】输入文件为block.in 输入包含两行，第一行包含一个整数n，表示大厦的宽度。第二行包含n个整数，第i个整数为?i。【输出】输出文件为block.out 仅一行，即建造所需的最少操作数。【样例解释】其中一种可行的最佳方案，依次选择 [1,5] [1,3] [2,3] [3,3] [5,5] 【数据范围】对于30%的数据，有1≤n≤10；对于70%的数据，有1≤n≤1000；对于100%的数据，有1≤n≤100000，0≤?i≤10000。

noip普及组复赛模拟试题17(附答案)

图书馆馆长正犯愁呢，原来，有一堆的书要他整理，每本书都有一个书号（<=32767),现在他有一本书，这本书的书号为K（<=32767),现在他要找出一本书号比这本书大的书和书号比这本小的书(但都要最接近图书馆馆长已有的书号），将找到的这两本书的书号加起来，并算出加起来以后的数是否为素数 Input 第一行二个数为N,K，表示几本书以及手中书的书号（<=32767) 第二行开始有N个整数，表示这些书的书号 Output 第一行一个数，表示两本书书号加起来的和第二行一个字符，表示和是否为素数，若是则输出"Y"否则输出"F"（引号不打出）Sample Input 6 5 6 4 5 3 1 20 Sample Output 10 F program ex1148; var n,k,i,x,s:integer; a:array[0..32767] of integer; f:boolean; begin readln(n,k); fillchar(a,sizeof(a),0); for i:=1 to n do begin read(x); a[x]:=1; end; s:=0; for i:=k+1 to 32767 do if a[i]<>0 then begin s:=s+i;break; end; for i:=k-1 downto 1 do if a[i]<>0 then begin s:=s+i;break; end; f:=true; for i:=2 to trunc(sqrt(s)) do if s mod i=0 then begin f:=false;break;end; writeln(s); if f=true then write('Y') else write('F'); end. 输入12 7 8 12 18 7 11 3 20 15 14 26 21 16 输出11 Y 输入21 10

NOIP初赛普及组C++题目及答案

第二十二届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2016年10月22日14:30~16:30 选手注意： ● 试题纸共有9页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。 ● 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共20题，每题分，共计30分；每题有且仅有一个正确选项） 1.以下不是微软公司出品的软件是（）。 A. Powerpoint B. Word C. Excel D. AcrobatReader 2. 如果256种颜色用二进制编码来表示，至少需要（）位。 A. 6 C. 8 3.以下不属于无线通信技术的是（）。 A. 蓝牙 B. WiFi C. GPRS D. 以太网 4. 以下不是CPU生产厂商的是（）。 D. IBM A. Intel B. AMD C. Microsoft 5. 以下不是存储设备的是（）。 D. 鼠标 A. 光盘 B. 磁盘 C. 固态硬盘 6.如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S和字母键D的顺序循环按键，即CapsLock、A、S、D、 CapsLock、A、S、D、……，屏幕上输出的第81个字符是字母（）。 A. A C. D D. a 7. 二进制数00101100和00010101的和是（）。 A. 00101000 C. 01000100 D. 00111000 8. 与二进制小数相等的八进制数是（）。 D. A. 初赛普及组C++语言试题第1页，共9 页

9. 以下是32位机器和64位机器的区别的是（）。 A. 显示器不同 B. 硬盘大小不同 C. 寻址空间不同 D. 输入法不同 10. 以下关于字符串的判定语句中正确的是（）。 A. 字符串是一种特殊的线性表 B. 串的长度必须大于零 C. 字符串不可以用数组来表示 D. 空格字符组成的串就是空串 11.一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标(2i+1)处），则图中所有结点的最大下标为（）。 A.6 B.10 C.12 D.15 12.若有如下程序段，其中s、a、b、c均已定义为整型变量，且a、c均已赋值（c大于0）。 s=a; for(b=1;b<=c;b++)s=s+1; 则与上述程序段修改s值的功能等价的赋值语句是（）。 A.s=a+b; B.s=a+c; C.s=s+c; D.s=b+c; 13.有以下程序： #include usingnamespacestd; intmain(){ intk=4,n=0; while(n。如果L中存在x（i1x i+1>...>x n，则称L是单峰的，并称x i是L的 CCFNOIP2016初赛普及组C++语言试题第2页，共9页

NOIP2015初赛普及组C++试题及参考答案

第二十一届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2015年10月11日14:30-16:30 一、单项选择题(共20题，每题1.5分，共计30分；每题有且仅有一个正确选项) ⒈1MB等于( )。 A.10000字节 B.1024字节 C.1000×1000字节 D.1024×1024字节 ⒉在PC机中，PENTIUM(奔腾)、酷睿、赛扬等是指( )。A.生产厂家名称 B.硬盘的型号 C.CPU的型号 D.显示器的型号 ⒊操作系统的作用是( )。 A.把源程序译成目标程序 B.便于进行数据管理 C.控制和管理系统资源 D.实现硬件之间的连接 ⒋在计算机内部用来传送、存贮、加工处理的数据或指令都是以( )形式进行的。 A.二进制码 B.八进制码 C.十进制码 D.智能拼音码 ⒌下列说法正确的是( )。 A.CPU的主要任务是执行数据运算和程序控制 B.存储器具有记忆能力，其中信息任何时候都不会丢失C.两个显示器屏幕尺寸相同，则它们的分辨率必定相同D.个人用户只能使用Wifi的方式连接到Internet ⒍二进制数00100100和00010100的和是( )。 A.00101000 B.01100111 C.01000100 D.00111000 ⒎与二进制小数0.1相等的十六进制数是( )。 A.0.8 B.0.4 C.0.2 D.0.1 ⒏所谓的“中断”是指( )。A.操作系统随意停止一个程序的运行 B.当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的过程 C.因停机而停止一个程序的运行 D.电脑死机 ⒐计算机病毒是( )。A.通过计算机传播的危害人体健康的一种病毒 B.人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C.一种由于计算机元器件老化而产生的对生态环境有害的物质 D.利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 ⒑FTP可以用于( )。 A.远程传输文件 B.发送电子邮件 C.浏览网页 D.网上聊天 ⒒下面哪种软件不属于即时通信软件( )。 A.QQ B.MSN C.微信 D.P2P

noip普及组复赛模拟试题8(答案)

Description 给定整数n(32位以内),判断它是否为2的方幂。是就输出'yes'，否则输出'no'。 Input 一个整数n。 Output 一个字符串 Sample Input 4 Sample Output yes Hint n > 0 && ( ( n & ( n - 1 ) ) == 0 貌似是数学问题，套用了提示 program ex1560; var n:longint; begin readln(n); if (n>0) and (n and (n-1)=0) then write('yes') else write('no'); end. 输入 127 输出 NO 输入 262144 输出 YES 输入 68719476736 输出 YES 问题描述：计算机软件版本通常被用来区分某种软件在不同时间的发布。大部分软件版本号都是用“.”分隔的非负数的序列。对两个不同的版本A = a1.a2.a3…an和B = b1.b2.b3…bm，如果下面两个条件之一成立，我们认为版本A要比版本B新： 1．对某个i，我们有：对所有j < i, ai > bi 和aj = bj； 2．n比m大，而且对所有i < m, ai = bi。 (ai和bi都不超过LONGINT) 在这个问题里，你要对给定的一组版本号，按照上面的定义从旧到新排序。输入文件（VERSIONS.IN）：输入文件第一行是一个整数N（N<=20），表示要排序的版本数。接下来的N行每行一个版本号。每个版本号是长度不超过50的字符串。输出文件（VERSIONS.OUT）：将排好序的结果以每行一个版本号输出。输入输出样例： VERSIONS.IN 4 3.0.5 1 2.4 2.4.6 VERSIONS.OUT 1

NOIP提高组初赛历年试题及答案选择题篇

NOIP提高组初赛历年试题及答案选择题篇单项选择题（共10-15题，每题1.5分，共计15-22.5分。每题有且仅有一个正确选项。）注：答案在末尾 NOIP2011-1.在二进制下，1011001+（）=1100110。同普及组NOIP2011-1 A.1011 B.1101 C.1010 D.1111 NOIP2011-2.字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。 A.66 B.5A C.50 D.视具体的计算机而定 NOIP2011-3.下图是一棵二叉树，它的先序遍历是（）。 A.ABDEFC B.DBEFAC C.DFEBCA D.ABCDEF NOIP2011-4.寄存器是（）的重要组成部分。同普及组NOIP2011-6 A.硬盘 B.高速缓存 C.内存 D.中央处理器（CPU） NOIP2011-5.广度优先搜索时，需要用到的数据结构是（）。同普及组 NOIP2011-11 A.链表 B.队列 C.栈 D.散列表

NOIP2011-6.在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（）。同普及组NOIP2011-12 A.程序运行时理论上所占的内存空间 B.程序运行时理论上所占的数组空间 C.程序运行时理论上所占的硬盘空间 D.程序源文件理论上所占的硬盘空间 NOIP2011-7.应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。A.O(n2) B.O(n log n) C.O(n) D.O(1) NOIP2011-8.为解决web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。 A.微软 B.美国计算机协会（ACM） C.联合国教科文组织 D.万维网联盟（W3C） NOIP2011-9.体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到低站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。同普及组NOIP2011-8 A.快速排序 B.插入排序 C.冒泡排序 D.归并排序 NOIP2011-10.1956年（）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain）,以表彰他们对半导体的研究和晶体管效应的发现。同普及组NOIP2011-18 A.诺贝尔物理学奖 B.约翰·冯·诺依曼奖 C.图灵奖 D.高德纳奖（Donald E.KnuthPrize）

noip2015初赛普及组答案分析

单项选择题 1.A。计算机内部的用来传送、存贮、加工处理的数据或指令都是以二进制形式进行的。 2.A。写这题我用的是排除法,B选项显然不对,内存在断电后数据会丢失,C选项也是,屏幕的分辨率是可以手动调整的,D选项,当年我们都用宽带连接Internet的。 3.A。二进制小数转化为十六进制小数时,每四位二进制数转化为以为十六进制数,故0.10002可以转化为0.816。 4.D。我的做法是将每个数都化为二进制形式,因为十六进制数和八进制数转化为二进制数很容易,最后求得答案是D。 5.D。在链表中,每个结点包括两个部分：一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域,结点与结点之间是用指针连接的,故地址不必连续。 6.B。模拟一下进栈出栈的过程就行了,共有6次操作:进栈,进栈,出栈,进栈,进栈,出栈,每次操作后栈内元素分别为”a”,”a b”,”a”,”a b c”,”a b c d”,”a b c”,故最后栈顶元素是c。 7.B。前序遍历的顺序是”根->左->右”,后序遍历的顺序是”左->右->根”,对照四个答案,只有B能满足题目要求。 8.B。我们知道树高为n的满二叉树的结点个数为2n?1,当树高为5 时结点个数为31,当树高为6时结点个数为63,故答案是B。 9.B。画一张图的事情,就不说了。 10.D。由递推公式可得T(n)=1+(1+2+…+n)=n2+n2+1,故算法时间的复杂度为O(n2)。 11.D。用vector存边,由一个顶点的边引到另一个顶点,再不断引出别的顶点,过程中每个顶点和每条边都只用到一遍,故复杂度为O(n+e)。12.A。哈夫曼算法用来求哈夫曼树,此树的特点就是引出的路程最短, 求的过程运用到贪心思想,具体的请参考一下别的文章。 13.D。llink和rlink分别指向前驱和后继,不妨设p的前驱为o,在未插入前 p->llink就是o,o->rlink就是p,插入时,先将o->rlink赋为q,再将 q->rlink赋为p,然后将q->llink赋为o,最后将p->llink赋为q。 14.A。最粗暴的方法就是直接模拟,不知道有没有更先进的算法。 15.A。- -丨这题猜猜都是A,哪有考生自带鼠标的。

noip普及组复赛

NOIP2011普及组复赛 1 .数字反转（c/pas ）【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零。（参见样例2）【输入】【输出】输出文件名为。 -1,000,000,000 < N< 1,000,000,000 o 【解题】这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题(以及但测试数据没出)。【法一】字符串处理 Var i,l,k:i nteger; s:stri ng; p:boolea n; begin assig n(i nput, ”)； reset(i npu t); assig n(output, ''); rewrite(out pu t); 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)an d((s[i]-0')) the n contin ue else begin write(s[i]); p :=false;; en d; en d; close(i npu t); close(out pu t); en d. 【法二】数字处理 Var f:i nteger; n,an s:lo ngint; begin assig n(i nput, ''); reset(i npu t); assig n(output, ''); rewrite(out pu t); readl n(n); 输入文件名为。输入共一行，一个整数 No -0 ,

noip普及组复赛模拟试题22(答案)

军方截获的信息由n（n<=30000）个数字组成，因为是敌国的高端秘密，所以一时不能破获。最原始的想法就是对这n个数进行小到大排序，每个数都对应一个序号，然后对第i个是什么数感兴趣，现在要求编程完成。【输入格式】第一行n，接着是n个截获的数字，接着一行是数字k，接着是k行要输出数的序号。【输出格式】 k行序号对应的数字。【输入样例】Secret.in 5 121 1 126 123 7 3 2 4 3 【输出样例】Secret.out 7 123 121 program secret; const max=30000; var n,i,x,k:longint; a:array[1..max] of longint; procedure sort(l,r:longint); var i,j,t,mid:longint; begin i:=l;j:=r; mid:=a[(l+r)div 2]; repeat while a[i]mid do dec(j); if j>=i then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i); dec(j) end; until i>j; if l

assign(input,'secret.in'); assign(output,'secret.out'); reset(input); rewrite(output); readln(n); for i:=1 to n do read(a[i]); sort(1,n); readln(k); for i:=1 to k do begin readln(x); writeln(a[x]); end; close(input); close(output); end. 输入 15 12 10 36 127 126 123 75 89 101 999 777 654 456 890 134 6 2 4 3 9 10 14 输出12 75 36 127 134 890 输入24 8 18 12 24 434 10 36 127 126 123 75 89 101 999 777 654 456 890 134 555 221 108 888 656 8 5 4 3 19 20 14 17 10 输出24

noip普及组复赛解题报告

N O I P2015普及组解题报告南京师范大学附属中学树人学校CT 1.金币(coin.cpp/c/pas) 【问题描述】国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。请计算在前K天里，骑士一共获得了多少金币。【输入格式】输入文件名为coin.in。输入文件只有1行，包含一个正整数K，表示发放金币的天数。【输出格式】输出文件名为coin.out。输出文件只有1行，包含一个正整数，即骑士收到的金币数。【数据说明】对于100%的数据，1≤K≤10,000。【思路】模拟【时空复杂度】

O(k)，O(1)

2、扫雷游戏（mine.cpp/c/pas）【问题描述】扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。【输入格式】输入文件名为mine.in。输入文件第一行是用一个空格隔开的两个整数n和m，分别表示雷区的行数和列数。接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符’*’表示相应格子是地雷格，字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。【输出格式】输出文件名为mine.out。输出文件包含n行，每行m个字符，描述整个雷区。用’*’表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。【数据说明】