http://rosalind.info/problems/as-graph/
http://en.wikipedia.org/wiki/Bioinformatics
字符串处理、正则表达式
s = gets
print [s.count('A'), s.count('C'), s.count('G'), s.count('T')] * ' '
print gets.gsub('T','U')
s = gets
s.gsub!('A','a'); s.gsub!('T','A'); s.gsub!('a','T')
s.gsub!('C','c'); s.gsub!('G','C'); s.gsub!('c','G')
print s.reverse
$buf = gets()
def gc(s)
gcc = 0.0
s.each_char{|si|
gcc += 1 if (si == 'G' || si == 'C')
}
return gcc / s.size
end
def getdna()
dna = gets().chomp
dna += $buf.chomp while ($buf = gets()) && ($buf[0] != '>')
return dna
end
dna = "$"
while $buf do
_id, _dna = $buf[1..-1], getdna()
id, dna = _id, _dna if gc(_dna) > gc(dna)
end
puts id
print gc(dna) * 100, '%'
s = gets.chomp; t = gets.chomp; dist = 0
0.upto(s.size-1){|i|
dist += 1 if s[i] != t[i]
}
p dist
s = gets.chomp; n = s.length; a = Array.new(n){Hash.new(0)}
begin
0.upto(n-1){|i|
a[i][s[i]] += 1
}
end while s = gets
def scan(a, n, ch)
print ch,':'
0.upto(n-1){|i|
print ' ', a[i][ch]
}
puts
end
def common(ai)
return 'A' if (ai['A'] >= ai['C'] && ai['A'] >= ai['G'] && ai['A'] >= ai['T'])
return 'C' if (ai['C'] >= ai['A'] && ai['C'] >= ai['G'] && ai['C'] >= ai['T'])
return 'G' if (ai['G'] >= ai['A'] && ai['G'] >= ai['C'] && ai['G'] >= ai['T'])
return 'T'
end
a.each{|ai|
#ai.sort_by{|key, value| value}
#print ai.begin().value
print common(ai)
}
puts
scan(a, n, 'A'); scan(a, n, 'C'); scan(a, n, 'G'); scan(a, n, 'T')
/* .................................................................................................................................. */
const int N = 1009;
pair<string, string> A[N];
int n;
bool adj(string a, string b, int k){
if (a == b) return false;
REP(i, k) if (a[SZ(a)-k+i] != b[i]) return false;
return true;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
string id, dna; cin >> id; while (id[0] == '>'){
ERS(id, 0), A[n].fi = id, CLR(dna);
while (cin >> id && id[0] != '>') dna += id;
A[n++].se = dna;
}
REP_2(i, j, n, n) if (adj(A[i].se, A[j].se, 3)){
cout << A[i].fi << " " << A[j].fi << endl;
}
}
dict = {
'UCA' => 'S', # Serine
'UCC' => 'S', # Serine
'UCG' => 'S', # Serine
'UCU' => 'S', # Serine
'UUC' => 'F', # Phenylalanine
'UUU' => 'F', # Phenylalanine
'UUA' => 'L', # Leucine
'UUG' => 'L', # Leucine
'UAC' => 'Y', # Uyrosine
'UAU' => 'Y', # Uyrosine
'UAA' => '_', # Stop
'UAG' => '_', # Stop
'UGC' => 'C', # Cysteine
'UGU' => 'C', # Cysteine
'UGA' => '_', # Stop
'UGG' => 'W', # Uryptophan
'CUA' => 'L', # Leucine
'CUC' => 'L', # Leucine
'CUG' => 'L', # Leucine
'CUU' => 'L', # Leucine
'CCA' => 'P', # Proline
'CCC' => 'P', # Proline
'CCG' => 'P', # Proline
'CCU' => 'P', # Proline
'CAC' => 'H', # Histidine
'CAU' => 'H', # Histidine
'CAA' => 'Q', # Glutamine
'CAG' => 'Q', # Glutamine
'CGA' => 'R', # Arginine
'CGC' => 'R', # Arginine
'CGG' => 'R', # Arginine
'CGU' => 'R', # Arginine
'AUA' => 'I', # Isoleucine
'AUC' => 'I', # Isoleucine
'AUU' => 'I', # Isoleucine
'AUG' => 'M', # Methionine
'ACA' => 'T', # Uhreonine
'ACC' => 'T', # Uhreonine
'ACG' => 'T', # Uhreonine
'ACU' => 'T', # Uhreonine
'AAC' => 'N', # Asparagine
'AAU' => 'N', # Asparagine
'AAA' => 'K', # Lysine
'AAG' => 'K', # Lysine
'AGC' => 'S', # Serine
'AGU' => 'S', # Serine
'AGA' => 'R', # Arginine
'AGG' => 'R', # Arginine
'GUA' => 'V', # Valine
'GUC' => 'V', # Valine
'GUG' => 'V', # Valine
'GUU' => 'V', # Valine
'GCA' => 'A', # Alanine
'GCC' => 'A', # Alanine
'GCG' => 'A', # Alanine
'GCU' => 'A', # Alanine
'GAC' => 'D', # Aspartic Acid
'GAU' => 'D', # Aspartic Acid
'GAA' => 'E', # Glutamic Acid
'GAG' => 'E', # Glutamic Acid
'GGA' => 'G', # Glycine
'GGC' => 'G', # Glycine
'GGG' => 'G', # Glycine
'GGU' => 'G' # Glycine
};
mRNA = gets.chomp
puts mRNA.gsub(/\w{3}/).each(&dict.method(:[]))[0..-1].gsub(/_.*/, '')
。。。mRNA、蛋白质（Protein）、氨基酸（Amino Acid）、密码子（Genetic Code）。。。
dict = {
'TCA' => 'S', # Serine
'TCC' => 'S', # Serine
'TCG' => 'S', # Serine
'TCT' => 'S', # Serine
'TTC' => 'F', # Phenylalanine
'TTT' => 'F', # Phenylalanine
'TTA' => 'L', # Leucine
'TTG' => 'L', # Leucine
'TAC' => 'Y', # Tyrosine
'TAT' => 'Y', # Tyrosine
'TAA' => '_', # Stop
'TAG' => '_', # Stop
'TGC' => 'C', # Cysteine
'TGT' => 'C', # Cysteine
'TGA' => '_', # Stop
'TGG' => 'W', # Tryptophan
'CTA' => 'L', # Leucine
'CTC' => 'L', # Leucine
'CTG' => 'L', # Leucine
'CTT' => 'L', # Leucine
'CCA' => 'P', # Proline
'CCC' => 'P', # Proline
'CCG' => 'P', # Proline
'CCT' => 'P', # Proline
'CAC' => 'H', # Histidine
'CAT' => 'H', # Histidine
'CAA' => 'Q', # Glutamine
'CAG' => 'Q', # Glutamine
'CGA' => 'R', # Arginine
'CGC' => 'R', # Arginine
'CGG' => 'R', # Arginine
'CGT' => 'R', # Arginine
'ATA' => 'I', # Isoleucine
'ATC' => 'I', # Isoleucine
'ATT' => 'I', # Isoleucine
'ATG' => 'M', # Methionine
'ACA' => 'T', # Threonine
'ACC' => 'T', # Threonine
'ACG' => 'T', # Threonine
'ACT' => 'T', # Threonine
'AAC' => 'N', # Asparagine
'AAT' => 'N', # Asparagine
'AAA' => 'K', # Lysine
'AAG' => 'K', # Lysine
'AGC' => 'S', # Serine
'AGT' => 'S', # Serine
'AGA' => 'R', # Arginine
'AGG' => 'R', # Arginine
'GTA' => 'V', # Valine
'GTC' => 'V', # Valine
'GTG' => 'V', # Valine
'GTT' => 'V', # Valine
'GCA' => 'A', # Alanine
'GCC' => 'A', # Alanine
'GCG' => 'A', # Alanine
'GCT' => 'A', # Alanine
'GAC' => 'D', # Aspartic Acid
'GAT' => 'D', # Aspartic Acid
'GAA' => 'E', # Glutamic Acid
'GAG' => 'E', # Glutamic Acid
'GGA' => 'G', # Glycine
'GGC' => 'G', # Glycine
'GGG' => 'G', # Glycine
'GGT' => 'G' # Glycine
};
dna = gets.chomp
while exon = gets do
dna.gsub!(exon.chomp, '')
end
puts dna.gsub(/\w{3}/).each(&dict.method(:[]))[0..-1].gsub(/_.*/, '')
s = gets.chomp; n = s.length
def cp(a, b)
return a == 'G' && b == 'C' || a == 'C' && b == 'G' || a == 'A' && b == 'T' || a == 'T' && b == 'A'
end
def test(s)
n = s.length
0.upto(n/2){|i|
return false if !cp(s[i], s[n-1-i])
}
return true
end
4.upto(8){|len|
next if len.odd?
0.upto(n-len){|l|
r = l + len - 1
print l+1, ' ', len, "\n" if (test(s[l..r]))
}
}
概率
I =->{gets.split.map &:to_f}
I[].each{|ai|
p (ai**2 + (1-ai)**2) / 2
}
I =->{gets.split.map &:to_f}
m, n = I[]
I[].each{|ai|
p (n - m + 1) * ((ai**2 + (1-ai)**2) / 2) ** m
}
字符串匹配
T = gets().chomp
P = gets().chomp
Tn, Pn = T.length, P.length
Pi = []; Pi[0] = j = -1
0.upto(Pn-1){|i|
j = Pi[j] while (j >= 0 && P[i] != P[j])
i += 1; j += 1; Pi[i] = P[i] == P[j] ? Pi[j] : j
}
j = 0
0.upto(Tn-1){|i|
j = Pi[j] while (j >= 0 && T[i] != P[j])
i += 1; j += 1; p i-Pn+1 if j == Pn
}
P = gets().chomp + '$' Pn = P.length Pi = []; Pi[0], Pi[1], i, j = -1, 0, 2, 0 while (i < Pn) do if (P[i-1] == P[j]) then j +=1; Pi[i] = j; i += 1 else if (j > 0) then j = Pi[j] else Pi[i] = 0; i += 1 end end end puts Pi[1..-1]*' '
s = gets.chomp
t = gets.chomp
i = 0; t.each_char{|ti|
i += 1 while s[i] != ti; i += 1;
p i
}
/* .................................................................................................................................. */
const int N = 1009;
string S[N]; int dp[N][N];
int n;
void check(string s){
FOR(i, 1, n) if (S[i].find(s) == string::npos) return;
OT(s), exit(0);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
string s; while (cin >> s){
S[n++] = s;
}
FOR(i, 1, n) if (SZ(S[i]) < SZ(S[0])) swap(S[0], S[i]);
int n0 = SZ(S[0]); DWN(len, n0-1, 0){
REP(i, n0-len){
s = S[0].substr(i, len);
check(s);
}
}
}
生成排列、组合
/* .................................................................................................................................. */
const int N = 10;
int A[N];
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, f = 1; REP_1_C(i, RD(n)) A[i] = i, f *= i;
printf("%d\n", f); DO(f){
REP_1(i, n) OT(A[i]);
next_permutation(A + 1, A + n + 1);
puts("");
}
}
/* .................................................................................................................................. */
const int N = 10;
int A[N];
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, f = 1; REP_1_C(i, RD(n)) A[i] = i, f *= i;
printf("%d\n", f*_1(n)); DO(f){
REP(s, _1(n)){
REP_1(j, n){
if (!_1(s, (n-j))) putchar('-');
OT(A[j]);
}
puts("");
}
next_permutation(A + 1, A + n + 1);
}
}
/* .................................................................................................................................. */
const int N = 10;
char S[N]; int A[N];
int n; LL k;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
char str[100]; gets(str);
REP_C(i, strlen(str)) if (str[i] != ' ') S[n++] = str[i];
RD(k); DO(pow(n, k)){
DWN(i, k, 0) putchar(S[A[i]]); puts("");
A[0]++; for (int i=0;A[i]==n;A[i]=0,++A[++i]);
}
}
/* .................................................................................................................................. */
const int N = 15;
char C[N]; int A[N];
int n, k;
void dfs(int dep = 0){
if (dep){
REP(i, dep) putchar(i[A][C]);
puts("");
}
if (dep == k) return;
REP(i, n) A[dep]=i, dfs(dep+1);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
char str[109]; REP_C(i, strlen(gets(str))) if (str[i] != ' ')
C[n++] = str[i];
RD(k);
dfs();
}
搜索
/* .................................................................................................................................. */
const int F[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
const int N = 10, L = 3628800;
int n = 10;
int D[L]; int a[N], st, ed; bool c[N];
int encode(){ // Cantor
int x = 0; REP(i, n){
int t = 0; FOR(j, i+1, n)
if (a[i]>a[j]) ++t;
x = x * (n-i) + t;
}
return x;
}
void decode(int x){
RST(a, c); REP(i, n){
while (i[a][c]) ++a[i];
while (x >= F[n-i-1]){
x -= F[n-i-1]; ++a[i];
while (i[a][c]) ++a[i];
}
i[a][c] = true;
}
}
void rev(int l, int r){
REP(i, (r - l + 1) / 2)
swap(a[l+i], a[r-i]);
}
int Q[L], cz, op; int bfs(){
if (st == ed) return 0;
Q[cz = 0] = st, op = 1;
RST(D); D[st] = 1;
while (cz < op){
int u = Q[cz++]; decode(u);
FOR(len, 1, n){
REP(l, n - len){
int r = l + len; rev(l, r); int v = encode(); rev(l, r);
if (D[v]) continue;
if (v == ed) return D[u];
Q[op++] = v;
D[v] = D[u] + 1;
}
}
}
return -1;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
while (~scanf("%d", &a[0])){
FOR(i, 1, n) --RD(a[i]); st = encode();
REP(i, n) --RD(a[i]); ed = encode();
OT(bfs());
}
}
/* .................................................................................................................................. */
template<class T1, class T2> ostream& operator <<(ostream& cout, const pair<T1, T2> &rhs){
cout << rhs.fi+1 << " " << rhs.se+1;
return cout;
}
const int F[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
const int N = 10, L = 3628800;
int n = 10;
int D[L], pre[L]; PII opt[L]; int a[N], st, ed; bool c[N];
int encode(){ // Cantor
int x = 0; REP(i, n){
int t = 0; FOR(j, i+1, n)
if (a[i]>a[j]) ++t;
x = x * (n-i) + t;
}
return x;
}
void decode(int x){
RST(a, c); REP(i, n){
while (i[a][c]) ++a[i];
while (x >= F[n-i-1]){
x -= F[n-i-1]; ++a[i];
while (i[a][c]) ++a[i];
}
i[a][c] = true;
}
}
void rev(int l, int r){
REP(i, (r - l + 1) / 2)
swap(a[l+i], a[r-i]);
}
void print_path(int v){
if (v == st) return;
print_path(pre[v]);
cout << opt[v] << endl;
}
int Q[L], cz, op; void bfs(){
if (st == ed) {puts(0); return;}
Q[cz = 0] = st, op = 1;
RST(D); D[st] = 1;
while (cz < op){
int u = Q[cz++]; decode(u);
FOR(len, 1, n){
REP(l, n - len){
int r = l + len; rev(l, r); int v = encode(); rev(l, r);
if (D[v]) continue; opt[v] = MP(l, r), pre[v] = u;
if (v == ed){OT(D[u]), print_path(v); return;}
Q[op++] = v, D[v] = D[u] + 1;
}
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
while (~scanf("%d", &a[0])){
FOR(i, 1, n) --RD(a[i]); st = encode();
REP(i, n) --RD(a[i]); ed = encode();
bfs();
}
}
动态规划
/* .................................................................................................................................. */
const int N = 1009;
char A[N], B[N];
int dp[N][N], n, m;
void print_path(int i, int j){
if (!i || !j) return;
if (A[i] == B[j] && dp[i][j] == dp[i-1][j-1] + 1){
print_path(i-1, j-1), putchar(A[i]);
}
else if (dp[i-1][j] > dp[i][j-1]){
print_path(i-1, j);
}
else{
print_path(i, j-1);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
RS(A+1), RS(B+1), n = strlen(A+1), m = strlen(B+1);
REP_2_1(i, j, n, m){
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if (A[i] == B[j]) checkMax(dp[i][j], dp[i-1][j-1] + 1);
}
print_path(n, m);
}
s = gets.chomp; n = s.length; s = '$' + s
t = gets.chomp; m = t.length; t = '$' + t
dp = Array.new(n+1){Array.new(m+1){0}}
def min(a, b)
return a < b ? a : b
end
1.upto(n){|i|
dp[0][i] = dp[i][0] = i
}
1.upto(n){|i|
1.upto(m){|j|
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1] + (s[i] != t[j] ? 1 : 0))
}
}
p dp[n][m]
s = gets.chomp; n = s.length; s = '$' + s
t = gets.chomp; m = t.length; t = '$' + t
dp = Array.new(n+1){Array.new(m+1){0}}
def min(a, b)
return a < b ? a : b
end
1.upto(n){|i|
dp[0][i] = dp[i][0] = i
}
1.upto(n){|i|
1.upto(m){|j|
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1] + (s[i] != t[j] ? 1 : 0))
}
}
# build alignment .. .
s_ = t_ = ''; i, j = n, m
while !i.zero? || !j.zero? do
if (j.zero? || dp[i][j] == dp[i-1][j] + 1) then
s_ += s[i]; t_ += '-'
i -= 1
elsif (i.zero? || dp[i][j] == dp[i][j-1] + 1) then
s_ += '-'; t_ += t[j]
j -= 1
else
s_ += s[i]; t_ += t[j]
i -= 1; j -= 1
end
end
s_.reverse!; t_.reverse!
puts dp[n][m], s_, t_
