【題目描述】
fqk 退役后開始補習文化課啦， 于是他打開了生物必修一開始復習蛋白質，他回想起了氨基酸通過脫水縮合生成肽鍵，具體來說，一個氨基和一個羧基會脫去一個水變成一個肽鍵。于是他腦洞大開，給你出了這樣一道題：
fqk 將給你 6 種氨基酸和 m 個脫水縮合的規則，氨基酸用'a ' , ' b' , ' c' , 'd ' , ' e' , 'f '表示，每個規則將給出兩個字符串 t s, ，其中?| s| =2, |t | =1，表示 s 代表的兩個氨基酸可以通過脫水縮合變成 t 。然后請你構建一個長度為 n ,且僅由 'a ' , ' b' , 'c ' , 'd ' , ' e' , ' f' ?構成的氨基酸序列，如果這個序列的前兩個氨基酸可以進行任意一種脫水縮合， 那么就可
以脫水縮合，脫水縮合后序列的長度將 1 ? ，這樣如果可以進行 1 ? n 次脫水縮合，最終序列的長度將變為 1 ，我們可以認為這是一個蛋白質，如果最后的蛋白質為 ' 'a ， 那么初始的序列就被稱為一個好的氨基酸序列。 fqk 想讓你求出有多少好的氨基酸序列。
注：題目描述可能與生物學知識有部分偏差（即氨基酸進行脫水縮合后應該是肽鏈而不是新的氨基酸），請以題目描述為準。
【輸入格式】
第一行兩個整數 n, q。
接下來 q 行，每行兩個字符串 t s, ，表示一個脫水縮合的規則。
【輸出格式】
一行，一個整數表示有多少好的氨基酸序列。
【輸入樣例】
3 5
ab a
cc c
ca a
ee c
ff d
【輸出樣例】
4
【樣例解釋】
一共有四種好的氨基酸序列，其脫水縮合過程如下：
"abb"--> "ab"--> "a"
"cab" -->"ab"--> "a"
"cca" -->"ca"--> "a"
"eea" -->"ca" -->"a"
【數據范圍】
對于 100% 的數據，2<=n<=6, q<=36

#include<cstdio> #include<iostream> using namespace std; char q[7],a[40],b[40],c[40]; int n,m,ans,flag; void Dfs(int t) {if(flag)return;if(t==n&&q[t]=='a'){flag=1;return;}for(int i=1;i<=m;i++)if(a[i]==q[t]&&b[i]==q[t+1]){q[t+1]=c[i];Dfs(t+1);q[t+1]=b[i];} } void check() {flag=0;Dfs(1);if(flag)ans++; } void dfs(int t) {if(t>n){check();return;}for(int i=0;i<=5;i++){q[t]=char(i+'a');dfs(t+1);} } int main() {//freopen("jh.in","r",stdin);freopen("merge.in","r",stdin);freopen("merge.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)cin>>a[i]>>b[i]>>c[i];dfs(1);printf("%d",ans);return 0; }

?

。數據存在梯度。
【時空限制】
對于每個測試點，時間限制為 s 2 ,空間限制為 MB 512 。

?

轉載于:https://www.cnblogs.com/thmyl/p/7359399.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的脱水缩合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。