信息学奥赛2009冬令营试题

2009年全国信息学奥林匹克冬令营NOI Winter Camp 2009竞赛时间：2008年1月20日上午8:00-13:00题目名称最短路问题语音识别优化设计V oice opt目录 shortest可执行文件名 shortest V oice N/A输入文件名 shortest.in voice.in opt1.in~opt10.in 输出文件名 shortest.out voice.out opt1.out~opt10.out 测试点最大时限 10s 6s N/A测试点数目 10 10 10每个测试点分值 10 10 10是否有部分分无有有题目类型传统传统提交答案附加文件无无 checker 提交源程序须加后缀对于Pascal语言 shortest.pas voice.pas N/A对于C 语言 shortest.c voice.c N/A对于C++ 语言 shortest.cpp voice.cpp N/A注意：除非特殊说明，最终测试时，所有编译命令均不打开任何优化开关最短路问题【问题描述】一个6×n的方格，初始每个格子有一个非负权值。

有如下两种操作形式：¾改变一个格子的权值（改变以后仍然非负）；¾求两个格子之间的最短路的权值。

【注解与任务】任意格子P的坐标(x P, y P)满足1 ≤x P≤ 6，1 ≤y P≤n。

格子P和Q的曼哈顿距离定义为|x P- x Q|+|y P - y Q|。

一个有序方格序列(p1, p2, ..., p n)，若满足任意p i和p i+1的曼哈顿距离为1，则称该序列为一条从p1到p n的路径，其权值为d(p1)+d(p2)+...+d(p n)，其中d(P)表示格子P的权值。

两个格子P和Q之间的最短路定义为从P到Q权值最小的路径。

【输入文件】第一行一个整数n。

接下来6行，每行n个整数，第i+1行第j个整数表示初始格子(i, j)的权值。

接下来是一个整数Q，后面的Q行，每行描述一个操作。

输入的操作有以下两种形式：操作1："1 x y c"(不含双引号)。

表示将格子(x, y)的权值改成c (1 ≤x≤ 6, 1 ≤y ≤n, 0 ≤c≤ 10000) 。

操作2："2 x1y1x2y2"(不含双引号)。

表示询问格子(x1, y1)和格子(x2, y2)之间的最短路的权值。

（1 ≤x1, x2≤6, 1 ≤y1, y2≤n）【输出文件】对于每个操作2，按照它在输入中出现的顺序，依次输出一行一个整数表示求得的最短路权值。

【样例输入】50 0 1 0 00 1 0 1 00 2 0 1 00 1 1 1 00 0 0 0 01 1 1 1 152 1 2 1 41 1 1 100002 1 2 1 41 2 3 100002 1 23 3【样例输出】12【数据约定】测试数据规模如下表所示数据编号n Q数据编号n Q300001 10 20 6 100002 100 200 7 3500030000500003 1000 2000 8 500006000010000 9 1000004 1000010000010000 10 1000005 10000【特别说明】本题测试时将使用-O2优化。

语音识别【题目背景】与机器进行语音交流，让机器明白你说什么，这是人们长期以来梦寐以求的事情。

语音识别技术就是让机器通过识别和理解过程把语音信号转变为相应的文本或命令的高技术。

——百度百科现在，我们需要你解决的是一个简化版的语音识别问题：麦克风所录入的信息可以被认为是一些独立的信号，每个信号都按照其电平值被表示为一个非负整数，这些信号组成的有序序列就是麦克风输入的信号序列。

语音信号实例信号序列可以用一个非负整数序列来描述，形如A = {a1, a2, ... a n}，信号序列A的子序列A'是指A中的一段连续信号A' = {a i, a i+1, ... a j-1, a j}。

实际情况中，麦克风录入的信号序列往往混有为数不多的噪声，为了在语音识别中能够处理噪声带来的问题，需要引入近似匹配的概念：设A、B是两个信号序列，A对于B近似匹配，是指从A中删除若干个信号之后，所得的信号序列恰好等于B。

我们把从A中删除信号的个数称为A对于B近似匹配的差别程度。

值得注意的是，为了使得识别有意义，只有那些差别程度不大的近似识别才是有意义的。

例如，从信号序列{1, 2, 0}中删除一个信号2就可以得到信号序列{1, 0}，因此{1, 2, 0}对于{1, 0}近似匹配，差别程度为1；同样{1, 2, 0}对于{0}也是近似匹配的，其差别程度为2，但是如果限定近似匹配的差别程度不能超过1，那么{1, 2, 0}对于{0}的近似匹配就将被忽略。

特别的，如果两个信号序列完全一致，那么这两个信号序列的匹配可以被认为是差别程度为0的近似匹配。

研究人员已经对很多日常使用的字进行了预处理，得到了和每个字相对应的信号序列，这些字的信号序列所组成的集合称为字典。

令A‘是信号序列A的一个子序列，如果A‘对于信号序列B近似匹配，那么A‘就是B在A中的一次近似出现。

例如：对于信号序列A = {a1, a2, a3, a4, a5, a6} = {3, 3, 3, 1, 2, 0}，那么A1 = {a1, a2, a3}, A2 = {a4, a5}, A3 = {a6}, A4 = {a1, a2}都是A的子序列。

考虑字典∑ = {a = {1}, b = {1, 2}, c = {0}, d = {3, 3}}，且近似匹配的差别程度上限为1，那么A1、A4都是d在A中的一次近似出现，A2是a或者b的近似出现，A3是c的近似出现。

进一步可知字典中的每一个字都可以在信号序列中被检测出来。

a被检测出3次，{a4},{a3, a4},{a4, a5}；b被检测出3次，{a4, a5}, {a3, a4, a5}, {a4, a5, a6}；c被检测出2次，{a6}, {a5, a6}；d被检测出4次，{a1, a2}, {a2, a3}, {a1, a2, a3}, {a2, a3, a4}。

为了对麦克风输入的信号序列作出尽量好的识别，一个最直观的想法是，从输入信号序列中能够识别出来的字越多越好。

具体的说，如果能够从信号序列A = {a1, a2, ... a n}中找出一组子序列D1, D2, ... D s，对于字典∑，满足：1)对于任意i、j，D i和D j没有相交部分；也就是说，如果D i = {a p, a p+1, ... a q}，D j = {a u, a u+1, ... a v}，那么一定有区间[p, q]和区间[u, v]没有交集，即p > v或者q < u。

2)任意D i都可以在字典中找到一个字(设为word i）的信号序列，使得D i对于字word i的信号序列近似匹配；那么D1->word1, D2->word2, ... D s->word s被称为A的一种识别方案，把这些近似匹配按照出现先后排列起来就可得到识别结果，s就是这种识别方案的长度。

最直观的想法就是希望能够找出一组最长的识别方案。

例如，考虑刚才的例子：{A1->d, A3->c}, {A4->d, A2->a, A3->c}，｛A4->d, A2->b, A3->c}都是可行的识别方案，对应的识别结果分别是："dc", "dac", "dbc"。

由于不存在长度超过3的识别方案，所以最长的识别方案的长度为3，有两种识别结果"dac"和"dbc"。

【任务】给定信号序列A，字典∑，和能够允许的近似匹配的差别程度的上限K。

要求计算：¾字典中有多少字在A中近似出现，总的近似出现的次数是多少？¾A的最长的识别方案的长度是多少，在识别方案长度最长的前提下，能够识别出的本质不同的序列有多少个？注意：如果两个识别方案分别对应识别结果words = {word1, word2, ... word p}和words' = {word'1, word'2, ... word'q}，如果words和words'不完全相同，则两个识别方案本质不同。

【输入文件】第一行有三个整数N、M、K，分别表示待测信号序列的长度、字典的大小和近似匹配差别程度的上限。

第二行有N个用空格隔开的非负整数，描述待测信号序列A。

接下来M行每行描述字典的一个不同的字，对于其中每一行：先输入一个非负整数L，表示这个字对应信号序列的长度，接下来L个整数给出这个字所对应的信号序列。

相邻的整数之间用空格隔开。

注意：不同的字可能对应相同或者类似的信号序列。

【输出文件】输出文件一共包含两行：第一行包含两个整数，分别表示字典中可以被检测出来的字的个数，以及近似出现的总次数；第二行包含两个整数，分别表示最长识别方案的长度，以及能够识别出的本质不同的最长识别方案数（输出的方案数为你所得到的答案对1 000 003取模后的结果）。

注意：每行要求包含且仅包含两个整数，用一个空格隔开，不允许多余的空格和换行，不允许输出不完整。

以下的输出均不合法（其中下划线表示空格，\n 表示回车）：多空格：100__100\n 100_100\n 多回车：100_100\n100_100\n\n多行首（尾）空格_100_100\n100_100_\n输出不完整100_100\n100\n【样例输入】6 4 13 3 3 1 2 01 12 1 21 02 3 3【样例输出】4 123 2【样例说明】样例为在题目背景中给出的例子。

【评分标准】每个测试点单独评分。

如果输出文件不存在、不合法则该测试点得0分，否则，你的得分为以下4项得分之和：能够识别的字的个数正确(2分)近似出现的总次数正确(4分)最长识别方案的长度正确(2分)最长识别方案的个数正确（2分）【数据约定】本题共有10个测试点，每个测试点10分，每个测试点单独评分Test#N≤M≤K≤L≤Test#N≤M≤K≤L≤1 6 5 1 10 6 100000202 150002 1000 10 5 100 7 10000020 20 10000015 5 500008 10000020 20 50000 3 5000020 20 150009 10000020 20 1000004 1000020 20 3000010 10000020 20 1000005 50000其中L表示字典中所有字的信号总长度。