P2377 三角形图

    • 1通过
    • 2提交
  • 题目提供者 一UNowen一
  • 评测方式 云端评测
  • 标签 字符串 模拟 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    模拟赛一道难过到我的题

    题目描述

    一个三角形网格上,每个小三角形的面积都为1。你可以从某个点开始,沿着边走出一个多边形来,使得围成一定的面积。我们可以给每个点定义5个方向:

    a 左转120°

    b 左转60°

    c 直走

    d 右转60°

    e 右转120°

    这样的话,一个图形就能被一组字母表示出来。 比如左边的图,从A点开始顺时针走,则可以表示为dcddeaddd;从B点开始顺时针走,则可以表示ddeaddddc;……。右图显示的是左图翻折后的情况。

    左图和右图是本质相同的图形。为了惟一地表示一类全等的图形,我们在这类图形的所有表示方法中找字典序最小的表示方法来代表这一类全等的图形。左图和右图的最小表示方法相同,都是addddcdde。

    现在告诉你一个图形的某个表示法(不一定是最小表示方法),请你求出在这个图形的基础上加一个小三角形后合法图形的个数,以及他们的最小表示方法。

    一个图形是合法的,当且仅当组成它的所有小三角形均有至少一条与其他三角形公共的边,且不存在中空。

    下面的图形都是不合法的:

    输入输出格式

    输入格式:

    第一行1个数字T,表示数据组数。

    接下来T行每行一个字符串,表示某个图形的某个表示方法。

    读入数据保证一定合法,且一定是顺时针的表示方法。

    输出格式:

    对于每组数据:

    第一行1个整数K,表示加一个小三角形后的不全等的图形的个数。

    接下来一行K个字符串,表示这K个不同图形的最小表示方法(按字典序排序),字符串两两之间用一个空格隔开,最小表示方法必须是顺时针的。

    两组数据间用一个空行隔开。

    输入输出样例

    输入样例#1: 复制
    Sample Input 1:
    2
    eee
    cedde
    Sample Input 2:
    2
    adeccecced
    dddddd
    输出样例#1: 复制
    Sample Output 1:
    1
    dede
    
    3
    beddde cdecde cecece
    Sample Output 2:
    5
    acedccecced addebcecced adebebecced adecbedcced cceccecce
    
    1
    cddddce

    说明

    样例解释

    Sample 1 的解释:

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