脱水缩合
题目描述：
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想让你求出有多少好的氨基酸序列。
注：题目描述可能与生物学知识有部分偏差（即氨基酸进行脱水
缩合后应该是肽链而不是新的氨基酸），请以题目描述为准。
输入格式:
第一行两个整数q,n。
接下来q行，每行两个字符串s,t表示一个脱水缩合的规则。
输出格式:
一行，一个整数表示有多少好的氨基酸序列。
输入样例:
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 数据存在梯度。
时空限制:
对于每个测试点,时间限制为2s,空间限制为512MB。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
map<int,bool>ma;
struct node
{
int tot;
int sum;
}e;
queue<node> q;
char s1[2],s2;
int n,m,ans,a[100][100];
int power(int x)
{
int ans=1;
for(int i=1;i<=x;i++)
ans=ans*10;
return ans;
}
int main()
{
freopen("merge.in","r",stdin);
freopen("merge.out","w",stdout);
e.sum=1,e.tot=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x=0;
cin>>s1>>s2;
x=s1[0]-96;
x=x*10+s1[1]-96;
a[s2-96][++a[s2-96][0]]=x;
}
q.push(e);
while(!q.empty())
{
e=q.front();
q.pop();
if(e.tot==n&&!ma[e.sum]) ans++,ma[e.sum]=1;
if(e.tot>n) break;
int tmp;
if(e.sum>1) tmp=power(e.tot-1);
else tmp=1;
for(int i=1;i<=a[e.sum/tmp][0];i++)
{
node t;
t.sum=a[e.sum/tmp][i]*tmp+e.sum%power(e.tot-1);
t.tot=e.tot+1;
q.push(t);
}
}
printf("%d",ans);
fclose(stdin);fclose(stdout);
return 0;
}