第一届机房病毒杯NOIP提高组模拟赛试题+题解

现在距离第一届机房病毒杯的举行（2008年11月9日）已经过去了将近一年的时间。我也顺利获得了当年的NOIP一等奖，现在我以文化课作为主要努力方向。

为了更好的造福广大OIer，我决定逐渐公开和整理一些OI资料，于是就从《第一届机房病毒杯NOIP提高组模拟赛》开始吧。因为这是第一届（或许是最后一届？）我自己主办的NOIP比赛，所以具有一定的纪念意义。值得说明的是，当初这届比赛就是为了模拟NOIP，所以难度很低。

题目一、十一月十五日的快乐

背景 Background

终于到了一年一度的11月15日，神牛OIer 们又可以去刷题了。今年参加NOIP的人特别多。某省的参赛地点排满了长队。人们在路上惊奇的发现，有很多老同学、老朋友也参加了比赛。一路上，人们谈笑风生，兴奋不已……考完了NOIP，大家又一路同行回到了各自的家，开始了狂欢夜。

多么令人期待和兴奋的一天！不过其实，人们最高兴的还不是遇见老朋友，而是结交新朋友。可是结交新的朋友就需要很多时间，而除了考试之外时间并不多。例如小L，他在NOIP的入口处等待开门时，决定趁机和其它市县的牛们多套近乎。可是队伍太长，且人们都很自觉的站成仅仅一列，而小L又很想多交不同地方的朋友，因此小L想知道他在哪一个区域内可以结交到最多的不同地方的朋友。当然，这个区域不能太大，否则还没考试他就累死了。

题目描述 Description

现在有n个人，题目给出了他们每个人所在市县的编号。他们站在一个从左向右的队伍中。小L不在队列中。他想找到一个长度不超过D的区域，使他能够找到最多的不同地方的朋友。要求输出能找到的朋友所在不同市县的最大数和找到这些朋友的最小区间长度。比如在整个队伍内他按从左向右顺序找到了3个A地朋友，1个B地朋友，1个C地朋友。假设D = 5，那么不同市县的最大数为3（A地、B地、C地），最小区间长度为3（只须结交A地的最右面的一个人即可得到最大市县数3，因此区间长度不是5而是3）。假设在队伍内的人他都还没有结交。

数据范围

对于 100% 的数据，保证5<=n<=1000000, 1<=D<=n, 所有市县编号不超过32767。

输入格式

输入文件第一行为两个正整数n，D。分别表示队伍人数和他想找到的最长的区间长度。 接下来的n行，每行有一个整数，表示每个人所在市县的编号（从左向右）。

输出格式

输出数据为一行，这行有两个整数，用空格分开，按顺序分别代表能找到的朋友所在不同市县的最大数和找到这些朋友的最小区间长度。

样例输入

5 4 1 1 1 2 3

样例输出

3 3

解题报告

本题有O(n)的算法。我们发现，区间长度最小时，一定是从一组相同市县的最后一个开始，到另一组相同市县的第一个结束。因为这两个向前后延伸，都是相同的市县，对找到朋友数没有贡献，还增加了区间长度。 故我们可以采用逐个扫描各人的市县编号，并维护一个数组，用以保存当前最大不超过d的长度下各市县的人数。用首尾指针记录当前区间位置。用一个计数变量计算当前不同的市县编号个数，若大于当前最优值，则立即更新;若相等，则选择区间长度小的。 维护数组头指针：人数标记数组头指针对应元素加一。若原来为零，即原来不存在这个市县，市县计数变量加一，表示这个市县被选中。 维护数组尾指针：1、如果尾指针对应市县对应的人数大于一，则最末端的人没有必要，尾指针向前推一位。2、若首尾指针之差大于d，则区间过长，不满足题意，尾指针前移;若发现「必须去掉」的尾指针对应元素不再存在，即数组值为零，计数变量减一，表示这个市县不再被选中。 注意，必须先维护头指针再维护尾指针，否则在首尾对应元素恰好相等的情况下，尾指针查询对应市县人数时可能出错，由于未加上头指针对应元素。应该先维护与当前状态无关的头指针。 具体实现时，利用头指针一一增加的特性，用一个循环变量i充当头指针。尾指针则由初值为1的变量j充当。注意长度是i-j+1，不是i-j。根据以上分析，程序就不难写出了。 由于C语言运算较快，易于通过。Pascal语言的程序需要常数级优化才能通过。

考察内容

看题能力、建模和优化算法的能力、根据数据范围确定时间复杂度要求的能力、队列数据类型和指针的应用。

题目二、机房病毒

背景 Background 我们机房中了病毒，因此几乎什么都无法正常进入。为了解决这个病毒，我们花了好几天。终于在大家的共同努力下，病毒不再猖狂了。 题目描述 Description 我们的机房的所有计算机组成了一棵树，这是由于病毒，计算机无法两两完全连通的结果。所以，每台计算机能够直接连通的是它的孩子计算机和父亲计算机。话说某天晚上，我们发现病毒绝迹了，但是我们无法确认是否真的消灭干净了。因此我们需要派一些同学牺牲上课时间看守住所有的电脑两个小时，以确认没有任何病毒痕迹才能放心。我们当然想少耽误同学们的学习时间。因此我们需要找出一种方案，使所需要的看守人员最少。直接连通的两台计算机只需要一个人即可看守住。

数据范围对于 100% 的数据，保证n≤1500。

输入文件中数据表示一棵树，描述如下： 第一行 N，表示树中结点的数目。 从第二行开始，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，…，rk。 对于一个n(1 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。

输出数据只有一行，表示至少需要耽误多少学生的学习时间。

关于本题目的特别说明

因原题解有问题，而本题是本届中最有难度的一道题，为了给大家留下思考空间（当然，实际上这套题最有难度的本题也很简单），暂时不放上新题解。只提醒大家这是一道树形DP。

题目三、风月提序

背景 Background

兰亭临帖 行书如行云流水 月下门推 心细如你脚步碎 忙不迭 千年碑易拓 却难拓你的美 真迹绝 真心能给谁 牧笛横吹 黄酒小菜有几碟 夕阳余晖 如你的羞怯似醉 摹本易写 而墨香不退与你共留余味 一行朱砂 到底圈了谁 无关风月 我题序等你回 悬笔一绝 那岸边浪千叠 情字何解 怎落笔都不对 而我独缺 你一生的了解 弹指岁月 倾城顷刻间烟灭 青石板街 回眸一笑你婉约 恨了没 你摇头轻叹谁让你蹙着眉 而深闺 徒留胭脂味 人雁南飞 转身一瞥你噙泪 掬一把月 手揽回忆怎么睡 又怎么会 心事密缝绣花鞋针针怨怼 若花怨蝶 你会怨着谁 无关风月 我题序等你回 手书无愧 无惧人间是非 雨打蕉叶 又潇潇了几夜 我等春雷 来提醒你爱谁 题目描述 Description 现李风正使毛笔而题序，临风月而赋诗。诗长而情切，然以之长而视之乱，无心以断行。望神牛帮之。（现已断句） 本题没有明确的数据范围，但输入数据保证你所写的代码中的正确、完整的纯文件输入和输出操作在运行时用时不会超过时限的二分之一。

备注 Tip

提示：汉字的两个字节的每个字节的ASCII码均和空格及四种英文标点不同。不用考虑其它标点符号。 由于输入文件可能是一本长篇小说，因此请注意防止变量和数组的溢出。 最后一行内容后可以输出也可以不输出换行符。

输入输出数据

第一行有一个数字，表示他希望每一行拥有多少字符。（不超过500字符） 剩下的输入文件中的数据表示一篇序或一首诗。 输入数据保证不包含换行符(字符13或字符10)。

输出数据表示你帮李风题的序或赋的诗断行后的结果。如果行的末尾的词语或短句没有结束（即其后字符不是空格或标点(只考虑,.?!四个半角英文符号。)），则需要等该词结束后在换行。 输出数据要尽量使每行字符数接近输入要求，但不能删除任何字符，也不能小于要求字符，最后一行除外。

样例输入

10

无关风月 我题序等你回

 手书无愧 无惧人间是非

 雨打蕉叶 又潇潇了几夜

 我等春雷 来提醒你爱谁

样例输出

无关风月 我题序等你回 手书无愧 无惧人间是非 雨打蕉叶 又潇潇了几夜 我等春雷 来提醒你爱谁 (样例说明 请注意观察样例输出从第二行起，每行开头为一个空格，请仔细思考这是为什么。)

解题报告

没什么好解释的，送分题目。细心即可。

题目四、心灵的抚慰

背景 Background 病毒问题解决后，神牛们的心灵久久不能平静。有个神牛因此已经「乱了」。他脑子中满是程序（否则怎么会成为神牛呢），而且他可以从一个程序联想到一些相似的程序。比如从程序1联想到2，从2联想到4，从4联想到6，从6联想到9……躺就像搜索一样一步一步越陷越深。不过同一种联想他只会联想一次。比如1、2之间他进行了一次联想，那么他不会再重新联想1到2，或2到1。眼看他又要乱了，有人突然想到，如果他刚开始时想到的程序能够经过联想若干次后联想回到原程序，那不就乱回来了吗？由于神牛马上就要开乱，请在1秒内告诉他，他需要想哪个程序，以便乱回来。 题目描述 Description 给出一些程序和他们互相联想的关系（如果两个程序A、B有联系，神牛可以从A联想到B，也可以从B联想到A，但A、B之间神牛最多联想一次），请告诉神牛他需要想哪个程序，以便在最短的时间内乱回来，并输出这个最短时间。 数据范围 对于100% 的数据，n≤250。

输入第一行有两个正整数N，M，分别表示程序个数和有多少对程序可以被神牛直接互相联想。 以下M行，每行三个正整数，分别表示一种联想的两端的程序的编号（从1开始），以及进行这种联想所需要的最短时间。

输出：如果神牛无论如何都再也乱不回来了，输出「He will never come back.」。 如果神牛能够乱回来，请输出神牛会乱多长时间。

例如输入：

4 3 1 2 10 1 3 20 1 4 30

输出：

He will never come back.

题解

本题是一个典型的求图中最小环算法。 算法的主旨是： 1、用Floyed算法求出点到点最短距离。枚举中间节点，再枚举两边节点（注意枚举顺序），若两边节点到其距离之和比原来两点之和小，则执行松弛操作，更新两边节点距离。 2、再枚举三个节点，看这三个点绕一圈所需时间（d

\[a,b\]

+dis

\[b,c\]

+d

\[c,a\]

），更新最小值。可以证明，任意一个环都可以经过Floyed点对点简化后形成一个由一条松弛后的边和两条原始边构成的三角形。注意，三条边至多有一条是松弛后的，否则有可能重复路径，形成直线往返。若环不存在，则输出无解。 此算法同样适用于有向图，只是需要注意绕圈方向严格（下面的程序中不是严格绕圈，应修改为首尾相接）

更多信息请到 RQNOJ (点击进入) 查阅。

题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。