P2750 [USACO5.5]贰五语言Two Five

    • 616通过
    • 1.1K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 概率论,统计 深度优先搜索,DFS IOI USACO 2001(或之前)
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有一种奇怪的语言叫做“贰五语言”。它的每个单词都由A~Y这25个字母各一个组成。但是,并不是任何一种排列都是一个合法的贰五语言单词。贰五语言的单词必须满足这样一个条件:把它的25个字母排成一个5*5的矩阵,它的每一行和每一列都必须是递增的。比如单词ACEPTBDHQUFJMRWGKNSXILOVY,它排成的矩阵如下所示:

    A C E P T

    B D H Q U

    F J M R W

    G K N S X

    I L O V Y

    因为它的每行每列都是递增的,所以它是一个合法的单词。而单词YXWVUTSRQPONMLKJIHGFEDCBA则显然不合法。 由于单词太长存储不便,需要给每一个单词编一个码。编码方法如下:从左到右,再从上到下,可以由一个矩阵的得到一个单词,再把单词按照字典顺序排序。比如,单词ABCDEFGHIJKLMNOPQRSTUVWXY的编码为1,而单词ABCDEFGHIJKLMNOPQRSUTVWXY的编码为2。

    现在,你需要编一个程序,完成单词与编码间的转换。

    输入输出格式

    输入格式:

    第一行为一个字母N或W。N表示把编码转换为单词,W表示把单词转换为编码。

    若第一行为N,则第二行为一个整数,表示单词的编码。若第一行为W,则第二行为一个合法的单词。

    输出格式:

    每行一个整数或单词。

    输入输出样例

    输入样例#1: 复制
    N
    2
    输出样例#1: 复制
    ABCDEFGHIJKLMNOPQRSUTVWXY
    输入样例#2: 复制
    W 
    ABCDEFGHIJKLMNOPQRSUTVWXY
    输出样例#2: 复制
    2

    说明

    题目翻译来自NOCOW。

    USACO Training Section 5.5

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