题目（看不清的亲们可以右键放大哦）：
数据：
Tag: NOIp
-
COCI 2008 Junior 试题及解析
题目
Instrukcije
【题目描述】
小马克今年成为小学生。不久后她将进行她的第一次考试，其中包括数学考试。她非常认真地复习，她认为自己已经准备好了。她的哥哥通过给她提出问题并解决的方式帮助她。
他写下许多问题，其中一个问题是由一连串整齐的数字组成，比如1个1，2个2，3个 3 等等。现在他给马克两个整数A和B；她的任务是找出由这两数描述的数列的和（从第A个数到第B个数组成的序列）。如果A是1，B是3，答案为1+2+2=5。
写一个问题，然后计算它们的和，小马克的哥哥能够验证答案正确与否。
【输入格式】
仅一行，包括正整数A和B，1≤A≤B≤1000。
【输出格式】
输出和仅显示一行。
【输入样例】
[cpp]1 3[/cpp]
【输出样例】
[cpp]5[/cpp]Lagno
【题目描述】
Lagno（西班牙和奥赛罗）是一种二人智力游戏。游戏设有一个黑方和一个白方。游戏桌面是正方形的，包含8行8列。
如果黑方玩家走出这样一部棋：将一枚黑子放在任一空格上，而在这个空格的八个方向（上、下、左、右和4个对角线方向）的至少一个方向上有一排白子被夹在这枚新下的黑子和其他黑子之间，任何方向，这排被新旧黑子包夹的所有的白子都要变成黑子。为这个游戏设计一个程序，计算一步棋中黑方能转变的白子数量的最大值。
【输入格式】
输入有8行，每行8个元素：“.”代表一个空格，“B”代表黑子，“W”代表白子。
【输出格式】
输出一步中黑方能吃掉白子的最大数，如果无法吃掉就输出“0”。
【输入样例】
[cpp]……..
……..
……..
…BW…
…WB…
……..
……..
……..[/cpp]
【输出样例】
[cpp]1[/cpp]Pjesma
【题目描述】
“Guess the song”是一项在克罗地亚的年轻程序员中非常流行的游戏。它是一种集技能、智慧、耐性于一体的游戏。这个游戏给玩游戏的人放音乐，游戏者的目标是竟可能快地猜这首歌的歌名。
Mirko可能不是一个很好的程序员，但他是一个世界级的猜歌者。Mirko总是在专辑里的某首歌播放出至少一半歌词的时候猜出歌名。所有歌名的单词是唯一的（没有一个单词会出现一次或更多次）。写一个程序，给出歌名和专辑名，看看Mirko在这首歌的哪个点上（在多少个单词之后）猜出歌名。
【输入格式】
第一行：包含一个整数N，1≤N≤50，它是一首歌里的单词数目。N下面的每一行包含歌名的一个单词。
第二行：包含一个整数M，1≤M≤10 000，它是专辑里的单词数目。M下面的每一行包含专辑里的一个单词。
歌名和专辑里的所有单词由1到15个小写英文字母组成。
注：测试数据将会使得Mirko总能从专辑里猜出歌曲名。
【输出格式】
输出一个数：Mirko在这首歌的哪个点上（在多少个单词之后）猜出歌名。
【输入样例】
[cpp]3
sedam
gladnih
patuljaka
7
sedam
dana
sedam
noci
sedam
gladnih
godina[/cpp]
【输出样例】
[cpp]6[/cpp]Nikola
【题目描述】
Nikola现在已经成为一个游戏里的重要人物。这个游戏是由一行N个方格，N个方格用1到N的数字表示。Nikola开始是在1号位置，然后能够跳到其他的位置，Nikola的第一跳必须跳到2号位置。随后的每一跳必须满足两个条件：
如果是向前跳，必须比前面一跳远一个方格。
如果是向后跳，必须和前面一跳一样远。
比如，在第一跳之后（当在2号位置时），Nikola能够跳回1号位置，或者向前跳到4号位置。
每次他跳入一个位置，Nikola必须付费。Nikola的目标是从一号位置尽可能便宜地跳到N号位置。
写一个程序，看看Nikola跳到N号位置时最小的花费。
【输入格式】
第一行：包含一个整数N，2≤N≤1000，它是位置的编号。
第2..N+1行：第i+1行表示第i个方格的费用，是一个正整数，绝对不超过500。
【输出格式】
输出Nikola跳到N号位置时最小的花费。
【输入样例】
[cpp]8
111
179
64
78
219
97
160
40[/cpp]
【输出样例】
[cpp]535[/cpp]解析
第一题：Instrukcije
算法：模拟。没什么好说的。
第二题：Lagno
算法：枚举。从任意一个点计算到其8个方向上第一个“W”点的距离，即这个点到8个方向上能将黑子变为白字的个数。
第三题：Nikola
算法：动态规划。
状态：f[i][j] 表示当前跳到第i个点，上一步跳了j步的状态。
初始值：f = Inf, f[1][0] = 0
答案：Min{f[n]}
转移方程：f[i][j] = Min{f[i][j], f[i – j][j – 1] + m[i]} = Min{f[i][j], f[i + j][j] + m[i]}
时间复杂度：O(n^2)
第四题：Pjesma
题意：若N个单词在M个单词表中的前i个单词出现的个数大于N的一半，则输出i的值。
算法：字符串处理。用一个标志数组标记是否匹配过。数据和标程
。
数据：
标程： 。版权
题目、数据版权为COCI所有，题解、标程版权归Mr.SXKDZ所有，转载请注明出处！ -
NOIp初赛总结——选择题
计算机基础知识复习
CPU：包括控制器和运算器。运算器：算术、逻辑（部件：算术逻辑单元、累加器、寄存器组、路径转换器、数据总线）；控制器：复位、使能（部件：计数器、指令寄存器、指令解码器、状态寄存器、时钟发生器、微操作信号发生器）。
主频：CPU的主频，即CPU内核工作的时钟频率（CPU Clock Speed）。通常所说的某某CPU是多少兆赫的，而这个多少兆赫就是“CPU的主频”。很多人认为CPU的主频就是其运行速度，其实不然。CPU的主频表示在CPU内数字脉冲信号震荡的速度，与CPU实际的运算能力并没有直接关系。
字长：电脑技术中对CPU在单位时间内能一次处理的二进制数的位数叫字长。所以能处理字长为8位数据的CPU通常就叫8位的CPU。同理32位的CPU就能在单位时间内处理字长为32位的二进制数据。当前的CPU大部分是32位的CPU。
【例1】关于CPU下面哪些说法是正确的：
A) CPU全称为中央处理器（或中央处理单元）。
B) CPU能直接运行机器语言。
C) CPU最早是由Intel公司发明的。
D) 同样主频下，32位的CPU比16位的CPU运行速度快一倍。
【答案】AB
【解析】C选项中第一个CPU由杰克在1958年研制出人类历史上第一块集成晶体管“微芯片”；D选项中CPU字长不能代表速度。
【例2】主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（ ）。
A. 寄存器 B. 高速缓存 C. 闪存 D. 外存
【答案】B
图灵机：是英国数学家阿兰·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。
【例3】关于图灵机下面的说法哪个是正确的：
A) 图灵机是世界上最早的电子计算机。
B) 由于大量使用磁带操作，图灵机运行速度很慢。
C) 图灵机只是一个理论上的计算模型。
D) 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
【答案】C
【解析】A、B项中图灵机只是理论模型，不是最早的电子计算机，最早的电子计算机是埃尼阿克； D项中是阿兰·图灵本人为破译德军的密码发挥了重要作用。
冯·诺依曼：冯·诺依曼计算机的设计思想：存储程序；逻辑组成：五大部分（运算器、控制器、存储器及输入输出设备）。
【例4】提出“存储程序”的计算机工作原理的是（ ）。
A. 克劳德·香农 B. 戈登·摩尔 C. 查尔斯·巴比奇 D. 冯·诺依曼
【答案】D
广告题目：CCF官网：http://www.ccf.org.cn/；NOI官网：http://www.noi.cn/；NOIp推荐IDE：GUIDE、Dev-C++、FreePascal。
HTML：超文本标记语言（英文：HyperText Markup Language，HTML）是为“网页创建和其它可在网页浏览器中看到的信息”设计的一种标记语言。HTML是一种规范，一种标准，它通过标记符号来标记要显示的网页中的各个部分。网页文件本身是一种文本文件，通过在文本文件中添加标记符，可以告诉浏览器如何显示其中的内容（如：文字如何处理，画面如何安排，图片如何显示等）。浏览器按顺序阅读网页文件，然后根据标记符解释和显示其标记的内容，对书写出错的标记将不指出其错误，且不停止其解释执行过程，编制者只能通过显示效果来分析出错原因和出错部位。但需要注意的是，对于不同的浏览器，对同一标记符可能会有不完全相同的解释，因而可能会有不同的显示效果。HTML之所以称为超文本标记语言，是因为文本中包含了所谓“超级链接”点。所谓超级链接，就是一种URL指针，通过激活（点击）它，可使浏览器方便地获取新的网页。这也是HTML获得广泛应用的最重要的原因之一。Html由此可见，网页的本质就是HTML，通过结合使用其他的Web技术（如：脚本语言、CGI、组件等），可以创造出功能强大的网页。因而，HTML是Web编程的基础，也就是说万维网是建立在超文本基础之上的。
HTML 5目前仍为草案，并已被W3C接纳。
【例5】在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（ ）。
A. <a url=”http://www.noi.cn”>欢迎访问NOI网站</a>
B. <a href=”http://www.noi.cn”>欢迎访问NOI网站</a>
C. <a>http://www.noi.cn</a>
D. <a name=”http://www.noi.cn”>欢迎访问NOI网站</a>
【答案】B
【解析】A项语法不正确； C项无用；D项为标签。
网络：IP地址：所谓IP地址就是给每个连接在Internet上的主机分配的一个32bit地址。按照TCP/IP协议规定，IP地址用二进制来表示，每个IP地址长32bit，比特换算成字节，就是4个字节。例如一个采用二进制形式的IP地址是“00001010000000000000000000000001”，这么长的地址，人们处理起来也太费劲了。为了方便人们的使用，IP地址经常被写成十进制的形式，中间使用符号“.”分开不同的字节。于是，上面的IP地址可以表示为“10.0.0.1”。
现有的互联网是在IPv4协议的基础上运行的。IPv6是下一版本的互联网协议，也可以说是下一代互联网的协议，它的提出最初是因为随着互联网的迅速发展，IPv4定义的有限地址空间将被耗尽，而地址空间的不足必将妨碍互联网的进一步发展。为了扩大地址空间，拟通过IPv6以重新定义地址空间。IPv4采用32位地址长度，只有大约43亿个地址，估计在2005～2010年间将被分配完毕，而IPv6采用128位地址长度，几乎可以不受限制地提供地址。
分类：A、B、C3类由InternetNIC在全球范围内统一分配，D、E类为特殊地址。
【例6】关于计算机网络，下面的说法哪些是正确的：
A) 网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。
B) 新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
C) TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。
D) 互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注册一个固定的域名来标明其地址。
【答案】C
【例7】 TCP/IP是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际协议（IP）。TCP/IP 协议把Internet网络系统描述成具有四个层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（ ）。
A. 链路层 B．网络层 C. 传输层 D. 应用层 E.会话层
【答案】B
各种编程语言： 最早编程语言：机器语言；最早面向过程的编程语言：Fortran；最早面向对象的编程语言：Smalltalk；C、C++、Pascal均属于面向过程的语言（C++、Object Pascal也是面向对象语言）、都需要编译。
【例8】Pascal语言、C语言和C++语言都属于（ ）。
A. 面向对象语言 B. 脚本语言 C. 解释性语言 D. 编译性语言
【答案】D
大事件：（今年指2011年）苹果前CEO乔布斯去世、Skype被微软收购、微软拟发布Win8同时能在平板电脑上运行……
【例9】今年（2010年）发生的事件有（ ）。
A.惠普实验室研究员Vinay Deolalikar自称证明了P≠NPB.英特尔公司收购计算机安全软件公司迈克菲（McAfee）
C.苹果公司发布iPhone 4手机
D.微软公司发布Windows 7操作系统
【答案】C
【例10】 在以下各项中，（ ）不是操作系统软件。
A. Solaris B. Linux C. Sybase D. WindowsVista E. Symbian
【答案】C
系统软件：在计算机软件中最重要且最基本的就是操作系统（OS）。它是最底层的软件，它控制所有计算机运行的程序并管理整个计算机的资源，是计算机裸机与应用程序及用户之间的桥梁。没有它，用户也就无法使用某种软件或程序。操作系统是计算机系统的控制和管理中心，从资源角度来看，它具有处理机、存储器管理、设备管理、文件管理等4项功能。操作系统如我们常用的Windows、Linux、Dos、Unix（开源）、Mac和Ubuntu（开源）等，而Foxpro、Access、Orale、Sybase、DB2和Informix等则是数据库系统。
【例11】Linux下可执行文件的默认扩展名为（ ）。
A. exe B. com C. dll D. 以上都不是
【答案】D
【解析】扩展名是Windows的概念。
编程基础知识
布尔表达式：是一段代码声明，它最终只有true（真）和false（假）两个取值。从最基本的层次来说，所有的布尔表达式，不论它的长短如何，其值只能是true或false。 运算符号：¬ — not；∧— and；∨ – or。
集合：组具有某种共同性质的数学元素。
【例12】以下逻辑表达式的值恒为真的是（ ）。
A. P∨(¬P∧Q)∨(¬P∧¬Q) B. Q∨(¬P∧Q)∨(P∧¬Q)
C. P∨Q∨(P∧¬Q)∨(¬P∧Q) D. P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)
【答案】A