2015 NOI全国赛第二试：荷马史诗编码挑战

"NOI2015day2竞赛中的'荷马史诗'题目是一道来自CCFNOI2015的信息学奥林匹克传统型问题，主要考察参赛者的算法设计和字符串处理能力。该题目背景设定在Allison对《荷马史诗》的阅读兴趣上，她希望通过某种编码方式压缩这部作品，同时保持不同单词的独特性。 首先，问题的关键在于确定如何将n种不同单词（编号从1到n，各单词出现次数由𝑤𝑖给出）用𝑘进制字符串𝑠𝑖替换，使得新版本的史诗中没有两个单词的前缀相同。这是一个经典的字符串处理问题，需要考虑字符串的前缀性质以及进制转换的规则。 输入格式要求从epic.in文件中读取数值，这些数值可能包括n（单词种类数量）、wi（第i种单词的出现次数）以及可能的k（进制数），这些都是解决此问题的基础数据。参赛者需要编写程序来计算最小长度的新史诗，并找到满足条件的最短的最长字符串si的长度。 为了实现这一目标，选手需要设计一种策略来生成每个单词的替代串，同时检查它们是否满足无前缀相同的条件。这可能涉及到动态规划或者字典树等数据结构，以高效地处理字符串比较和查找。此外，因为每个测试点有1秒的时间限制和512MB的内存限制，选手还需要考虑算法的时间复杂性和空间效率。 题目类型为传统型，意味着它强调基础算法技巧和逻辑推理，而不是依赖于特定库或高级编程特性。参赛者需要提交Pascal、C或C++语言编写的源程序，但要注意编译时不开启任何优化开关，以保证比赛公平性。 最后，题目还包含有部分分数的机制，这意味着即使不能完全解决问题，部分解答也可能得分，因此策略选择和解题思路的灵活性也非常重要。这道题目不仅考察了参赛者的编程技能，还锻炼了他们的问题解决和抽象思维能力。"