分析如DNA 序列这样的生命科学数据是计算机的一个有趣应用。从生物学
的角度上说，DNA 是一种由腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶这四种核苷酸
组成的链式结构。这四种核苷酸分别用大写字母A、C、G、T 表示。这样，一
条DNA 单链可以被表示为一个只含以上四种字符的字符串。我们将这样的字符
串称作一个DNA 序列。
有时生物学家可能无法确定一条DNA 单链中的某些核苷酸。在这种情况下，
字符N 将被用来表示一个不确定的核苷酸。换句话说，N 可以用来表示A、C、
G、T 中的任何一个字符。我们称包含一个或者多个N 的DNA 序列为未完成序
列；反之，就称作完成序列。如果一个完成序列可以通过将一个未完成序列中的
每个N 任意替换成A、C、G、T 得到的话，就称完成序列适合这个未完成序列。
举例来说，ACCCT 适合ACNNT，但是AGGAT 不适合。
研究者们经常按照如下方式排序四种核苷酸：A 优先于C，C 优先于G，G
优先于T。如果一个DNA 序列中的每个核苷酸都与其右边的相同或者优先，就
将其归类为范式-1。举例来说，AACCGT 是范式-1，但是AACGTC 不是。
一般来说，一个DNA 序列属于范式-j ( j > 1)，只要它属于范式-( j-1)或者是
一个范式-( j-1)和一个范式-1 的连接。举例来说，AACCC、ACACC 和ACACA
都是范式-3，但GCACAC 和ACACACA 不是。
同样，研究者们按照字典序对DNA 序列进行排序。按照这个定义，最小的
属于范式-3 的DNA 序列是AAAAA，最大的是TTTTT。这里是另外一个例子，
考虑未完成序列ACANNCNNG。那么前7 个适合这个未完成序列的DNA 序列
是：
ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG
写一个程序，找到按字典序的第R 个适合给定的长度为M 的未完成序列的
范式-K。
R(1≤R≤2×10^12)。第二行包含一个长度为M 的字符串，表示未完成序列。保证适
合该未完成序列的范式-K 的总数不超过4×10^18，因此该数可以用C 和C++中的
long long 类型或者Pascal 中的Int64 类型表示。同时，R 不会超过适合给定未完
成序列的范式-K 的总数。
9 3 5 ACANNCNNG 5 4 10 ACANN
ACAAACCCG ACAGC
公開 測資點#0 (6%): 1.0s , <1K
公開 測資點#1 (7%): 1.0s , <1K
公開 測資點#2 (7%): 1.0s , <1K
公開 測資點#3 (6%): 1.0s , <1K
公開 測資點#4 (7%): 1.0s , <1K
公開 測資點#5 (7%): 1.0s , <1M
公開 測資點#6 (6%): 1.0s , <1K
公開 測資點#7 (7%): 1.0s , <1K
公開 測資點#8 (7%): 1.0s , <1K
公開 測資點#9 (6%): 1.0s , <1K
公開 測資點#10 (7%): 1.0s , <1M
公開 測資點#11 (7%): 1.0s , <1M
公開 測資點#12 (6%): 1.0s , <1M
公開 測資點#13 (7%): 1.0s , <1K
公開 測資點#14 (7%): 1.0s , <1M
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||