Genotype&&陨石的秘密

素颜马尾好姑娘i 2021-12-11 13:47 251阅读 0赞

**Genotype：**

**Genotype** 是一个有限的基因序列。它是由大写的英文字母A-Z组成，不同的字母表示不同种类的基因。一个基因可以分化成为一对新的基因。这种分化被一个定义的规则集合所控制。每个分化的规则可以用三个大写字母A1A2A3表示，含义为基因A1可以分化成A2A3

我们用S代表特种基因，繁殖genotype是从特种基因序列开始。根据给定的规则，它由被选择控制规则对基因不断进行繁殖而成。

## 任务 ##

从文本文件GEN.IN 读入一个定义的规则集和一个想生成的genotypes 单词序列

对每一个给定的 genotype，根据给定的分化规则，检查是否它能从某一个确定特种基因序列生成，如果能，找到最小的序列长度，

将结果写入文本文件GEN.OUT.

## 输入 ##

在文件GEN.IN 的第一行有一个整数n, 1 <= n <= 10000. 下面n 每一行为一个分化规则. 这些规则都由包含A – Z的三个大写字母组成.

接下来有一个整数k, 1 <= k <= 10000. 接下来的k 行有一个 genotype. Genotype由没有空格的单词组成，最多100 个英文大写字母.

## 输出 ##

在文件GEN.OUT中有k行,在第I行应写入: 一个正整数――需要生成第I个genotypes的最小长度；或者单词 NIE, 如果不能生成对应的genotype。

\--------------------------------------------------------------------

Ps.数据已弱化，可水过- =

读取时用一个map\[A\]\[B\]数组表示 字母AB能变成的字母

由于只有26个字母，可以用一个26位的二进制数表示

进行两次动归

f\[i\]\[j\]表示从字符串 从 i 到 j 能变成的字母，同理也是个二进制数

f\[i\]\[j\]=f\[i\]\[j\] |map\[c1\]\[c2\] 存在 (f\[i\]\[k\]&char\[c1\]&&f\[k+1\]\[j\]&char\[c2\])

不难得到那几段字符串能变成 ‘S’

在进行一次动归

g\[i\]表示前 i 个字符能变成几个 ‘S’

g\[i\]=min(g\[j\]+1) 存在(f\[i\]\[j+1\]&char\['S'\])

复杂度O(len^3\*26^2)+O(len^2)

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<algorithm>
     3 #include<string>
     4 #include<cstring>
     5 #include<iostream>
     6 #include<cmath>
     7 #define LL long long
     8 #define INF 99999999
     9 #define Min(num1,num2) if(num1>num2) num1=num2
    10 #define Max(num1,num2) if(num1<num2) num1=num2
    11 using namespace std;
    12 int n,f[101][101],g[101],num[101],map[101][101];
    13 string s;
    14 void work(){
    15     memset(f,0,sizeof f);
    16     cin>>s;
    17     int l=s.size();
    18     for(int k=1,i=0;i<l;k++,i++) f[k][k]=num[s[i]-'A'];
    19     for(int p=1;p<=l;p++)
    20         for(int i=1;i<=l;i++){
    21             int j=i+p;
    22             if(j>l) break;
    23             for(int k=i;k<j;k++)
    24           for(int ci=0;ci<26;ci++)
    25                     for(int cj=0;cj<26;cj++)                
    26                         if((f[i][k]&num[ci])&&(f[k+1][j]&num[cj]))
    27                             f[i][j]|=map[ci][cj];
    28                         
    29          }
    30     int key='S'-'A';
    31     for(int i=1;i<=l;i++) g[i]=INF;
    32     g[0]=0;
    33     for(int i=1;i<=l;i++)
    34         for(int j=1;j<=i;j++)
    35             if((f[j][i]&num[key])&&g[j-1]!=INF)
    36                 Min(g[i],g[j-1]+1);
    37     g[l]==INF ? printf("NIE\n") : printf("%d\n",g[l]);
    38 } 
    39 int main(){
    40         freopen("GEN.in","r",stdin);
    41         freopen("GEN.out","w",stdout);
    42       scanf("%d\n",&n);
    43         num[0]=1;
    44          for(int i=1;i<=26;i++) num[i]=num[i-1]<<1;
    45       for(int a,b,c,i=1;i<=n;i++){
    46             a=getchar()-'A';
    47              b=getchar()-'A';
    48              c=getchar()-'A';
    49              map[b][c]|=num[a];
    50          getchar();
    51          }
    52          int T;
    53          scanf("%d\n",&T);
    54       while(T--) work();  
    55 }

\---------------------------------------------------------------------------

**陨石的秘密：**

公元11380年，一颗巨大的陨石坠落在南极。于是，灾难降临了，地球上出现了一系列反常的现象。当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含5个整数：

**1 1 1 1 6**

**0 0 6 3 57**

**8 0 11 3 2845**

著名的科学家SS发现，这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算，他定义了一种SS表达式：

1．  SS表达式是仅由‘\{’，‘\}’，‘\[’，‘\]’，‘（’，‘）’组成的字符串。

2．  一个空串是SS表达式。

3．  如果A是SS表达式，且A中不含字符‘\{’，‘\}’，‘\[’，‘\]’，则(A)是SS表达式。

4．  如果A是SS表达式，且A中不含字符‘\{’，‘\}’，则\[A\]是SS表达式。

5．  如果A是SS表达式，则\{A\}是SS表达式。

6．  如果A和B都是SS表达式，则AB也是SS表达式。

例如

**()(())\[\]**

**\{()\[()\]\}**

**\{ \{\[\[(())\]\]\}\}**

都是SS表达式。

而

**()(\[\])()**

**\[()**

不是SS表达式。

一个SS表达式E的深度D(E)定义如下：

例如()\{()\}\[\]的深度为2。

密文中的复杂运算是这样进行的：

设密文中每行前4个数依次为L1，L2，L3，D，求出所有深度为D，含有L1对\{\}，L2对\[\]，L3对()的SS串的个数，并用这个数对当前的年份11380求余数，这个余数就是密文中每行的第5个数，我们称之为“神秘数”。

密文中某些行的第五个数已经模糊不清，而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

**输入文件**

共一行，4个整数L1，L2，L3，D。相邻两个数之间用一个空格分隔。

（0≤L1≤10，0≤L2≤10，0≤L3≤10，0≤D≤30）

**输出文件**

共一行，包含一个整数，即神秘数。

\---------------------------------------------------------------------------

Ps。坑爹数学题- =

题目所求在 l1个｛｝ l2个\[\]  l3个() 是有几个深度为 D 的 SS 串，

不妨设(g\[l1\]\[l2\]\[l3\]\[D\])为使用 l1个｛｝ l2个\[\]  l3个() 时深度不超过 D 的 SS 串数目

题目所求就是 g\[l1\]\[l2\]\[l3\]\[D\]-g\[l1\]\[l2\]\[l3\]\[D-1\]

转移：

可以由以下集中状态转移过来：

(---------)-------------g\[ 0 \]\[ 0 \]\[ i \]\[D-1\]\*g\[l1      \]\[l2     \]\[l3-i-1\]

\[---------\]-------------g\[ 0 \]\[ j \]\[ i \]\[D-1\]\*g\[l1      \]\[l2-j-1\]\[l3-i   \]

\{--------\}-------------g\[ k \]\[ j \]\[ i \]\[D-1\]\*g\[l1-k-1\]\[l2-j    \]\[l3-i   \]

累加起来就是 g\[l1\]\[l2\]\[l3\]\[D\]

Ps.边界 g\[0\]\[0\]\[0\]\[D\]=0

代码如下:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<algorithm>
     3 #include<string>
     4 #include<cstring>
     5 #include<iostream>
     6 #include<cmath>
     7 #define LL long long
     8 #define INF 999999999
     9 #define Min(num1,num2) if(num1>num2) num1=num2
    10 #define Max(num1,num2) if(num1<num2) num1=num2
    11 #define key 11380
    12 //using namespace std ;
    13 int f[12][12][12][32],L1,L2,L3,D;
    14 int main(){
    15   freopen("secret.in","r",stdin);
    16   freopen("secret.out","w",stdout);
    17   scanf("%d%d%d%d",&L3,&L2,&L1,&D);
    18   for(int i=0;i<=D;i++) f[0][0][0][i]=1;
    19     for(int d=1;d<=D;d++)
    20         for(int l1=0;l1<=L1;l1++)
    21           for(int l2=0;l2<=L2;l2++)
    22               for(int l3=0;l3<=L3;l3++)
    23                 if(l1||l2||l3){
    24                  int sum=0;
    25                 //{ }
    26                     for(int i=0;i<=l1;i++)
    27                         for(int j=0;j<=l2;j++)
    28                           for(int k=0;k<l3;k++)
    29                                 sum=(sum+f[i][j][k][d-1]*f[l1-i][l2-j][l3-k-1][d])%key;
    30                 //[ ]
    31                     for(int i=0;i<=l1;i++)
    32                         for(int j=0;j<l2;j++)
    33                           sum=(sum+f[i][j][0][d-1]*f[l1-i][l2-j-1][l3][d])%key;
    34                 //( )
    35                     for(int i=0;i<l1;i++)
    36                       sum=(sum+f[i][0][0][d-1]*f[l1-1-i][l2][l3][d])%key;
    37                   f[l1][l2][l3][d]=sum;
    38                 }
    39         printf("%d",(f[L1][L2][L3][D]-f[L1][L2][L3][D-1]+key)%key);
    40 }

转载于:https://www.cnblogs.com/Blacko/p/3404742.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211211/7d513b2914e34e1895c29470de251f21.png