| 题目名称 | 3162. 金字塔 |
|---|---|
| 输入输出 | ZYH.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 LGLJ
于2019-06-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：17， 提交：40， 通过率：42.5% | ||||
 LGLJ |
100 | 0.047 s | 2.85 MiB | C++ |
 Hale |
100 | 0.106 s | 14.94 MiB | C++ |
 会挽弯弓满月 |
100 | 0.108 s | 3.75 MiB | C++ |
|
徐诗畅 |
100 | 0.111 s | 3.90 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.118 s | 14.35 MiB | C++ |
|
dsn |
100 | 0.133 s | 1.22 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.134 s | 2.70 MiB | C++ |
|
郑霁桓 |
100 | 0.136 s | 3.58 MiB | C++ |
|
梦那边的美好ET |
100 | 0.136 s | 3.89 MiB | C++ |
|
梦那边的美好ET |
100 | 0.142 s | 3.89 MiB | C++ |
| 本题关联比赛 | |||
| 2024国庆练习3 | |||
| 关于 金字塔 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
第六个测试点字符串长度不止是300！！！，数组必须开大！！！
| ||||
|
人生最绝望的事不过是在测试数据中间卡了一个点QAQ
| ||||
|
真的搞不懂抄别人代码，改改变量名就过的人的素质和目的在哪里
LGLJ
2019-06-07 11:38
2楼
| ||||
|
我恨windows批处理文件，乱改文件名以及cogs上传数据更新不了！！！！
LGLJ
2019-06-06 10:46
1楼
| ||||
【题目描述】
虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。首先，金字塔由若干房间组成，房间之间连有通道。如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。并且，每个房间的墙壁都涂有若干种颜色的一种。
探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。最后，机器人会从入口退出金字塔。
显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。因为结果可能会非常大，你只需要输出答案对$10^9$ 取模之后的值。
【输入格式】
输入文件包含一行，一个字符串$S$，长度不超过$300$，表示机器人得到的颜色序列。
【输出格式】
输出一个整数表示答案。
【样例输入】
ABABABA
【样例输出】
5
【提示】
例如序列“ABABABA”对应5种金字塔结构，最底部是树根。我们认为子树之间是有序的，所以方案3和4是两种不同的方案。如书中图所示。
【来源】
《算法竞赛进阶指南》