NOI2015_day2VIP专享VIP免费

第3 2 届全国信息学奥林匹克竞赛 CCF NOI 2015 第二试 竞赛时间：2015 年7 月19 日8:00-13:00 题目名称 荷马史诗 品酒大会 小园丁与老司机 目录 epic sav ou r farm 可执行文件名 epic sav ou r farm 输入文件名 epic.in sav ou r.in farm.in 输出文件名 epic.ou t sav ou r.ou t farm.ou t 每个测试点时限 1 秒 1 秒 1 秒 内存限制 512MB 512MB 512MB 测试点数目 20 20 20 每个测试点分值 5 5 5 是否有部分分 是 否 是 题目类型 传统型 传统型 传统型 是否有附加文件 是 是 是 提交源程序须加后缀 对于 Pascal 语言 epic.pas sav ou r.pas farm.pas 对于 C 语言 epic.c sav ou r.c farm.c 对于 C++ 语言 epic.cpp sav ou r.cpp farm.cpp 注意：最终测试时，所有编译命令均不打开任何优化开关。 第32 届全国信息学奥林匹克竞赛 第二试 荷马史诗 第2 页 共11 页 荷马史诗 【问题描述】 追逐影子的人，自己就是影子 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。 一部《荷马史诗》中有 ᵅ 种不同的单词，从 1 到 ᵅ 进行编号。其中第 ᵅ 种单词出现的总次数为 ᵆᵅ 。Allison 想要用 ᵅ 进制串 ᵆᵅ 来替换第 ᵅ 种单词，使得其满足如下要求： 对于任意的 1≤ ᵅ, ᵅ ≤ ᵅ ， ᵅ≠ ᵅ ，都有： ᵆᵅ 不是 ᵆᵅ 的前缀。 现在 Allison 想要知道，如何选择 ᵆᵅ ，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的 ᵆᵅ 的最短长度是多少？ 一个字符串被称为 ᵅ 进制字符串，当且仅 当它的每 个字符是 0 到 ᵅ− 1 之 间（ 包 括 0 和 ᵅ− 1 ） 的整 数。 字符串 ᵄᵆᵅ1 被称为字符串 ᵄᵆᵅ2 的前缀，当且仅 当：存 在 1≤ ᵆ ≤ ᵅ ，使得 ᵄᵆᵅ1 = ᵄᵆᵅ2[1..ᵆ] 。其中， ᵅ 是字符串 ᵄᵆᵅ2 的长度， ᵄᵆᵅ2[1..ᵆ] 表 示 ᵄᵆᵅ2 的前 ᵆ 个字符组成的字符串。 【输入格式】 从文件 epic.in 中读入 数据 。 输 入 文件 的第 1 行包 含 2 个正 整 数 ...