P2753 [USACO4.3]字母游戏Letter Game

    • 171通过
    • 428提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    在家里用电视机做字母游戏是很流行的,其中一种玩法是:每一个字母有一个数值与之对应.你收集字母组成一个或多个词以得到尽可能高的得分.除非你已有了 “找词的方法”(“a way with words”),你会把你知道的字都试一遍.有时你也许会查阅其拼写,然后计算得分。显然可以用计算机更为准确地完成此任务。上图示出了英文字母及其所对应的值,当给出英文单词(word) 的表列及收集的字母时,请找出所能形成的得分最高的词或词对(pairs of words)。

    输入输出格式

    输入格式:

    (file lgame.in)

    输入文件lgame.in中有一行由小写字母(a'到z')组成的字符串, 这就是收集到字母(就是可以使用的字母),字符串由至少3个字母至多7个字母(以任意顺序) 组成。

    (file lgame.dict)

    词典文件lgame.dict由至多40,000行组成,文件的最后一行有'.' 表示文件的结束。其它各行每一行都是由至少3个小写字母,至多7 个小写字母组成的字符串。文件中的词已按字典顺序排序。

    (管理员注:读入不用开文件,先读.in,再读.dict)

    输出格式:

    (file lgame.out)

    在文件lgame.out的第一行,你的程序应写上最高得分(子任务A).使用上面图形中给出的字母-值对应表。

    随后的每一行是由文件lgame.dict中查到的具有这个得分的所有的词和或词对(word pairs)(子任务B)。要利用图中给定的字母的值。

    当两个词能够形成 一个组合(具有给定的字母)时,这两个词应该打印到同一行,两个词中间用一个空格隔开。不许重复表示词对,例如'rag prom'和'prom rag'是同样的词对,只输出字典顺序较小的那个。

    输出要按照字典顺序排序,如果两个词对第一个单词的顺序相同,则按照第二个单词。一个词对中的两个单词可以相同。

    输入输出样例

    输入样例#1: 复制
    SAMPLE INPUT(file lgame.in)
    
    prmgroa
    [编辑] SAMPLE INPUT(file lgame.dict)
    
    profile
    program
    prom
    rag
    ram
    rom
    .
    输出样例#1: 复制
    24
    program
    prom rag

    说明

    样例输入请参考原题

    题目翻译来自NOCOW。

    USACO Training Section 4.3

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。