#P4606. [Apio2008]DNA
[Apio2008]DNA
[APIO2008] DNA
题目描述
DNA 单链由腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶组成,分别用大写字母 A、C、G、T 表示。一条 DNA 单链可以写成由这四种字母组成的序列。
字母 N 表示未知的核苷酸,可以独立替换为四种字母中的任意一种。原序列称为待补全序列,替换后得到与之匹配的完整序列。例如 ACCCT 与 ACNNT 匹配,AGGAT 与它不匹配。
以 A、C、G、T 为从小到大的顺序,定义下列范式。
- 一个序列属于范式 ,当且仅当每个字母都不大于它右侧紧邻的字母。例如
AACCGT属于范式 ,AACGTC不属于。 - 对 ,一个序列如果属于范式 ,或者可以由一个范式 的序列接上一个范式 的序列得到,则它属于范式 。例如
AACCC、ACACC和ACACA都属于范式 ,GCACAC和ACACACA不属于。
长度为 的范式 序列中,字典序最小的是 AAAAA,最大的是 TTTTT。给定待补全序列 ACANNCNNG,与它匹配的前七个范式 序列为:
ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG
给定一个长度为 的待补全序列,求与之匹配的所有范式 完整序列中字典序第 小的一个。
输入格式
第一行三个整数 。第二行一个长度为 的字符串,由 A、C、G、T、N 组成。
输出格式
输出一行,表示要求的完整序列。
9 3 5
ACANNCNNG
ACAAACCCG
5 4 10
ACANN
ACAGC
数据范围
,,。保证匹配的范式 完整序列至少有 个,至多有 个。计数可用有符号 64 位整数表示。
原赛中, 的测试占 分。每个测试点按输出是否正确给满分或零分。