e977 - 11962 - DNA II
題目描述
題目要求將輸入的 DNA 字串轉換為一個整數表示形式，該整數由字串的長度和一個基於 DNA 序列的序號組成。DNA 序列由 A、C、G 和 T 四個字符組成，每個字符對應一個不同的數值（A=0, C=1, G=2, T=3）。序號的計算方式是將 DNA 序列轉換為以 4 為基數的數字。
解題思路
程式碼首先讀取測試案例的數量。對於每個測試案例，它讀取 DNA 字串，然後將其轉換為一個以 4 為基數的整數。轉換的過程是將每個 DNA 字符轉換為其對應的數值（C=1, G=2, T=3），然後將這個數值加到一個累加器中，每次左移 2 位，相當於乘以 4。最後，程式碼輸出 "Case X: (長度:序號)"，其中 X 是測試案例編號，長度是 DNA 字串的長度，序號是計算出的以 4 為基數的整數。
複雜度分析
- 時間複雜度: O(n)，其中 n 是 DNA 字串的長度。程式碼需要遍歷 DNA 字串一次來計算序號。
- 空間複雜度: O(1)。程式碼使用的額外空間是常數級別的，例如儲存 DNA 字串和一些整數變數。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(long long int x) {
if(!x){
putchar_unlocked('0');
return;
}
long long int stk[15],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int n;
char a[31],t;
n=read();
for(int c=1;c<=n;++c){
int al=0;
while(t=getchar_unlocked()){
if(t<'A')break;
a[al]=t;
++al;
}
long long int ans=0;
for(int i=0;i<al;++i){
ans<<=2;
if(a[i]=='C')
++ans;
else if(a[i]=='G')
ans+=2;
else if(a[i]=='T')
ans+=3;
}
putchar_unlocked('C');
putchar_unlocked('a');
putchar_unlocked('s');
putchar_unlocked('e');
putchar_unlocked(' ');
write(c);
putchar_unlocked(':');
putchar_unlocked(' ');
putchar_unlocked('(');
write(al);
putchar_unlocked(':');
write(ans);
putchar_unlocked(')');
putchar_unlocked('\n');
}
}