P2856 [USACO06FEB]手机Cellphones

    • 2通过
    • 46提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 前缀和 线段树 贪心 USACO 2006
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    The cows have started using cellphones to cowmunicate with each other, but have found that the button layout doesn't suit their hooves very well. They are designing a special cellphone with fewer but larger buttons.

    One feature they liked on the standard cellphones was predictive text. Each button has a few letters associated with it, and one types a word by pushing the associated buttons. Because there is more than one letter for each button, this can be ambiguous for some words. However, most of the time the ambiguity can be resolved by using a dictionary to determine what word the user wanted.

    Since the cows are designing a custom cellphone, they are also going to replace the English alphabet with the Cow alphabet. By an amazing coincidence, the cow alphabet is simply the first L (1 <= L <= 26) letters of the English alphabet, in the same order. They want to find out how to assign the letters of the Cow alphabet to the B buttons (1 <= B <= L) in such a way that the maximum number of words in their dictionary are unambiguous when entered with predictive text. Like normal cellphones, they want the letters on each button to be a contiguous section (one or more consecutive letters) of the alphabet.

    奶牛的名字都是由英文字母表的前1(1 < K 26)个字母构成的.现在想设计一种手机, 有个按键.请你把这L个字母按顺序分配给B个按键,使能够通过按这些键而唯一确 定的奶牛数尽量多.

    输入输出格式

    输入格式:

    Line 1: Two space-separated integers: B and L

    Line 2: D, the number of words in the dictionary (1 <= D <= 1000)

    Lines 3..D+2: Each line contains one word from the dictionary in upper case and of length 1..10 characters. The words are presented in alphabetical order and with no duplicates.

    输出格式:

    Line 1: The number of words in the Cow dictionary that have unique button sequences.

    Lines 2..B+1: The nth line contains the letters that appear on button n, in upper case and alphabetical order. The lines must be listed in alphabetical order, and every Cow letter must appear exactly once. If there is more than one optimal solution, use the one that places the most letters on button 1. Ties are broken by placing the most letters on button 2, etc.

    输入输出样例

    输入样例#1: 复制
    3 13
    11
    ALL
    BALL
    BELL
    CALK
    CALL
    CELL
    DILL
    FILL
    FILM
    ILL
    MILK
    输出样例#1: 复制
    7
    AB
    CDEFGHIJK
    LM

    说明

    Explanation of the sample:

    Button 1 contains AB, button two contains C-K, and button 3 contains LM. The words CELL, DILL, FILL and FILM are all entered as 2233, while the remaining 7 words are all entered uniquely.

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