脱水缩合
(merge.c/cpp/pas)
【题目描述】
fqk 退役后开始补习文化课啦， 于是他打开了生物必修一开始复习
蛋白质，他回想起了氨基酸通过脱水缩合生成肽键，具体来说，一个
氨基和一个羧基会脱去一个水变成一个肽键。于是他脑洞大开，给你
出了这样一道题：
fqk 将给你 6 种氨基酸和 m 个脱水缩合的规则，氨基酸用
' ' , ' ' , ' ' , ' ' , ' ' , ' ' f e d c b a 表示，每个规则将给出两个字符串 t s, ，其中
1 | | , 2 | | t s ，表示 s 代表的两个氨基酸可以通过脱水缩合变成 t 。然后
请你构建一个长度为 n ,且仅由 ' ' , ' ' , ' ' , ' ' , ' ' , ' ' f e d c b a 构成的氨基酸序列，
如果这个序列的前两个氨基酸可以进行任意一种脱水缩合， 那么就可
以脱水缩合，脱水缩合后序列的长度将 1 ，这样如果可以进行 1 n 次
脱水缩合，最终序列的长度将变为 1 ，我们可以认为这是一个蛋白质，
如果最后的蛋白质为 ' 'a ， 那么初始的序列就被称为一个好的氨基酸序
列。 fqk 想让你求出有多少好的氨基酸序列。
注：题目描述可能与生物学知识有部分偏差（即氨基酸进行脱水
缩合后应该是肽链而不是新的氨基酸），请以题目描述为准。
【输入格式】
第一行两个整数 q n, 。
接下来 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 的数据， 36 , 6 2 q n 。数据存在梯度。
【时空限制】
对于每个测试点，时间限制为 s 2 ,空间限制为 MB 512 。
思路：
纯搜索题
我们从"a"开始搜索，每次搜到长度等于n的序列就return
不需要判断这个序列是否合法
因为就是从"a"出来的
这个序列一定合法的
唯一需要判定的就是是否重复
判断是否重复最好用bfs写
而且这个题的数据范围特别小
但是
当时脑抽不知道怎么着就写了个dfs
按理说dfs是能过的
但是脑子又抽了一下
判断还放在了return的后面
天啊，50分就这么没了
要不是这数据水我就爆零了
这告诉我们脑子是个好东西
所以
以后写搜索一定要先判断是否重复
来，上代码：
（附两个代码，一个是dfs（虽然标解就是dfs），另一个是bfs）
dfs：
#include<map> #include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; struct node { string from,to; int next; }; struct node edge[40]; int n,q,num; long long int ans=0; string cur,kol; map<char,int>head; map<string,bool>pd; void edge_add(string from,string to) { num++; edge[num].to=to; edge[num].from=from; edge[num].next=head[from[0]]; head[from[0]]=num; } void dfs(string kcc,int now) { if(pd[kcc]==true) return ; if(now==n) { //cout<<kcc<<endl; ans++; return ; } string kll=kcc; for(int i=head[kcc[kcc.length()-1]];i!=0;i=edge[i].next) { string::iterator it=kcc.end()-1; kcc.erase(it); kcc+=edge[i].to; dfs(kcc,now+1); pd[kcc]=true; kcc=kll; } } int main() { scanf("%d%d",&n,&q); n--; for(int i=1;i<=q;i++) { cin>>cur>>kol; swap(cur[0],cur[1]); edge_add(kol,cur); } dfs("a",0); cout<<ans<<endl; return 0; }
bfs：
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<string> #include<iostream> using namespace std; struct node { string from,to; int next; }; struct node edge[1000]; int n,q,num; long long int ans=0; string cur,kol; map<char,int>head; map<string,bool>pd; queue<string>que; void edge_add(string from,string to) { num++; edge[num].to=to; edge[num].from=from; edge[num].next=head[from[0]]; head[from[0]]=num; } void bfs() { string start="a"; que.push(start); pd[start]=true; while(!que.empty()) { cur=que.front(); for(int i=head[cur[cur.length()-1]];i!=0;i=edge[i].next) { kol=que.front(); string::iterator it=kol.end()-1; kol.erase(it); kol+=edge[i].to; if(pd[kol]==false) { pd[kol]=true; if(kol.length()>=n) ans++; else que.push(kol); } } que.pop(); } } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=q;i++) { cin>>cur>>kol; swap(cur[0],cur[1]); edge_add(kol,cur); } bfs(); cout<<ans<<endl; return 0; }