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所有，转载请注明出处！