Sicily 1035 DNA matching

古城微笑少年丶 2022-08-06 12:19 152阅读 0赞

解题思路：

对于每一组数据，把第一个字符串与其以后所有的字符串进行比较（标记第一个字符串），如果互为互补序列，则把该字符串进行标记，并把所求的组数加1，并结束此次比较；然后依次用第二个、第三个、、、（标记第二个、第三个、、、字符串）与其以后的字符串进行比较，直至第n+1个。在比较过程中，要判断用于比较的字符串是否已经被标记，如果标记则跳过此字符串；并且判断被比较的字符串是否已经被标记，如果标记则跳过此字符串。

代码：

\#include<iostream>  
\#include<string>  
using namespace std;  
bool com(char num1,char num2)      //判断字符是否对应  
\{  
 if(num1=='A')  
    \{  
    if(num2=='T')  
      return true;  
    else  
      return false;  
    \}  
 if(num1=='T')  
    \{  
    if(num2=='A')  
      return true;  
    else  
      return false;  
    \}  
 if(num1=='G')  
    \{  
    if(num2=='C')  
      return true;  
    else  
      return false;  
    \}  
 else if(num1=='C')  
    \{  
    if(num2=='G')  
      return true;  
    else  
      return false;  
    \}  
\}  
bool judge(string num1,string num2)      //判断两个字符串是否为互补  
\{  
 for(int i=0;i<num1.length() ;i++)  
 \{  
  if(!com(num1\[i\],num2\[i\]))  
    return false;   
 \}  
 return true;  
\}  
int main()  
\{  
 int a,b;  
 cin>>a;  
 for(int i=0;i<a;i++)  
 \{  
  cin>>b;  
  string num\[101\];  
  int c=0;                          //表示配对的组数  
  int num1\[101\];                    //标记是否已经配对  
  for(int j=0;j<b;j++)  
    \{  
     cin>>num\[j\];  
     num1\[j\]=0;  
    \}  
    
  for(int j=0;j<b-1;j++)  
  \{  
        if(num1\[j\]==0)  
     \{  
         num1\[j\]=1;  
         for(int k=j+1;k<b;k++)  
         \{  
          if(num1\[k\]==0)  
          \{  
           if(num\[j\].length()==num\[k\].length())  
        \{  
           if(judge(num\[j\],num\[k\]))  
           \{  
            c++;  
           num1\[k\]=1;  
           break;  
           \}  
         
          \}   
          \}  
          \}  
     \}  
    
      
  \}  
  cout<<c<<endl;  
\}  
return 0;  
\}